22.1.4.3 Mathematical Considerations

22.1.4.3 数学的な考慮事項

スパース行列を、完全な行列とまったく同じように動作させる試みがなされました。ただし、特定の違いがあり、特に他の製品のスパース実装との違いがあります。

まず、演算子"./"と".^"演算子は注意して使用する必要があります。例で何が起こっているか考えてみましょう。

 s = speye (4);
 a1 = s .^ 2;
 a2 = s .^ s;
 a3 = s .^ -2;
 a4 = s ./ 2;
 a5 = 2 ./ s;
 a6 = s ./ s;

となります。sを 2 乗する最初の例では、問題は発生しません。ただし、 sを要素ごとにそれ自身に乗じると、多数の項が含まれ、0 .^ 0その数は 1 になります。完全な行列があります。 s .^ s

同様に、は無限大であるs .^ -2のような項が含まれており0 .^ -2、はs .^ -2完全な行列でもある。

「./」演算子にはs ./ 2問題はありませんが、多数の無限項も含まれており、同様に完全な行列です。の場合、のような項が含まれており、これはであり、したがって、これはsのゼロ要素が値で埋められた完全な行列です。 2 ./ ss ./ s0 ./ 0NaNNaN

上記の動作は完全な行列と一致していますが、他の製品のスパース実装とは一致していません。

疎行列の特定の問題は、ゼロが格納されていないため、これらのゼロの符号ビットも同様に格納されていないという事実によって発生します。場合によっては、ゼロの符号ビットが重要です。例:

a = 0 ./ [-1, 1; 1, -1];
b = 1 ./ a
⇒ -Inf            Inf
    Inf           -Inf
c = 1 ./ sparse (a)
⇒  Inf            Inf
    Inf            Inf

この動作を修正するには、負の符号ビットを持つゼロ要素を行列に格納して、その符号ビットが尊重されるようにする必要があります。現時点では、効率上の理由から、これは実行されません。そのため、ゼロの符号ビットが重要な計算は、スパース行列を使用して実行してはならないことがユーザーに警告されます。

一般に、疎行列で使用される関数または演算子は、元の行列と同じかそれより多い数の非ゼロ要素を持つ疎行列になります。これは、疎行列の因数分解の重要なケースに特に当てはまります。これに対処する通常の方法は、行列の因数分解が元の行列の因数分解よりも疎になるように行列を並べ替えることです。つまり、の因数分解は、同等の因数分解よりもL * U = P * S * Q疎な項とを持ちます。 LUL * U = S

因数分解する行列の種類に応じて、並べ替えに使用できる関数がいくつかあります。行列が対称正定値の場合は、symamdまたはcsymamdを使用する必要があります。それ以外の場合は、 amd、colamdまたはccolamd を使用する必要があります。完全性のために、並べ替え関数colpermとrandpermも使用できます。

単純な正定値行列の構造の例については、図22.3を参照してください。

Figure 22.3: 単純なスパース行列の構造

この行列の標準的なコレスキー分解は、完全な行列に使用するのと同じコマンドで取得できます。これは、コマンドを使用して視覚化できます r = chol (A); spy (r);。図 22.4 を参照してください。元の行列には 598 個の非ゼロ項がありましたが、このコレスキー分解には 10200 個の非ゼロ項があり、対称行列の半分だけが格納されています。これは、重要なレベルの埋め込みであり、このような小さなテストケースでは問題になりませんが、他のスパース行列を操作する場合は大きなオーバーヘッドになる可能性があります。

元の行列の適切なスパース性保存順列はsymamdによって与えられ、この並べ替えを使用した因数分解はコマンドを使用して視覚化できますq = symamd (A); r = chol (A(q,q)); spy (r)。これにより、399 個の非ゼロ項が得られ、これは大幅な改善です。

コレスキー分解自体は、分解中に行列の適切なスパース性保存並べ替えを決定するために使用できます。その場合、これは 3 つの戻り引数として取得される可能性があります[r, p, q] = chol (A); spy (r)。

Figure 22.4: 上記の行列の置換されていないコレスキー分解の構造

Figure 22.5: 上記の行列の並べ替えられたコレスキー分解の構造

非対称行列の場合、適切なスパース性保存順列はcolamdであり、この並べ替えを使用した因数分解はコマンドを使用して視覚化できます q = colamd (A); [l, u, p] = lu (A(:,q)); spy (l+u)。

最後に、Octave は div (/) および ldiv (\) 演算子を使用するときに暗黙的に行列を並べ替えるため、パフォーマンスを最大化するためにユーザーが行列を明示的に並べ替える必要はありません。

: p = amd (S)

: p = amd (S, opts)

行列のおおよその最小次数順列を返します。

これは、のコレスキー分解がS自体のコレスキー分解よりもスパースになる傾向があるような順列です。は通常、よりも高速ですが、同様の目的を果たします。 S (p, p)amdsymamd

オプションパラメータoptsは、の動作を制御する構造体ですamd。構造体のフィールドは次のとおりです。

　opts.dense
　amd入力行列の密な行または列と見なすものを決定します。n は行列Sの次数ですが、エントリ数を超える行または列は、順列の計算中に無視されます。dense の値は正のスカラーでなければならず、デフォルト値は 10.0 です。 max (16, (dense * sqrt (n)))amd

　opts.aggressive
　この値がゼロ以外のスカラーの場合、amd積極的な吸収を実行します。デフォルトでは、積極的な吸収は実行されません。

コード自体の作者は Timothy A. Davis です ( http://faculty.cse.tamu.edu/davis/suitesparse.htmlを参照)。

22.1.4.3 Mathematical Considerations

22.1.4.3 数学的な考慮事項

WikiWikiについて

マニュアル

開発環境

リポジトリ掲示版

公式サイト