CRS形式の変更点

追加された行はこの色です。
削除された行はこの色です。
CRS形式へ行く。
CRS形式の差分を削除
#contents
*CRS形式 [#gb7a22d4]

CRS (Compressed Row Storage) 形式は、疎行列を格納する方法の一つで、
広く使われています。
例えば、以下のような複素数成分の行列があったとします。
#br
CENTER:&math(\left(\begin{array}{cccc} a & b & c & 0 \\ 0 & 0 & 0 & d \\ e & 0 & 0 & f \\ 0 & 0 & g & 0 \end{array}\right));
#br
以下の手順でCRSデータを作成します。

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

- A  = [a, b, c, d, e, f, g] ~
- I(A) = [1, 1, 1, 2, 3, 3, 4] ~
- J(A) = [1, 2, 3, 4, 1, 4, 3]

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

(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]>http://www.jicfus.jp/wiki/index.php?2%20%E5%8F%82%E8%80%83%E6%96%87%E7%8C%AE%E3%81%8A%E3%82%88%E3%81%B3%E5%8F%82%E8%80%83%E6%9B%B8%E3%81%AE%E8%A8%98%E8%BF%B0#No2]]), Sec.4.3.1




***参考資料 [#zb0918ad]

- [[疎行列 (ウィキペディア)>http://ja.wikipedia.org/wiki/%E7%96%8E%E8%A1%8C%E5%88%97]]
- [[並列数値アルゴリズム I (多田野寛人氏)>http://www.ccs.tsukuba.ac.jp/workshop/HPCseminar/2010/material/2010-04alg.pdf]] / [[CCS HPCサマーセミナー2010>http://www.ccs.tsukuba.ac.jp/workshop/HPCseminar/2010/]]
CRS形式 の変更点

CRS形式の変更点
