MATLAB Function Reference
  Go to function:
    Search    Help Desk 
symmmd    Examples   See Also

Sparse symmetric minimum degree ordering

Syntax

Description

p = symmmd(S) returns a symmetric minimum degree ordering of S. For a symmetric positive definite matrix S, this is a permutation p such that S(p,p) tends to have a sparser Cholesky factor than S. Sometimes symmmd works well for symmetric indefinite matrices too.

Remarks

The minimum degree ordering is automatically used by \ and / for the solution of symmetric, positive definite, sparse linear systems.

Some options and parameters associated with heuristics in the algorithm can be changed with spparms.

Algorithm

The symmetric minimum degree algorithm is based on the column minimum degree algorithm. In fact, symmmd(A) just creates a nonzero structure K such that K'*K has the same nonzero structure as A and then calls the column minimum degree code for K.

Examples

Here is a comparison of reverse Cuthill-McKee and minimum degree on the Bucky ball example mentioned in the symrcm reference page.

Even though this is a very small problem, the behavior of both orderings is typical. RCM produces a matrix with a narrow bandwidth which fills in almost completely during the Cholesky factorization. Minimum degree produces a structure with large blocks of contiguous zeros which do not fill in during the factorization. Consequently, the minimum degree ordering requires less time and storage for the factorization.

See Also

colmmd      Sparse column minimum degree permutation

colperm     Sparse column permutation based on nonzero count

symrcm      Sparse reverse Cuthill-McKee ordering

References

[1] Gilbert, John R., Cleve Moler, and Robert Schreiber, "Sparse Matrices in MATLAB: Design and Implementation," SIAM Journal on Matrix Analysis and Applications 13, 1992, pp. 333-356.



[ Previous | Help Desk | Next ]