スパースストレージ形式#
スパース行列にはさまざまな行列保存形式があります。インテル® oneMKL スパース BLAS ライブラリーは、次のスパース行列形式をサポートしています。
oneMKL スパース BLAS でサポートされるスパース行列形式 |
|---|
圧縮スパース行 (CSR)#
最も一般的なスパース形式の 1 つは、スカラーサイズ (nrows、ncols) と 3 つのデータ配列で表される CSR (3 配列 CSR または CSR3 と呼ばれることもあります) 形式です。row_ptr、col_ind、values および index_base パラメーター。この形式の一部のバージョンでは、ゼロ以外の要素の数 (nnz) も明示的に格納されますが、これは row_ptr の説明で後述するように row_ptr 配列から抽出できるため、ここでは含めません。
CSR 行列形式の要素 |
説明 |
|---|---|
|
スパース行列の行数 |
|
スパース行列の列数。 |
|
行列のインデックスが 0 から始まるか 1 から始まるかを指定するパラメーター。 |
|
スパース行列のゼロ以外の要素を行ごとに格納した配列。 |
|
|
|
|
CSR 形式の例#
次に、低レベルのインターフェイスの使用例を 3 つ示します。
CSR ケース 1: ゼロベースのインデックスを持つソートされた正方行列#
ゼロベースのインデックスと実数正方行列を想定します。
nrows |
3 |
||||
ncols |
3 |
||||
index |
0 |
||||
row_ptr |
0 |
2 |
4 |
5 |
|
col_ind |
0 |
2 |
1 |
2 |
0 |
values |
1.0 |
2.0 |
-1.0 |
4.0 |
3.0 |
CSR ケース 2: 1 から始まるインデックスと空の行を持つソートされた長方形行列#
1 から始まるインデックスと、空の行を持つ実数長方形行列を想定します。
nrows |
4 |
||||||
ncols |
5 |
||||||
index |
1 |
||||||
row_ptr |
1 |
3 |
6 |
6 |
8 |
||
col_ind |
1 |
3 |
2 |
3 |
5 |
1 |
4 |
values |
1.0 |
2.0 |
-1.0 |
4.0 |
1.0 |
3.0 |
1.0 |
CSR ケース 3: ゼロベースのインデックスを持つソートされていない長方形行列#
ソートされていない CSR の例: ゼロベースのインデックスと実長方形行列を想定すると、CSR 形式では列インデックスを特定の行内でソートする必要はありませんが、values と col_ind 配列は互いに一貫している必要があります。sorted プロパティーは必須ではありませんが、より優れたアルゴリズムとデータの局所性を有効にするため、実行時にパフォーマンスが向上する可能性があります。適用可能な場合に sorted プロパティーを設定する方法、または必要に応じてそれを実現するために行列を並べ替える方法の詳細は、sparse::set_matrix_property() および sparse::sort_matrix を参照してください。
nrows |
4 |
|||||||||
ncols |
5 |
|||||||||
index |
0 |
|||||||||
row_ptr |
0 |
2 |
5 |
9 |
10 |
|||||
col_ind |
0 |
2 |
4 |
1 |
2 |
1 |
2 |
0 |
3 |
0 |
values |
1.0 |
2.0 |
1.0 |
-1.0 |
4.0 |
2.0 |
3.0 |
1.0 |
4.0 |
3.0 |
座標 (COO) 形式#
最も単純なスパース行列形式は COO 形式で、スカラーサイズ (nrows、ncols、nnz) と 3 つのデータ配列で表されます: row_ind、col_ind、values、および index パラメーター。各タプル (row_ind[i], col_ind[i], values[i])) は、スパース行列内のゼロ以外の値を表します。
COO 行列形式の要素 |
説明 |
|---|---|
|
スパース行列の行数 |
|
スパース行列の列数。 |
|
スパース行列の非ゼロの数。 |
|
行列のインデックスが 0 から始まるか 1 から始まるかを指定するパラメーター。 |
|
|
|
|
|
スパース行列のゼロ以外の要素を含む配列。ソートされた順序で格納されることが望まれますが、必ずしもそうである必要はありません。 |
COO 形式の例#
次の例は、スパース COO 形式の使用方法を示しています。
COO ケース 1: 1 から始まるインデックスを持つソートされた長方形行列#
以下に、行ごとにソートし、次に行内の列ごとにソートした、1 から始まるインデックスの長方形 COO 行列の例を示します。
nrows |
4 |
||||||
ncols |
5 |
||||||
nnz |
7 |
||||||
index |
1 |
||||||
row_ind |
1 |
1 |
2 |
2 |
2 |
4 |
4 |
col_ind |
1 |
3 |
2 |
3 |
5 |
1 |
4 |
values |
1.0 |
2.0 |
-1.0 |
4.0 |
1.0 |
3.0 |
1.0 |
COO ケース 2: ゼロベースのインデックスを持つソートされていない長方形行列#
COO 形式では、スパース行列内のゼロ以外の各要素を表すすべての i について (row_ind[i], col_ind[i], val[i]) がソートなしの順序でグループ化されている限り、ソートされた配列は必要ありません。sorted プロパティーは必須ではありませんが、より優れたアルゴリズムとデータの局所性を有効にするため、実行時にパフォーマンスが向上する可能性があります。
ゼロベースのインデックスによるソートされていない COO 行列と実長方形行列の例を以下に示します。
nrows |
4 |
|||||||||
ncols |
5 |
|||||||||
index |
0 |
|||||||||
row_ind |
2 |
1 |
0 |
1 |
2 |
3 |
0 |
1 |
2 |
2 |
col_ind |
1 |
4 |
2 |
1 |
0 |
0 |
0 |
2 |
3 |
2 |
values |
2.0 |
1.0 |
2.0 |
-1.0 |
1.0 |
3.0 |
1.0 |
4.0 |
4.0 |
3.0 |