Documentation

colamd

Column approximate minimum degree permutation

所有的页面崩溃

Syntax

p = colamd(S)

Description

p = colamd(S)returns the column approximate minimum degree permutation vector for the sparse matrixS. For a non-symmetric matrixS,S(:,p)tends to have sparser LU factors thanS. The Cholesky factorization ofS(:,p)' * S(:,p)also tends to be sparser than that ofS'*S.

knobs我s a two-element vector. If S ism-by-n, then rows with more than(knobs(1))*nentries are ignored. Columns with more than(knobs(2))*mentries are removed prior to ordering, and ordered last in the output permutationp. If theknobsparameter is not present, thenknobs(1)=knobs(2) = spparms('wh_frac').

stats我s an optional vector that provides data about the ordering and the validity of the 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 bycolamd(roughly of size2.2*nnz(S) + 4*m + 7*n我ntegers)

stats(4)

0我f the matrix is valid, or1我f invalid

stats(5)

Rightmost column index that is unsorted or contains duplicate entries, or0我f no such column exists

stats(6)

最后一次看到重复或外-order row index in the column index given bystats(5), or0我f no such row index exists

stats(7)

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 tocolamd. For this reason,colamdverifies thatS我s valid:

  • If a row index appears two or more times in the same column,colamd我gnores 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).

  • IfS我s invalid in any other way,colamdcannot continue. It prints an error message, and returns no output arguments (porstats) .

The ordering is followed by a column elimination tree post-ordering.

Examples

collapse all

Open Live Script

The Harwell-Boeing collection of sparse matrices and the MATLAB® demos directory include a test matrixwest0479. 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. Thecolamdordering scrambles this structure.

loadwest0479A = 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))')

References

[1] The authors of the code forcolamdare Stefan I. Larimore and Timothy A. Davis. The algorithm was developed in collaboration with John Gilbert, Xerox PARC, and Esmond Ng, Oak Ridge National Laboratory. Sparse Matrix Algorithms Research:http://faculty.cse.tamu.edu/davis/research.html

See Also

||||

Introduced before R2006a

MATLAB Documentation
金宝app

Try MATLAB, Simulink, and Other Products

Get trial now