Symmetric approximate minimum degree permutation
p = symamd(S)
p = symamd(S,knobs)
[p,stats] = symamd(...)
p = symamd(S) for a symmetric
positive definite matrix
S, returns the permutation
p such that
to have a sparser Cholesky factor than
S. To find
the ordering for
M such that
spones(M'*M) = spones
(S), and then computes
p = colamd(M).
symamd function may also work well for symmetric
S must be square; only the strictly lower
triangular part is referenced.
p = symamd(S,knobs) where
a scalar. If
rows and columns with more than
are removed prior to ordering, and ordered last in the output permutation
knobs parameter is not present, then
knobs = spparms('wh_frac').
[p,stats] = symamd(...) produces
the optional vector
stats that provides data about
the ordering and the validity of the matrix
Number of dense or empty rows ignored by
Number of dense or empty columns ignored by
Number of garbage collections performed on the internal
data structure used by
Rightmost column index that is unsorted or contains duplicate
Last seen duplicate or out-of-order row index in the
column index given by
Number of duplicate and out-of-order row indices
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
symamd verifies that
If a row index appears two or more times in the same column,
symamdignores the duplicate entries, continues processing, and provides information about the duplicate entries in
If row indices in a column are out of order,
symamdsorts 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
Sis invalid in any other way,
symamdcannot continue. It prints an error message, and returns no output arguments (
The ordering is followed by a symmetric elimination tree post-ordering.
Compare Reverse Cuthill-McKee and Minimum Degree
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.
 Davis, Timothy A., John R. Gilbert, Stefan I. Larimore, and Esmond G. Ng. “Algorithm 836: COLAMD, a Column Approximate Minimum Degree Ordering Algorithm.” ACM Transactions on Mathematical Software 30, no. 3 (September 2004): 377–380. https://doi.org/10.1145/1024074.1024080.
Run code in the background using MATLAB®
backgroundPool or accelerate code with Parallel Computing Toolbox™
This function fully supports thread-based environments. For more information, see Run MATLAB Functions in Thread-Based Environment.