colamd - Column approximate minimum degree permutation - MATLAB (original) (raw)
Column approximate minimum degree permutation
Syntax
Description
[p](#mw%5F3d467fa0-475c-4849-acb4-850661a25fd5) = colamd([S](#mw%5F58c2f61d-6663-4bc4-9a4c-991353ae47c8)) returns the column approximate minimum degree permutation vector for the sparse matrixS.
[p](#mw%5F3d467fa0-475c-4849-acb4-850661a25fd5) = colamd([S](#mw%5F58c2f61d-6663-4bc4-9a4c-991353ae47c8),[knobs](#mw%5F8ccc3c66-2707-4f8a-8b8a-472cdb3318d3)) specifies thresholds for the maximum number of entries in the rows and columns ofS before a row or column is ignored.
[[p](#mw%5F3d467fa0-475c-4849-acb4-850661a25fd5),[stats](#mw%5F9abb9a8d-3d39-4860-9b16-36342ee0c3e8)] = colamd(___) specifies an additional output stats that provides data about the ordering and the validity of the matrix S.
Examples
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))')
Input Arguments
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 reason, colamd verifies that S is a valid sparse matrix:
- 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 instats(4:7). - If row indices in a column are out of order,
colamdsorts each column of its internal copy of the matrixS(but does not repair the input matrixS), continues processing, and provides information about the out-of-order entries instats(4:7). - If
Sis invalid in any other way,colamdcannot continue. It prints an error message, and returns no output arguments (porstats).
Data Types: single | double | logical
Complex Number Support: Yes
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 permutationp. - If
knobs(1)orknobs(2)are less than 0, then only completely dense rows or columns are removed, respectively. - If
knobs(3)is nonzero, thenstatsandknobsare printed.
Example: p = colamd(S,[10 5])
Output Arguments
Permutation vector, returned as a numeric vector. For a non-symmetric matrixS, S(:,p) tends to have sparser LU factors thanS. The Cholesky factorization of S(:,p)'*S(:,p) also tends to be sparser than that of S'*S.
The ordering is followed by a column elimination tree post-ordering.
Ordering information, returned as a vector. The stats vector contains information about the ordering performed and about the sparse input matrixS:
| stats(1) | Number of dense or empty rows ignored bycolamd |
|---|---|
| stats(2) | Number of dense or empty columns ignored bycolamd |
| stats(3) | Number of garbage collections performed on the internal data structure used by colamd (roughly of size2.2*nnz(S) + 4*m + 7*n integers) |
| stats(4) | 0 if the matrix is valid, or 1 if invalid |
| stats(5) | Rightmost column index that is unsorted or contains duplicate entries, or 0 if no such column exists |
| stats(6) | 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 |
| stats(7) | Number of duplicate and out-of-order row indices |
The elements stats(4:7) are only relevant for input matricesS 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 information.
References
[1] 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.
Extended Capabilities
Version History
Introduced before R2006a
You can specify the sparse matrix input argument S as single precision. The function still returns output arguments related to indexing, such as ordering and permutation vectors, as type double.