colamd (MATLAB Function Reference)

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

MATLAB Function Reference

colamd

Column approximate minimum degree permutation

Syntax

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

Description

p = colamd(S) 回傳稀疏矩陣(sparse matrix) S 的 column approximate minimum degree permutation vector。對非對稱矩陣 S 來說， S(:,p) 應該會有比 S 更稀疏(sparser)的 LU 分解。 S(:,p)' * S(:,p) 的 Cholesky factorization 應該會比 S'*S 的Cholesky factorization 更為稀疏(sparser)。

knobs 是二個元素的向量。若 S 是 m x n 的矩陣，則會忽略超過 (knobs(1))*n 的橫列(row)。超過 (knobs(2))*m 的直行(column)會在排序時先被移除，最後再排在輸出結果 p 的後面。若未指定 knobs 參數，則 knobs(1) = knobs(2) = spparms('wh_frac').

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

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

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

stats(3)
在執行 colamd 時對內部資料結構所做的垃圾收集次數。（約為 2.2*nnz(S) + 4*m + 7*n 左右的整數。）

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

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

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

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

`stats(1)`	被 `colamd` 所忽略的密集(dense)或空(empty)的橫列(row)的數量。
`stats(2)`	被 `colamd` 所忽略的密集(dense)或空(empty)的直行(column)的數量。
`stats(3)`	在執行 `colamd` 時對內部資料結構所做的垃圾收集次數。（約為 `2.2nnz(S) + 4m + 7*n` 左右的整數。）
`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 來產生不合法的稀疏矩陣，並拿來當做 colamd 的引數。因此 colamd 以下列方式來判斷 S 是否合法：

若某個橫列索引值在同一直行中出現二次以上， 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 column elimination tree post-ordering.

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

See Also

colmmd, colperm, spparms, symamd, 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/

cmopts 　 colmmd