Approximate minimum degree permutation
P = amd(A)
P = amd(A,opts)
P = amd(A) returns the
approximate minimum degree permutation vector for the sparse matrix
= A + A'. The Cholesky factorization of
to be sparser than that of
amd function tends to be faster than
symamd, and also tends to return better
be square. If
A is a full matrix, then
P = amd(A,opts) allows additional
options for the reordering. The
opts input is a
structure with the two fields shown below. You only need to set the
fields of interest:
dense — A
nonnegative scalar value that indicates what is considered to be dense.
If A is n-by-n, then rows and columns with more than
A + A' are considered to be "dense" and are
ignored during the ordering. MATLAB® software places these rows
and columns last in the output permutation. The default value for
this field is 10.0 if this option is not present.
aggressive — A scalar value controlling aggressive absorption. If this field is set to a nonzero value, then aggressive absorption is performed. This is the default if this option is not present.
MATLAB software performs an assembly tree post-ordering,
which is typically the same as an elimination tree post-ordering.
It is not always identical because of the approximate degree update
used, and because "dense" rows and columns do not take
part in the post-order. It well-suited for a subsequent
chol operation, however, If you require
a precise elimination tree post-ordering, you can use the following
P = amd(S); C = spones(S)+spones(S'); [ignore, Q] = etree(C(P,P)); P = P(Q);
already symmetric, omit the second line,
C = spones(S)+spones(S').
This example constructs a sparse matrix and computes a two Cholesky
factors: one of the original matrix and one of the original matrix
amd. Note how much sparser the
Cholesky factor of the preordered matrix is compared to the factor
of the matrix in its natural ordering:
A = gallery('wathen',50,50); p = amd(A); L = chol(A,'lower'); Lp = chol(A(p,p),'lower'); figure; subplot(2,2,1); spy(A); title('Sparsity structure of A'); subplot(2,2,2); spy(A(p,p)); title('Sparsity structure of AMD ordered A'); subplot(2,2,3); spy(L); title('Sparsity structure of Cholesky factor of A'); subplot(2,2,4); spy(Lp); title('Sparsity structure of Cholesky factor of AMD ordered A'); set(gcf,'Position',[100 100 800 700]);