Main Content

colamd

列の近似最小次数置換

説明

p = colamd(S) は、スパース行列 S について、列の近似最小次数による置換ベクトルを返します。

p = colamd(S,knobs) は、S の行と列内のエントリの最大数のしきい値を指定します。この数を超えると、行または列は無視されます。

[p,stats] = colamd(___) は、行列 S の並べ替えと妥当性に関するデータを提供する追加の出力 stats を指定します。

すべて折りたたむ

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

Figure contains 2 axes objects. axes object 1 with title A, xlabel nz = 1887 contains a line object which displays its values using only markers. axes object 2 with title A(:,p), xlabel nz = 1887 contains a line object which displays its values using only markers.

元の行列に対する 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))')

Figure contains 2 axes objects. axes object 1 with title lu(A), xlabel nz = 15918 contains a line object which displays its values using only markers. axes object 2 with title lu(A(:,p)), xlabel nz = 5920 contains a line object which displays its values using only markers.

入力引数

すべて折りたたむ

スパース行列。MATLAB® 組み込み関数は正しいスパース行列を作成しますが、MATLAB C または Fortran API を使用して作成された正しくないスパース行列が colamd に渡される可能性もあります。このことから、colamdS が正しいスパース行列であることを確認します。

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

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

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

データ型: double | logical
複素数のサポート: あり

行と列のしきい値。ベクトルとして指定します。knobs は 1 ~ 3 個の要素をもつことができます。

  • エントリ数が max(16,knobs(1)*sqrt(size(S,2))) より多い行は無視されます。

  • エントリ数が max(16,knobs(2)*sqrt(min(size(S)))) より多い列は、出力の置換 p において最後に並べ替えられます。

  • knobs(1) または knobs(2) が 0 未満の場合、それぞれ完全に密な行または列のみが取り除かれます。

  • knobs(3) が非ゼロの場合、stats および knobs が出力されます。

例: p = colamd(S,[10 5])

出力引数

すべて折りたたむ

置換ベクトル。数値ベクトルとして返されます。非対称行列 S の場合、S(:,p)S に比べ、よりスパースな LU 分解となる傾向があります。S(:,p)'*S(:,p) のコレスキー分解も S'*S のコレスキー分解に比べ、よりスパースとなる傾向があります。

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

並べ替えの情報。ベクトルとして返されます。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)

重複数と順序が違う行インデックス数

要素 stats(4:7) は、MATLAB C または Fortran API を使用して作成された入力行列 S の場合にのみ関係があります。その場合、それらの要素により、そのような行列の形式が正しくないかどうかが診断されます。詳細については、S の説明を参照してください。

参照

[1] Davis, Timothy A., John R. Gilbert, Stefan I. Larimore, and Esmond G. Ng. “Algorithm 836: COLAMD, a Column Approximate Minimum Degree Ordering Algorithm.” ACM Transactions on Mathematical Software 30, no. 3 (September 2004): 377–380. https://doi.org/10.1145/1024074.1024080.

拡張機能

バージョン履歴

R2006a より前に導入