## Documentation Center |

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 `C
= A + A'`. The Cholesky factorization of `C(P,P)` or `A(P,P)` tends
to be sparser than that of `C` or `A`.
The `amd` function tends to be faster than `symamd`, and also tends to return better
orderings than `symamd`. Matrix `A` must
be square. If `A` is a full matrix, then `amd(A)` is
equivalent to `amd(sparse(A))`.

`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`max(16,(dense*sqrt(n)))`entries in`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
code:

P = amd(S); C = spones(S)+spones(S'); [ignore, Q] = etree(C(P,P)); P = P(Q);

If `S` is
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
preordered by `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]);

Was this topic helpful?