symamd (MATLAB Function Reference)

(translator=pacific, ChineseSource=pacific-20020703-8\symamd.html, EnglishSource=c:\matlabr12\help\techdoc\ref\symamd.html)

MATLAB Function Reference

symamd

Symmetric approximate minimum degree permutation

Syntax

p = symamd(S)
p = symamd(S,knobs)
[p,stats] = symamd(S)
[p,stats] = symamd(S,knobs)

Description

p = symamd(S) 對一個對稱的正定(positive definite)矩陣 S 來說，回傳排列向量(permutation vector) p ，使得 S(p,p) 有比 S 更稀疏的 Cholesky factor。為了要找到 S 的排列順序， symamd 先產生一個使得 spones(M'*M) = spones (S)的矩陣 M，再去計算 p = colamd(M)。 symamd 函式對於對稱不定(symmetric indefinite)矩陣也有可能計算出結果(works well)。

S 一定是平方矩陣，而且只有矩陣的三角形下半部部分(lower triangular part)會對計算結果產生影響。

knobs 是一個數。若 S 是 n x n 的矩陣，超過 knobs*n 的橫列和直行會在排序時先被移除，最後再排在輸出結果 p 的後面。I若未指定 knobs 參數，則 knobs = spparms('wh_frac').

stats 是在使用 symamd 指令對矩陣 S 做運算時的相關性質。以選擇性引數向量(optional vector)來表示。

stats(1)
被 symamd 所忽略的密集(dense)或空(empty)的橫列(row)的數量。

stats(2)
被 symamd 所忽略的密集(dense)或空(empty)的直行(column)的數量。

stats(3)
在執行 symamd 時對內部資料結構所做的垃圾收集次數。（約為8.4*nnz(tril(S,-1)) + 9n 左右的整數。）

stats(4)
若矩陣合法，則回傳 0 ，不合法則回傳 1。

stats(5)
未排序或包括重覆entry(duplicate entries)的直行中，最右邊那個直行的索引值，若沒有此行則回傳 0 。

stats(6)
在 stats(5) 的直行中，最下面一個重覆或不照順序排列的橫列索引值，若沒有則回傳 0 。

stats(7)
包含重覆entry(duplicate entries)和未排序的橫列的數量。

`stats(1)`	被 `symamd` 所忽略的密集(dense)或空(empty)的橫列(row)的數量。
`stats(2)`	被 `symamd` 所忽略的密集(dense)或空(empty)的直行(column)的數量。
`stats(3)`	在執行 `symamd` 時對內部資料結構所做的垃圾收集次數。（約為`8.4*nnz(tril(S,-1)) + 9n` 左右的整數。）
`stats(4)`	若矩陣合法，則回傳 `0` ，不合法則回傳 `1`。
`stats(5)`	未排序或包括重覆entry(duplicate entries)的直行中，最右邊那個直行的索引值，若沒有此行則回傳 `0` 。
`stats(6)`	在 `stats(5)` 的直行中，最下面一個重覆或不照順序排列的橫列索引值，若沒有則回傳 `0` 。
`stats(7)`	包含重覆entry(duplicate entries)和未排序的橫列的數量。

雖然 MATLAB 有內建函式來產生合法的稀疏矩陣，但使用者可能會使用 MATLAB C 或 Fortran APIs 來產生不合法的稀疏矩陣，並拿來當做 symamd 的引數。因此 colamd 以下列方式來判斷 S 是否合法：

I若某個橫列索引值在同一直行中出現二次以上， colamd 會忽略掉重覆的entry(duplicate entries)並繼續執行，且在 stats(4:7)中顯示有關重覆的entry(duplicate entries)的訊息。
若在某個直行中，橫列沒有依照順序排列， colamd 會先複製矩陣 S ，再將此複製直行的橫列索引值加以排序（也就是說，不會修改原來的矩陣 S），然後繼續執行，且在 stats(4:7)中顯示有關未依順序排列的訊息。(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).)
若 S 非上述二種情形且不合法， colamd 無法繼續執行下去。程式會顯示錯誤訊息，而不會回傳值給輸出引數（p 和 stats）。

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

Note symamd 的執行速度會比 symmmd 還快，並回傳較佳的排序。

See Also

colamd, colmmd, colperm, spparms, symmmd, symrcm

References

colamd 的指令原始碼為佛羅里達大學的Stefan I. Larimore 和 Timothy A. Davis (davis@cise.ufl.edu)所寫。這個演算法是 John Gilbert, Xerox PARC, 和 Esmond Ng, Oak Ridge National Laboratory共同合作產生的。佛羅里達大學的稀疏矩陣研究： http://www.cise.ufl.edu/research/sparse/。(The authors of the code for symamd 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/)

switch 　 symbfact