|
5164
|
1 function [p, stats] = symamd (S, knobs) |
|
|
2 %SYMAMD Symmetric approximate minimum degree permutation. |
|
|
3 % P = SYMAMD (S) for a symmetric positive definite matrix S, returns the |
|
|
4 % permutation vector p such that S(p,p) tends to have a sparser Cholesky |
|
|
5 % factor than S. Sometimes SYMAMD works well for symmetric indefinite |
|
|
6 % matrices too. SYMAMD tends to be faster than SYMMMD and tends to return |
|
|
7 % a better ordering. The matrix S is assumed to be symmetric; only the |
|
|
8 % strictly lower triangular part is referenced. S must be square. |
|
|
9 % |
|
|
10 % See also COLMMD, COLPERM, SPPARMS, COLAMD, SYMMMD, SYMRCM. |
|
|
11 % |
|
|
12 % Usage: P = symamd (S) |
|
|
13 % P = symamd (S, knobs) |
|
|
14 % [P, stats] = symamd (S) |
|
|
15 % [P, stats] = symamd (S, knobs) |
|
|
16 % |
|
|
17 % knobs is an optional input argument. If S is n-by-n, then rows and |
|
|
18 % columns with more than knobs(1)*n entries are removed prior to ordering, |
|
|
19 % and ordered last in the output permutation P. If the knobs parameter is not |
|
|
20 % present, then the default of 0.5 is used instead. knobs (2) controls the |
|
|
21 % printing of statistics and error messages. |
|
|
22 % |
|
|
23 % stats is an optional 20-element output vector that provides data about the |
|
|
24 % ordering and the validity of the input matrix S. Ordering statistics are |
|
|
25 % in stats (1:3). stats (1) = stats (2) is the number of dense or empty |
|
|
26 % rows and columns ignored by SYMAMD and stats (3) is the number of |
|
|
27 % garbage collections performed on the internal data structure used by |
|
|
28 % SYMAMD (roughly of size 8.4*nnz(tril(S,-1)) + 9*n integers). |
|
|
29 % |
|
|
30 % MATLAB built-in functions are intended to generate valid sparse matrices, |
|
|
31 % with no duplicate entries, with ascending row indices of the nonzeros |
|
|
32 % in each column, with a non-negative number of entries in each column (!) |
|
|
33 % and so on. If a matrix is invalid, then SYMAMD may or may not be able |
|
|
34 % to continue. If there are duplicate entries (a row index appears two or |
|
|
35 % more times in the same column) or if the row indices in a column are out |
|
|
36 % of order, then SYMAMD can correct these errors by ignoring the duplicate |
|
|
37 % entries and sorting each column of its internal copy of the matrix S (the |
|
|
38 % input matrix S is not repaired, however). If a matrix is invalid in other |
|
|
39 % ways then SYMAMD cannot continue, an error message is printed, and no |
|
|
40 % output arguments (P or stats) are returned. SYMAMD is thus a simple way |
|
|
41 % to check a sparse matrix to see if it's valid. |
|
|
42 % |
|
|
43 % stats (4:7) provide information if SYMAMD was able to continue. The |
|
|
44 % matrix is OK if stats (4) is zero, or 1 if invalid. stats (5) is the |
|
|
45 % rightmost column index that is unsorted or contains duplicate entries, |
|
|
46 % or zero if no such column exists. stats (6) is the last seen duplicate |
|
|
47 % or out-of-order row index in the column index given by stats (5), or zero |
|
|
48 % if no such row index exists. stats (7) is the number of duplicate or |
|
|
49 % out-of-order row indices. |
|
|
50 % |
|
|
51 % stats (8:20) is always zero in the current version of SYMAMD (reserved |
|
|
52 % for future use). |
|
|
53 % |
|
|
54 % The ordering is followed by a column elimination tree post-ordering. |
|
|
55 % |
|
|
56 % Authors: |
|
|
57 % |
|
|
58 % The authors of the code itself are Stefan I. Larimore and Timothy A. |
|
|
59 % Davis (davis@cise.ufl.edu), University of Florida. The algorithm was |
|
|
60 % developed in collaboration with John Gilbert, Xerox PARC, and Esmond |
|
|
61 % Ng, Oak Ridge National Laboratory. |
|
|
62 % |
|
|
63 % Date: |
|
|
64 % |
|
|
65 % September 8, 2003. Version 2.3. |
|
|
66 % |
|
|
67 % Acknowledgements: |
|
|
68 % |
|
|
69 % This work was supported by the National Science Foundation, under |
|
|
70 % grants DMS-9504974 and DMS-9803599. |
|
|
71 |
|
|
72 % Notice: |
|
|
73 % Copyright (c) 1998-2003 by the University of Florida. |
|
|
74 % All Rights Reserved. |
|
|
75 % |
|
|
76 % See http://www.cise.ufl.edu/research/sparse/colamd (the colamd.c |
|
|
77 % file) for the License. |
|
|
78 % |
|
|
79 % Availability: |
|
|
80 % |
|
|
81 % The colamd/symamd library is available at |
|
|
82 % |
|
|
83 % http://www.cise.ufl.edu/research/sparse/colamd/ |
|
|
84 % |
|
|
85 |
|
|
86 %------------------------------------------------------------------------------- |
|
|
87 % perform the symamd ordering: |
|
|
88 %------------------------------------------------------------------------------- |
|
|
89 |
|
|
90 if (nargout <= 1 & nargin == 1) |
|
|
91 p = symamdmex (S) ; |
|
|
92 elseif (nargout <= 1 & nargin == 2) |
|
|
93 p = symamdmex (S, knobs) ; |
|
|
94 elseif (nargout == 2 & nargin == 1) |
|
|
95 [p, stats] = symamdmex (S) ; |
|
|
96 elseif (nargout == 2 & nargin == 2) |
|
|
97 [p, stats] = symamdmex (S, knobs) ; |
|
|
98 else |
|
|
99 error ('symamd: incorrect number of input and/or output arguments') ; |
|
|
100 end |
|
|
101 |
|
|
102 %------------------------------------------------------------------------------- |
|
|
103 % symmetric elimination tree post-ordering: |
|
|
104 %------------------------------------------------------------------------------- |
|
|
105 |
|
|
106 [ignore, q] = sparsfun ('symetree', S (p,p)) ; |
|
|
107 p = p (q) ; |
|
|
108 |
