22.1.1 疎行列の格納
厳密に言えば、スパース行列がどのように格納されるかをユーザーが理解する必要はありません。ただし、そのような理解はスパース行列のサイズを理解するのに役立ちます。独自の oct ファイルを作成したいユーザーにとっても、格納手法の理解は必要です。
疎行列データを保存する方法は多種多様です。すべての方法に共通するのは、解決する問題の特定のクラスに関する事前知識に基づいて、複雑さとストレージを削減しようとすることです。疎行列を保存するために使用できる手法の優れた要約は、Saad 8によって提供されています。完全な行列の場合、行列内の行列要素のポイントは、コンピューターのメモリ内の位置から推測できます。ただし、疎行列の場合はそうではないため、行列の非ゼロ要素の位置を均等に保存する必要があります。
これを実現する明白な方法は、行列の要素を 3 つ組として保存することです。2 つの要素は配列内の位置 (行と列) で、3 つ目の要素はデータそのものです。これは概念的には理解しやすいですが、厳密に必要な量よりも多くのストレージが必要になります。
Octave 内で使用される保存方法は、圧縮列形式です。これは Yale 形式に似ています。9 この 形式では、行内の各要素の位置とデータは、以前と同じように保存されます。ただし、同じ列のすべての要素がコンピューターのメモリに隣接して保存されると仮定すると、各列の非ゼロ要素の位置ではなく、その数に関する情報のみを保存する必要があります。したがって、行列の列数よりも多くの非ゼロ要素が行列にあると仮定すると、使用されるメモリの量に関して有利になります。
実際、列インデックスには列の数よりも 1 つ多い要素が含まれ、最初の要素は常に 0 です。この利点は、最初の列または最後の列に特別なケースがないため、コードが簡素化されることです。これを C で示す短い例を以下に示します。
for (j = 0; j < nc; j++)
for (i = cidx(j); i < cidx(j+1); i++)
printf ("nonzero element (%i,%i) is %d\n",
ridx(i), j, data(i));
上記の例が行列にどのように当てはまるかの例を考えれば、より明確な理解が得られるだろう。行列を考えてみよう。
1 2 0 0 0 0 0 3 0 0 0 4
この行列の非ゼロ要素は
(1, 1) ⇒ 1 (1, 2) ⇒ 2 (2, 4) ⇒ 3 (3, 4) ⇒ 4
これは、それぞれ列インデックス、行インデックス、データを表す 3つのベクトルcidx、ridx、dataとして保存されます。上記の行列のこれら3つのベクトルの内容は次のようになります。
cidx = [0, 1, 2, 2, 4] ridx = [0, 0, 1, 2] data = [1, 2, 3, 4]
これは、最初の行と列が 0 から始まると想定された要素の表現ですが、Octave 自体では行と列のインデックスは 1 から始まります。したがって、 i番目の列の要素数 は で与えられます 。 cidx (i + 1) - cidx (i)
Octave は圧縮された列形式を使用しますが、圧縮された行形式も同様に可能であることに注意してください。ただし、混合されたスパース行列と密行列間の混合操作のコンテキストでは、スパース行列の要素が密行列と同じ順序になっていることは理にかなっています。Octave は密行列を列優先の順序で格納するため、スパース行列もこの方法で同様に格納されます。
Octave が使用するスパース マトリックス ストレージのさらなる制約は、行内のすべての要素が行インデックスの昇順で格納されることです。これにより、特定の操作が高速化されます。ただし、スパース マトリックスの作成時に要素を並べ替える必要があります。要素が無秩序であることは、2 つのスパース マトリックスを連結するなどの操作が簡単かつ高速になるという点で潜在的に利点となりますが、他の部分では複雑さと速度の問題が生じます。
Footnotes
(8)
Y. Saad "SPARSKIT: A basic toolkit for sparse matrix computation", 1994, https://www-users.cs.umn.edu/~saad/software/SPARSKIT/paper.ps