MATLAB Function Reference

colmmd

Sparse column minimum degree permutation

Syntax

p = colmmd(S)

Description

p = colmmd(S) 回傳矩陣 S 的 column minimum degree permutation vector。對非對稱的稀疏矩陣 S 來說，所得到的 p 可使的 S(:,p) 應該會有比 S 更稀疏(sparser)的 LU factor。

當我們使用 \ 和 / 來對非對稱性或對稱性的無限稀疏線性系統(nonsymmetric and symmetric indefinite sparse linear systems)做計算的時候，會用到 colmmd 的排列法則。

利用 spparms 函式可改變此演算法的選項和參數。

Algorithm

對稱性矩陣的 minimum degree algorithm 在George 和 Liu 所寫的paper[1]中有所描述。非對稱性矩陣的 minimum degree algorithm 則在  Gilbert, Moler, 和 Schreiber 的paper[2]中有所描述。和 A'*A 的 symmetric minimum degree 相似，但不會真正形成 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.

Examples

 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 colmmd ordering scrambles this structure.

load west0479
A = west0479;
p = colmmd(A);
spy(A)
spy(A(:,p))

比較原來矩陣和重新排列過的矩陣的LU factorization的 spy 繪圖之後，可知 minimum degree 可減少超過 2.8 倍的計算時間和儲存位元。非零的數分別為16777和5904。

spy(lu(A))
spy(lu(A(:,p)))

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