Oracle® Developer Studio 12.5: パフォーマンスライブラリユーザーズガイド

印刷ビューの終了

更新: 2016 年 6 月
 
 

スパース行列

スパース行列は、通常、必要な格納領域を最小限に抑える形式で表されます。疎であることの利点を活かし、ゼロを格納しないことによって、かなりの格納領域を節約できます。SPSOLVE および SuperLU で使用される格納形式は圧縮スパース列 (CSC) 形式で、これは Harwell-Boeing 形式とも呼ばれます。

CSC 形式では、スパース行列を 2 つの整数配列と 1 つの浮動小数点配列で表します。整数配列 (colptr と rowind) はスパース行列の非ゼロの位置を指定し、浮動小数点配列 (values) は非ゼロ値に使用されます。

列ポインタ (colptr) 配列は n+1 個の要素で構成されています。colptr(i) は i 番目の列の先頭を指し、colptr(i+1)-1 は i 番目の列の末尾を指します。行インデックス (rowind) 配列には非ゼロ値の行インデックスが格納されます。values 配列には、対応する非ゼロの数値が格納されます。

neqns 個の方程式と nnz 個の非ゼロ要素から成るスパース行列には次の行列データ形式が存在します。

  • 対称

  • 構造的対称

  • 非対称

現在、SuperLU は非対称行列のみをサポートしています。多くの場合、もっとも効率的なデータ表現は具体的な問題によって異なります。以降のセクションでは、スパース行列データ形式の例を示します。

対称スパース行列

対称スパース行列は、すべての i および j について a(i, j) = a(j, i) である行列です。この対称性のため、ソルバールーチンに渡す必要があるのは下側の三角形の値のみです。上側の三角形は下側の三角形から判断できます。

対称行列の例を次に示します。この例の出典は、A. George および J. W-H. Liu 著、『Computer Solution of Large Sparse Positive Definite Systems』です。

image:対称行列

A を CSC 形式で表すには、次のようにします。

  • colptr: 1, 6, 7, 8, 9, 10

  • rowind: 1, 2, 3, 4, 5, 2, 3, 4, 5

  • values: 4.0, 1.0, 2.0, 0.5, 2.0, 0.5, 3.0, 0.625, 16.0

構造的対称スパース行列

構造的対称スパース行列では、その非ゼロ値が、すべての i および j について、a(i, j) ≠ 0 であれば a(j, i) ≠ 0 であるという性質を持ちます。構造的対称行列の連立方程式を解く場合は、行列全体をソルバールーチンに渡す必要があります。

構造的対称行列の例を次に示します。

image:構造的対称行列

A を CSC 形式で表すには、次のようにします。

  • colptr: 1, 3, 6, 7, 9

  • rowind: 1, 2, 1, 2, 4, 3, 2, 4

  • values: 1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0

非対称スパース行列

非対称スパース行列では、すべての i および j について a(i, j) = a(j, i) となるわけではありません。行列の構造には明白なパターンがありません。非対称行列の連立方程式を解く場合は、行列全体をソルバールーチンに渡す必要があります。非対称行列の例を次に示します。

image:非対称行列

A を CSC 形式で表すには、次のようにします。

  • 1 オリジンのインデックス:

    • colptr: 1, 6, 7, 8, 9, 11

    • rowind: 1, 2, 3, 4, 5, 2, 3, 4, 2, 5

    • values: 1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0, 9.0, 10.0

  • 0 オリジンのインデックス:

    • colptr: 0, 5, 6, 7, 8, 10

    • rowind: 0, 1, 2, 3, 4, 1, 2, 3, 1, 4

    • values: 1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0, 9.0, 10.0