Documentation

This is machine translation

Translated by
Mouseover text to see original. Click the button below to return to the English version of the page.

amd

Approximate minimum degree permutation

Syntax

```P = amd(A) P = amd(A,opts) ```

Description

`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')`.

Examples

collapse all

Compute the Cholesky factor of a matrix before and after it is ordered using `amd` to examine the effect on sparsity.

Load the barbell graph sparse matrix and add a sparse identity matrix to it to ensure it is positive definite. Compute two Cholesky factors: one of the original matrix and one of the original matrix preordered with `amd`.

```load barbellgraph.mat A = A+speye(size(A)); p = amd(A); L = chol(A,'lower'); Lp = chol(A(p,p),'lower');```

Plot the sparsity patterns of all four matrices. The Cholesky factor obtained from the preordered matrix is much sparser compared to the factor of the matrix in its natural ordering.

```figure subplot(2,2,1) spy(A) title('Original Matrix A') subplot(2,2,2) spy(A(p,p)) title('AMD ordered A') subplot(2,2,3) spy(L) title('Cholesky factor of A') subplot(2,2,4) spy(Lp) title('Cholesky factor of AMD ordered A')```