NaLab:04 疎行列格納形式と利用

投稿者: | 2018-05-14

前回のゼミでは,疎行列格納形式のCRS・CCS形式を簡単に紹介した.今回はその若干の復習と,実際にその形式を利用した確認方法を実施することが課題として挙げられた.

疎行列格納形式

 疎行列はゼロ要素割合が非常に多いため,領域を行列要素数分丸々確保してしまうと,メモリ領域やゼロを掛ける積算の部分でムダが生じる.これを回避してより高速な計算を実現するために,疎行列格納形式が存在する.

COO形式

COO形式は,データセットが

[総行数][総列数][非ゼロ要素数]
[1つめの要素のある行番号][1つめの要素のある列番号][そこに格納されている要素の値]
[2つめの要素のある行番号][2つめの要素のある列番号][そこに格納されている要素の値]

という形で,行・列・要素が順番に格納されてdatファイルとして構成されている,MTX形式とも言われる格納形式.
しかし,ある行において連続して値が格納されているとすると,

2行目がたくさんある場合…
2 3 0.5
2 5 0.8
2 6 0.11
2 9 0.4

となって,これが続けば,行情報をストアしてる配列要素はムダに長くなってもったいない.列が連続する場合も同様.

CRS形式

CRS形式では,上記のような連続するについてを圧縮して保存する形式である.圧縮方法としては,2行目がたくさんあり,それが10個あるとすると,この「10個あるよ!」という「10」という値を記憶しておく.
詳しい方法は調べよう.

CCS形式

CCS形式は,CRS形式が行方向圧縮であることに対し,について圧縮して保存する形式である.これも詳しい方法は調べよう.

課題

とりあえずMatrix MarketよりダウンロードしたMTX形式の疎行列データを利用し,それをCRS形式に変換・そこからさらにCCS形式に変換し,CRS・CCSの両形式を同時に保持できるようにすることと,それを使って行列ベクトル積を実行し,答えが合えば,行列の変換がうまくいっているということになる.水曜までの完成は厳しいと思うが,頑張ってほしい….

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です