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?