このページの翻訳は最新ではありません。ここをクリックして、英語の最新版を参照してください。

colamd

列の近似最小次数置換

構文

p = colamd(S)


説明

p = colamd(S) は、スパース行列 S について、列の近似最小次数による置換ベクトルを返します。非対称行列 S の場合、S(:,p) は S に比べ、よりスパースな LU 分解となる傾向があります。S(:,p)' * S(:,p) のコレスキー分解も S'*S のコレスキー分解に比べ、よりスパースとなる傾向があります。

knobs は 2 要素のベクトルです。S が m 行 n 列の場合、要素数が (knobs(1))*n より多い行は無視されます。要素数が (knobs(2))*m より多い列は、並べ替えの前に取り除かれ、出力の置換 p において最後に並べ替えられます。knobs パラメーターが存在しない場合には、knobs(1) = knobs(2) = spparms('wh_frac') となります。

stats はオプションのベクトルで、行列 S の並びと妥当性に関するデータを提供します。

stats(1)	colamd で無視される密または空の行の数
stats(2)	colamd で無視される密または空の列の数
stats(3)	colamd が使用する内部データ構造で実行されるガベージ コレクションの回数 (およそ 2.2*nnz(S) + 4*m + 7*n 整数のサイズ)
stats(4)	行列が正しい場合は 0、正しくない場合は 1
stats(5)	並べ替えされていないものや重複したエントリをもつ右側の列インデックスまたは、対象となる列が存在しない場合は 0
stats(6)	stats(5) で与えられる列インデックスと行インデックスの順序の違いや重複、または対象となる列が存在しない場合は、0
stats(7)	重複数と順序が違う行インデックス数

MATLAB^® の組み込み関数は、有効なスパース行列を作成しますが、ユーザーが MATLAB の C または Fortran API を使用して無効なスパース行列を作成し、colamd に渡すことも考えられます。このことから、colamd は S が正しいことを確認します。

• 行インデックスが、同じ列に複数回現れる場合、colamd は重複しているエントリを無視し、処理を続け、重複エントリに関する情報を stats(4:7) に出力します。

• 列の行インデックスの順序が異なる場合、colamd は、行列 S の内部コピーの各列を並べ替えし (入力行列 S は修正しません)、処理を続け、stats(4:7) に、範囲外のエントリの情報を与えます。

• S が、他の方法を使用して正しく設定できない場合、colamd は処理を続行できません。エラー メッセージを表示して、出力引数 (p または stats) を戻しません。

順序は、列の消去木の帰りがけ順に従います。

例

スパース行列と LU 分解の比較

Harwell-Boeing が所有するスパース行列のコレクションから MATLAB® のデモ ディレクトリに用意されているものとして、テスト行列 west0479 があります。これは、Westerberg に基づく 8 ステージの化学蒸留塔のモデルから導出された 479 次の行列です。spy プロットは、8 ステージである証拠を示しています。colamd による並べ替えは、この構造を攪乱させることになります。

load west0479
A = 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)')

元の行列に対する LU 分解の spy プロットを並べ替え後の行列に対する LU 分解の spy プロットと比較すると、最小次数が、時間と保存の必要条件を 2.8 倍以上も低減させていることがわかります。非ゼロ要素の個数は、それぞれ 15918 個と 5920 個です。

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

参照

[1] The authors of the code for colamd are 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

参考

colperm | dissect | spparms | symamd | symrcm

R2006a より前に導入

×

例を開く

この例の変更されたバージョンがあります。編集された方の例を開きますか?

いいえ、変更されたバージョンを上書きします。 はい