symamd

対称な近似最小次数置換

ページ内をすべて折りたたむ

構文

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

説明

p = symamd(S) は、対称正定値行列 S に対して S(p,p) が S よりもスパースなコレスキー因子をもつような置換ベクトル p を返します。S の並びを算出するために、symamd は spones(M'*M) = spones (S) を満たす行列 M を作成し、p = colamd(M) を計算します。関数 symamd は、対称不定値行列にも対応しています。

S は、正方行列でなければなりません。厳密な意味で下三角部のみが参照されます。

p = symamd(S,knobs) の knobs はスカラー値です。S が n 行 n 列の場合、knobs*n より大きい行と列のエントリは、並べ替える前に除去され、出力の置換行列 p の後に並べられます。knobs パラメーターが存在しない場合には、knobs = spparms('wh_frac') となります。

[p,stats] = symamd(...) はオプションのベクトル stats を出力し、行列 S の並びと妥当性に関するデータを提供します。

stats(1)

symamd で無視される密または空の行の数

stats(2)

symamd で無視される密または空の列の数

stats(3)

symamd が使用する内部データ構造で実行されるガベージ コレクションの回数 (およそ 8.4*nnz(tril(S,-1)) + 9n 整数のサイズ)

stats(4)

行列が正しい場合は 0、正しくない場合は 1

stats(5)

並べ替えされていないものや重複したエントリをもつ右側の列インデックスまたは、対象となる列が存在しない場合は 0

stats(6)

stats(5) で与えられる列インデックスと行インデックスの順序の違いや重複、または対象となる列が存在しない場合は、0

stats(7)

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

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

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

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

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

並びは、対称消去ツリー ポストの並びに従います。

例

すべて折りたたむ

ライブ スクリプトを開く

ここでは、symrcm のリファレンス ページで説明されているバッキー ボールの例で逆 Cuthill-McKee と最小度合いを比較します。

B = bucky+4*speye(60);
r = symrcm(B);
p = symamd(B);
R = B(r,r);
S = B(p,p);
subplot(2,2,1), spy(R,4), title('B(r,r)')
subplot(2,2,2), spy(S,4), title('B(s,s)')
subplot(2,2,3), spy(chol(R),4), title('chol(B(r,r))')
subplot(2,2,4), spy(chol(S),4), title('chol(B(s,s))')

Figure contains 4 axes objects. Axes object 1 with title B(r,r), xlabel nz = 240 contains a line object which displays its values using only markers. Axes object 2 with title B(s,s), xlabel nz = 240 contains a line object which displays its values using only markers. Axes object 3 with title chol(B(r,r)), xlabel nz = 514 contains a line object which displays its values using only markers. Axes object 4 with title chol(B(s,s)), xlabel nz = 348 contains a line object which displays its values using only markers.

このような小さな問題でも、両方の並べ替えの動作が明らかです。RCM は、コレスキー分解の際、バンド幅が狭い行列を作成します。分解の際、最小度合いは大規模で連続したゼロのブロックをもつ構造体を作成します。その結果、最小度合い並べ替えは、分解の計算時間とメモリ容量を小さくできます。

参照

[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 より前に導入

参考

| | | | |