MATLAB Function Reference |
Symmetric approximate minimum degree permutation
Syntax
Description
p = symamd(S)
for a symmetric positive definite matrix S
, returns the permutation vector p
such that S(p,p)
tends to have a sparser Cholesky factor than S
. To find the ordering for S
, symamd
constructs a matrix M
such that spones(M'*M) = spones (S)
, and then computes p = colamd(M)
. The symamd
function may also work well for symmetric indefinite matrices.
S
must be square; only the strictly lower triangular part is referenced.
knobs
is a scalar. If S
is n
-by-n
, rows and columns with more than knobs*n
entries are removed prior to ordering, and ordered last in the output permutation p
. If the knobs
parameter is not present, then knobs = spparms('wh_frac')
.
stats
is an optional vector that provides data about the ordering and the validity of the matrix S
.
Although, MATLAB built-in functions generate valid sparse matrices, a user may construct an invalid sparse matrix using the MATLAB C or Fortran APIs and pass it to symamd
. For this reason, symamd
verifies that S
is valid:
symamd
ignores the duplicate entries, continues processing, and provides information about the duplicate entries in stats(4:7)
.
symamd
sorts each column of its internal copy of the matrix S
(but does not repair the input matrix S
), continues processing, and provides information about the out-of-order entries in stats(4:7)
.
S
is invalid in any other way, symamd
cannot continue. It prints an error message, and returns no output arguments (p
or stats
).
The ordering is followed by a symmetric elimination tree post-ordering.
Note
symamd tends to be faster than symmmd and tends to return a better ordering.
|
Examples
Here is a comparison of reverse Cuthill-McKee and minimum degree on the Bucky ball example mentioned in the symrcm
reference page.
B = bucky+4*speye(60); r = symrcm(B); p = symamd(B); R = B(r,r); S = B(p,p); subplot(2,2,1), spy(R,4), title('B(r,r)') subplot(2,2,2), spy(S,4), title('B(s,s)') subplot(2,2,3), spy(chol(R),4), title('chol(B(r,r))') subplot(2,2,4), spy(chol(S),4), title('chol(B(s,s))')
Even though this is a very small problem, the behavior of both orderings is typical. RCM produces a matrix with a narrow bandwidth which fills in almost completely during the Cholesky factorization. Minimum degree produces a structure with large blocks of contiguous zeros which do not fill in during the factorization. Consequently, the minimum degree ordering requires less time and storage for the factorization.
See Also
colamd
, colmmd
, colperm
, spparms
, symmmd
, symrcm
References
The authors of the code for symamd
are Stefan I. Larimore and Timothy A. Davis (davis@cise.ufl.edu
), University of Florida. The algorithm was developed in collaboration with John Gilbert, Xerox PARC, and Esmond Ng, Oak Ridge National Laboratory. Sparse Matrix Algorithms Research at the University of Florida: http://www.cise.ufl.edu/research/sparse/
switch | symbfact |
© 1994-2005 The MathWorks, Inc.