ドキュメンテーション

最新のリリースでは、このページがまだ翻訳されていません。 このページの最新版は英語でご覧になれます。

colamd

列の近似最小次数置換

構文

p = colamd(S)

説明

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

knobs は 2 要素のベクトルです。S が mn 列の場合、要素数が (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 に渡すことも考えられます。このことから、colamdS が正しいことを確認します。

  • 同じ行インデックスが同じ列の中に複数回現れる場合、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 (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/

この情報は役に立ちましたか?