Column approximate minimum degree permutation
Compare Sparse Matrix and LU Factorization
The Harwell-Boeing collection of sparse matrices and the MATLAB® demos directory include a test matrix
west0479. It is a matrix of order 479 resulting from a model due to Westerberg of an eight-stage chemical distillation column. The spy plot shows evidence of the eight stages. The
colamd ordering scrambles this structure.
load west0479 A = west0479; p = colamd(A); figure() subplot(1,2,1), spy(A,4), title('A') subplot(1,2,2), spy(A(:,p),4), title('A(:,p)')
Comparing the spy plot of the LU factorization of the original matrix with that of the reordered matrix shows that minimum degree reduces the time and storage requirements by better than a factor of 2.8. The nonzero counts are 15918 and 5920, respectively.
figure() subplot(1,2,1), spy(lu(A),4), title('lu(A)') subplot(1,2,2), spy(lu(A(:,p)),4), title('lu(A(:,p))')
S — Sparse matrix
Sparse matrix. Although MATLAB® built-in functions generate valid sparse matrices, it is possible to
construct an invalid sparse matrix using the MATLAB C or Fortran APIs and pass it to
colamd. For this
colamd verifies that
S is a valid sparse
If a row index appears two or more times in the same column,
colamdignores the duplicate entries, continues processing, and provides information about the duplicate entries in
If row indices in a column are out of order,
colamdsorts each column of its internal copy of the matrix
S(but does not repair the input matrix
S), continues processing, and provides information about the out-of-order entries in
Sis invalid in any other way,
colamdcannot continue. It prints an error message, and returns no output arguments (
Complex Number Support: Yes
knobs — Row and column thresholds
[10 10 0] (default) | vector
Row and column thresholds, specified as a vector.
knobs can have
one to three elements:
Rows with more than
max(16,knobs(1)*sqrt(size(S,2)))entries are ignored.
Columns with more than
max(16,knobs(2)*sqrt(min(size(S))))entries are ordered last in the output permutation
knobs(2)are less than 0, then only completely dense rows or columns are removed, respectively.
knobs(3)is nonzero, then
p = colamd(S,[10 5])
p — Permutation vector
Permutation vector, returned as a numeric vector. For a non-symmetric matrix
S(:,p) tends to have sparser LU factors than
S. The Cholesky factorization of
also tends to be sparser than that of
The ordering is followed by a column elimination tree post-ordering.
stats — Ordering information
Ordering information, returned as a vector. The
contains information about the ordering performed and about the sparse input matrix
Number of dense or empty rows ignored by
Number of dense or empty columns ignored by
Number of garbage collections performed on the internal data
structure used by
Rightmost column index that is unsorted or contains duplicate
Last seen duplicate or out-of-order row index in the column index
Number of duplicate and out-of-order row indices
stats(4:7) are only relevant for input matrices
S that were constructed using the MATLAB C or Fortran APIs. In this case, the elements diagnose whether such a
matrix has invalid format. See the description of
S for more
 Davis, Timothy A., John R. Gilbert, Stefan I. Larimore, and Esmond G. Ng. “Algorithm 836: COLAMD, a Column Approximate Minimum Degree Ordering Algorithm.” ACM Transactions on Mathematical Software 30, no. 3 (September 2004): 377–380. https://doi.org/10.1145/1024074.1024080.
Run code in the background using MATLAB®
backgroundPool or accelerate code with Parallel Computing Toolbox™
This function fully supports thread-based environments. For more information, see Run MATLAB Functions in Thread-Based Environment.
Introduced before R2006a