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
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.
p = symamd(S,knobs)
where knobs
is
a scalar. If S
is n
byn
,
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')
.
[p,stats] = symamd(...)
produces
the optional vector stats
that provides data about
the ordering and the validity of the matrix S
.
stats(1)  Number of dense or empty rows ignored by 
stats(2)  Number of dense or empty columns ignored by 
stats(3)  Number of garbage collections performed on the internal
data structure used by 
stats(4) 

stats(5)  Rightmost column index that is unsorted or contains duplicate
entries, or 
stats(6)  Last seen duplicate or outoforder row index in the
column index given by 
stats(7)  Number of duplicate and outoforder row indices 
Although, MATLAB^{®} builtin 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:
If a row index appears two or more times in the same
column, symamd
ignores the duplicate entries, continues
processing, and provides information about the duplicate entries in stats(4:7)
.
If row indices in a column are out of order, 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 outoforder entries
in stats(4:7)
.
If 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 postordering.
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/