Sparse Matrices (Mathematics)

Mathematics

置換と並べ替え

スパース行列Sの行と列の置換は、二つの方法により表現されます。

置換行列Pが、P*S のようにSの行に、または、S*P'のようにSの列に働きます。
置換ベクトルp、これは、1:nの置換を含んだフルベクトルですが、これがS(p,:)としてSの行に、または、S(p,:)として列に機能します。

例えば、ステートメント

p = [1 3 4 2 5]
I = eye(5,5);
P = I(p,:);
e = ones(4,1);
S = diag(11:11:55) + diag(e,1) + diag(e,-1)

は、つぎの結果を出力します。

p =

     1     3     4     2     5

P =

     1     0     0     0     0
     0     0     1     0     0
     0     0     0     1     0
     0     1     0     0     0
     0     0     0     0     1

S =

    11     1     0     0     0
     1    22     1     0     0
     0     1    33     1     0
     0     0     1    44     1
     0     0     0     1    55

置換ベクトルpと置換行列Pを使って、種々の置換を行なってみましょう。例えば、ステートメントS(p,:)とP*Sは、つぎの結果を出力します。

ans =

    11     1     0     0     0
     0     1    33     1     0
     0     0     1    44     1
     1    22     1     0     0
     0     0     0     1    55

同様に、S(:,p)とS*P'は、つぎの結果を出力します。

ans =

    11     0     0     1     0
     1     1     0    22     0
     0    33     1     1     0
     0     1    44     0     1
     0     0     1     0    55

Pがスパース行列ならば、二つの表現はnに比例したストレージを使い、時間的にはnnz(S)に比例して、Sのどちら側からでも適用できます。ベクトル表現は、わずかですがコンパクトで、効率的です。それで、種々のスパース行列置換ルーチンは、すべてLU(三角)分解でピポット置換(これは、MATLABの古いバージョンと一致する行列を出力)を例外として、フル行ベクトルを出力します。

2つの表現間の変換を行なうため、I = speye(n)を適切なサイズの対角が1の行列とします。そして、つぎの計算を行ないます。

P = I(p.:)
P' = I(:,p).
p = (1:n)*P'
p = (P*(1:n)')'

Pの逆は、R = P'です。pの逆をr(p) = 1:nで計算することができます。

r(p) = 1:5

r =

     1     4     2     3     5

スパース性に対する並べ替え

行列の列を並べ替えることは、LU、QR型のスパースにします。行と列の並べ替えは、Cholesky 型のスパースになります。最も簡単な並べ替えは、非ゼロのカウントにより列をソートすることです。これは、特に、行または列の非ゼロカウントの中で大きな変化があるとき、全く不規則な構造をもつ行列に対して良い並べ替えになります。

関数p = colperm(S)が、この列カウント置換を計算します。M-ファイルcolpermは、たった一つのラインからなるものです。

[ignore,p] = sort(full(sum(spones(S))));

このラインは、つぎのステップで処理します。

関数sponesは、Sの中のすべての非ゼロ要素の位置に1をもつスパース行列を作ります。
関数sumは、各々の列の中で非ゼロのカウントを含むベクトルを作成し、行列の列方向に和を計算します。
関数fullは、このベクトルをフルストレージ書式に変換します。
関数sortは、次数の高いものから低いものへと値をソートします。関数sortからの2番目の出力は、このベクトルをソートする置換を設定するものです。

バンド幅を狭くするための並べ替え

逆Cuthill-McKee順列は、プロファイラまたは行列のバンド幅を狭くしようとするものです。しかし、この結果が生じる可能性の一番高い最も小さいバンド幅であることを保証していません。しかし、通常は、最小のバンド幅になっています。関数symrcm(A)は、実際に、対称行列A + A'の非ゼロ構造に機能します。しかし、非対称行列に対しても有効です。この並びは、1次元問題やある意味で"長くて薄い"問題から生じる行列に対して有効です。"

最小次数の並び

グラフの中のノードの度合いは、隣接行列の対応する行の非ゼロ要素と同数で、このノードに接続している数です。最小次数アルゴリズムは、これらの次数がGauss消去法の中で、どのように変更されていくかをベースにした並べ替えを作成しています。列カウンタや逆Cuthill-McKeeを含んで、他のほとんどの並びよりもスパースファクタをもたらす複雑で強力なアルゴリズムです。

MATLABは、対称行列に対してsymamd と symmmd、非対称行列に対してcolamd と colmmdの2つのバージョンを用意しています。colamd と colmmd は、AA'、または、A'Aの型の対称行列に対して、機能します。

最小次数並べ替えアルゴリズムの最も時間を費やす部分は、個々のノードの度合いを保持することです。これを行う、4つの関数は、すべて、正確な度合いよりも近似的なものを使っています。結果として、

colmmd と symmmdを使って得られた因子分解は、正確な度合いを使って計算すると、より多くの非ゼロ要素をもつ傾向を示します。
colamd と symamd は、colmmd や symmmdよりも、より厳密な近似を使います。これらは、正確な度合いを使って得られるものと同等の結果を得ます。
colamd と symamd は、colmmd と symmmdより、それぞれ、速く処理します。これは、非常に大きい行列に対して、真実です。

関数spparmsを使うアルゴリズムの詳細に関連した種々のパラメータを変更することができます。

colmmd や symmmdで使われる詳細は、[5]を参照してください。colamd と symamdで使われるアルゴリズムの詳細は、[6]を参照してください。colamd と symamd で使われる近似度合いは、[1]をベースにしています。

標準数学演算因子分解