NaLab03:疎行列の取り扱い

投稿者: | 2018-05-09

今日のB4計算機ゼミでは,前回の課題であった「べき乗法」の演習の報告を行った.後に,次回からは「疎行列」を取り扱うことを前提に,疎行列の格納方法を調べておく課題が出された.

疎行列・密行列

行列には格納される要素を基準にみれば「疎行列」と「密行列」に大別できる.
どのように差があるかというと,格納されている要素の非ゼロ要素の割合で組み分けするのである.
例えば,以下のようなものを見てみると,

密行列はゼロでない要素がびっしりと詰まっているが,疎行列はゼロ要素が多く詰まっている.この例だと,10×10の行列なので100個の要素があるが,密行列なら各要素にゼロ以外の要素があるので,行列の積を計算するときなどは,ちゃんと各要素に出番があるわけだ.
しかし疎行列を見ると,ゼロが非常に多い.積を計算するとなれば,計算にかかる時間や処理が無駄に多くなり,格納する際のメモリにもムダが生じることが考えられる.
そこで,疎行列を扱う際に活用する新たなフォーマットがあれば,低コストで計算ができそうな気がするのである.

疎行列格納形式

行列を格納する方法はいろいろあるが,特に以下の3つがある.

・MTX形式(COO形式)
・CRS形式(CSR形式)
・CCS形式(CSC形式)

MTX形式には,
[要素の中身,格納されている行,格納されている列]
がセットになって羅列されている形式である.
しかし,疎行列では「0」が格納されている割合が多くなるから,このフォーマットで行列を保持していても,計算にムダが生じる.
そこで他の2種類は,要素が「0」となる部分の行データや列データが圧縮されることで,メモリを節約し,計算を効率よくできるようになる.

次回のゼミまでに,このそれぞれの形式について各自調べて,どのような構造で圧縮が実現されているのかを理解しておくことを次回までの進捗となる.
それ以降は,MTXのフォーマットをCRSおよびCCSへ変換,また,CRSとCCSの間の相互変換をできる関数の実装が課題となるだろう.

コメントを残す

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