Documentation |
Column approximate minimum degree permutation
p = colamd(S)
p = colamd(S) returns the column approximate minimum degree permutation vector for the sparse matrix S. For a non-symmetric matrix S, S(:,p) tends to have sparser LU factors than S. The Cholesky factorization of S(:,p)' * S(:,p) also tends to be sparser than that of S'*S.
knobs is a two-element vector. If S is m-by-n, then rows with more than (knobs(1))*n entries are ignored. Columns with more than (knobs(2))*m entries are removed prior to ordering, and ordered last in the output permutation p. If the knobs parameter is not present, then knobs(1) = knobs(2) = spparms('wh_frac').
stats is an optional vector that provides data about the ordering and the validity of the matrix S.
Number of dense or empty rows ignored by colamd | |
Number of dense or empty columns ignored by colamd | |
Number of garbage collections performed on the internal data structure used by colamd (roughly of size 2.2*nnz(S) + 4*m + 7*n integers) | |
0 if the matrix is valid, or 1 if invalid | |
Rightmost column index that is unsorted or contains duplicate entries, or 0 if no such column exists | |
Last seen duplicate or out-of-order row index in the column index given by stats(5), or 0 if no such row index exists | |
Number of duplicate and out-of-order row indices |
Although MATLAB^{®} built-in functions generate valid sparse matrices, a user may construct an invalid sparse matrix using the MATLAB C or Fortran APIs and pass it to colamd. For this reason, colamd verifies that S is valid:
If a row index appears two or more times in the same column, colamd ignores the duplicate entries, continues processing, and provides information about the duplicate entries in stats(4:7).
If row indices in a column are out of order, colamd sorts 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 stats(4:7).
If S is invalid in any other way, colamd cannot continue. It prints an error message, and returns no output arguments (p or stats) .
The ordering is followed by a column elimination tree post-ordering.
[1] The authors of the code for "colamd" are Stefan I. Larimore and Timothy A. Davis (davis@cise.ufl.edu), University of Florida. The algorithm was developed in collaboration with John Gilbert, Xerox PARC, and Esmond Ng, Oak Ridge National Laboratory. Sparse Matrix Algorithms Research at the University of Florida: http://www.cise.ufl.edu/research/sparse/