CRS形式

CRS形式 †

CRS (Compressed Row Storage) 形式は、疎行列を格納する方法の一つで、広く使われています。例えば、以下のような複素数成分の行列があったとします。

以下の手順でCRSデータを作成します。

(1) 非ゼロ要素を左から右、上から下へ書きならべ、その成分の行と列を別の配列に格納する。

(2) 配列 I(A) は同じ数字が続くので、何番目の要素から次の行が始まるかを書く。最後に、非ゼロ要素数+1 を追加する。

(3) I'(A), J(A), A の組を使って疎行列を表現する。

ここで、(2)で I'(A) に非ゼロ要素数+1を加えるのは、例えば次のようにコードを書く場合に便利なため (row_ptr = I'(A), col_ind = J(A), val = A に対応)。

　do i = 1, n
　　y(i) = 0.0d0
　　do j = row_ptr(i), row_ptr(i+1)-1
　　　y(i) = y(i) + val(j) * x(col_ind(j))
　　end do
　end do

CRSフォーマットは線形アルゴリズムの研究者の間で広く使われているため、応用数学分野の研究者との連携に便利です。少し変更すれば Matrix market フォーマットにも変換可能です。

その他の行列の格納形式については、以下を参照して下さい。

R.Barrett et al., Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods (参考文献[2]), Sec.4.3.1