疎行列の格納方式メモ

プログラミング

はじめに

巨大だけどほとんどの要素がゼロであるような疎行列は、そのまま保持するより、要素がゼロじゃないところだけをうまく保持する事でメモリや計算量を減らせたりする。
扱う行列のタイプによって、効率のよい形式がいくつかあるようなので代表的なものをメモしておく。

Coodinate(COO) Format

  • 非ゼロ要素の(row indices, column indices, value)を要素数分持たせる形式
  • 非ゼロ要素が散らばっている場合に有利
0 4 0
0 2 0
0 0 1

を

row 0 1 2
column 1 1 2
value 4 2 1

のように保持する。

compressed sparse row(CSR) Format / compressed sparse column(CSC) Format

  • Coodinate Formatにおいて、左から右、上から下へ順番に要素を取っていくと、rowは同じ数字が並ぶので、これを圧縮した形式
    • rowについてソートし圧縮をするのをCSR、columnについてソートし圧縮するのがCSC
  • 圧縮の仕方としては、行iがcolのrow[i]からrow[i+1]まで、となるようにrowの要素に持たせる
  • row/columnがある程度固まっていると圧縮率が高まるため、非ゼロ要素は基本的に散らばっていて、ほどほどに固まっているような場合に有利
    • というか、だいたいの場合においてこの形式が有効
row 0 0 0 1 1 2
column 0 1 2 1 2 0

でrowを圧縮する場合は、

compressed row 0 3 5 (9)

のように持たせる。(9は実装上の都合)

ELLPack(ELL) Format

  • N*Mの行列で、各行で非ゼロ要素が一番多い行の非ゼロ要素数をmとしたとき、N*mの行列を2つ(column indices用、values用)用意する形式
    • 埋まらない場所ができるので、少し無駄があるっぽい
  • 特定のrow/columnに非ゼロ要素が固まっているような場合に有利

Diagonal(DIA) Storage Format

  • 対角方向に見て、非ゼロ要素がある対角方向のみ保持する形式
    • 対角要素に非ゼロ要素が固まって出るような場合に有効
  • N*Mの行列で、非ゼロ要素のある対角方向の数をmとすると、N*mの行列を1つ用意するだけでよい
    • これも埋まらない場所ができるので、少し無駄があるっぽい
  • 対角方向に非ゼロ要素が固まっている場合に有利

Hybrid(ELL + COO) Format

  • 基本的にELLを使って、埋まらない場所ができる場所についてのみCOOで持つような形式
  • 特定のrow/columnに非ゼロ要素が固まっている＋少し散らばっているような場合に有利

block compressed sparse row(BSR) Format

  • 行列を小さい行列のブロックに分割し、その小さい行列の開始(row,column)とその小さい行列の各要素を保持する形式
    • すべてがゼロ要素の小さい行列を持たないようにする
    • 要素がゼロの要素も保存するので、少し無駄があるっぽい
  • ちょこちょこと小さな固まりが点在する場合に有利

Skyline Storage Format

  • 三角行列や行列の三角領域を想定して、対角要素からその要素の終わり位置pointer配列とvalues用の配列2つで保持する形式らしい
  • 三角行列みたいに対角の部分から非ゼロ要素がのびているような場合に有利？

その他

  • たくさんのFormatやその派生が存在する模様
  • また、対称行列かどうかなども考慮するとよさそう

参考