MATLAB Function Reference

symmmd

Sparse symmetric minimum degree ordering

Syntax

p = symmmd(S)

Description

p = symmmd(S) 回傳 S 的 symmetric minimum degree ordering 。對一個對稱的正定(positive definite)矩陣 S 來說，回傳排列向量(permutation vector) p ，使得 S(p,p) 有比 S 更稀疏的 Cholesky factor。 symamd 函式對於對稱不定(symmetric indefinite)矩陣也可能計算出結果(works well)。

Remarks

當我們使用 \ 和 / 來對對稱性的正定稀疏線性系統(symmetric, positive definite, sparse linear systems)做計算的時候，會利用到 minimum degree ordering。

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

Algorithm

symmetric minimum degree algorithm 是根據 the column minimum degree algorithm 來產生的。事實上， symmmd(A) 只是建立一個有非零數值的結構 K ，使的 K'*K 和 A 的非零數值的結構相同，再去解 K 的 column minimum degree。

Examples

在 symrcm 網頁中有提到用 reverse Cuthill-McKee 和 minimum degree 二種方法來做 Bucky ball 範例的比較。

B = bucky+4*speye(60);
r = symrcm(B);
p = symmmd(B);
R = B(r,r);
S = B(p,p);
subplot(2,2,1), spy(R), title('B(r,r)')
subplot(2,2,2), spy(S), title('B(s,s)')
subplot(2,2,3), spy(chol(R)), title('chol(B(r,r))')
subplot(2,2,4), spy(chol(S)), title('chol(B(s,s))')

即使這個範例的運算量不大，但是和運算量很大時所得到的結果是差不多的。 RCM 會產生一個窄寬度的頻寬，而在執行 Cholesky factorization 時頻寬中幾乎都是非零結構。而 Minimum degree 在執行 factorization 產生一大塊連續的零。因此， minimum degree ordering 較省時間和儲存位元。

See Also

colamd, colmmd, colperm, symamd, symrcm

References

[1] 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.

symmlq

symrcm