CRS形式

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

 
 

以下の手順で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]), Sec.4.3.1

参考資料


トップ   編集 凍結 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS
Last-modified: 2013-06-25 (火) 19:58:01 (3127d)