MATLAB Function Reference |
Sparse column minimum degree permutation
Syntax
Note
colmmd is obsolete and will be removed from a future version of MATLAB. Use colamd instead.
|
Description
p = colmmd(S)
returns the column minimum degree permutation vector for the sparse matrix S
. For a nonsymmetric matrix S
, this is a column permutation p
such that S(:,p)
tends to have sparser LU factors than S
.
The colmmd
permutation is automatically used by \
and /
for the solution of nonsymmetric and symmetric indefinite sparse linear systems.
Use spparms
to change some options and parameters associated with heuristics in the algorithm.
Algorithm
The minimum degree algorithm for symmetric matrices is described in the review paper by George and Liu [1]. For nonsymmetric matrices, the MATLAB minimum degree algorithm is new and is described in the paper by Gilbert, Moler, and Schreiber [2]. It is roughly like symmetric minimum degree for A'*A
, but does not actually form A'*A
.
Each stage of the algorithm chooses a vertex in the graph of A'*A
of lowest degree (that is, a column of A
having nonzero elements in common with the fewest other columns), eliminates that vertex, and updates the remainder of the graph by adding fill (that is, merging rows). If the input matrix S
is of size m
-by-n
, the columns are all eliminated and the permutation is complete after n
stages. To speed up the process, several heuristics are used to carry out multiple stages simultaneously.
See Also
colamd
, colperm
, lu
, spparms
, symamd
, symmmd
, symrcm
The arithmetic operator \
References
[1] George, Alan and Liu, Joseph, "The Evolution of the Minimum Degree Ordering Algorithm," SIAM Review, 1989, 31:1-19.
[2] 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.
colamd | colorbar |
© 1994-2005 The MathWorks, Inc.