scipyでの疎行列(sparse matrix)の扱い
scipyにはsparseという疎行列関連のモジュールがあります．
すでに公式のドキュメントが充実していますが，
自分の中の整理も兼ねて日本語でまとめたいと思います．
概要：全部で7種類の疎行列型が存在します．
- csc_matrix: Compressed Sparse Column format
- csr_matrix: Compressed Sparse Row format
- bsr_matrix: Block compressed Sparse Row format
- lil_matrix: LInked List format
- dok_matrix: Dictionary Of Keys format
- coo_matrix: COOrdinate format (aka IJV, triplet format)
- dia_matrix: DIAgonal format
それぞれについて特徴をまとめます．
csc_matrix (Compressed Sparse Column format):
長所
csc+csc, csc*csc等の演算が効率的．
column slicingが効率的(縦ベクトルが取り出しやすい)．
csc*vectorがそこそこ効率的(csr, bsrには劣る)．
短所
row slicingが非効率的(横ベクトルが取り出しにくい)．
csc式で疎行列型を構築することは非効率的(lilかdokを使うことを考えよ)．
csr_matrix (Compressed Sparse Row format):
長所
csr+csr, csr*csr等の演算が効率的．
row slicingが効率的(横ベクトルが取り出しやすい)．
csr*vectorが効率的(cscよりも速い)．
短所
column slicingが非効率的(縦ベクトルが取り出しにくい)．
csr式で疎行列型を構築することは非効率的(lilかdokを使うことを考えよ)．
bsr_matrix (Block compressed Sparse Row format):
csrと非常によく似た構造を持つ。
csrと異なるのは、bsrは行列の一部が密であるときに有効であること。
このような構造は、有限要素法のアルゴリズムで頻出し、csrやcscと比べて
さらに効率的な演算が可能である。
lil_matrix (LInked List format):
少しずつ行列を構築していく(for文などでまわしながら)ときに効率的な形式。
長所
柔軟なslicingが可能。
lil式で疎行列型を構築することは効率的。
短所
(行列同士の)加算や乗算が遅い(csrかcrcを使うことを考えよ)。
column slicingが遅い(cscを使うことを考えよ)。
想定された使用法
疎行列の構築に便利。
一度疎行列を構築したあと、より高速に演算がしたいならcsrかcscへ変換せよ。
巨大な行列を疎行列型にしたいならば、cooを使うことを考えよ。
データ構造
rowの配列(`self.rows`)であり、各々のrowは非ゼロ要素のcolumnインデックスのソート済みリストである。
非ゼロ要素の実際の値は、同様の形式で`self.data`に格納される。
dok_matrix (Dictionary Of Keys format):
少しずつ行列を構築していく(for文などでまわしながら)ときに効率的な形式。
各要素への定数時間でのアクセスが可能。
重複エントリー(i,j)は許されない。
一度dok式で疎行列の構築が済めば、coo式に効率的に変換できる。
coo_matrix (COOrdinate format (aka IJV, triplet format)):
長所
疎行列型の間での高速変換を助ける。
重複エントリー(i,j)を許す。
csr/csc式への、または、からの、非常に高速な変換。
短所
基礎演算およびslicingは直接実行できない(おそらく、内部で一度変換がおこなわれる)。
想定された使用法
疎行列の構築が高速。
一度疎行列を構築したあと、より高速に演算がしたいならcsrかcscへ変換せよ。
csrかcsc式への変換の時に重複エントリー(i,j)があれば、デフォルトでは、それらは合計される。これは有限要素の行列やそれに類するものの効率的な構築を助ける。
dia_matrix (DIAgonal format):
対角成分が順に格納されているデータから構築できる。
つまり、行列の斜め方向でデータが格納されている場合に簡単に変換できる。
まとめ
効率的に疎行列を構築するには、lil式(推奨)かdok式を使う。lil_matrixクラスは基本的なslicingといい感じのindexingをnumpyの構文と似たように実行できる。coo式はソートされていないデータ／インデックスから効率的に疎行列を構築するのに役立つ。
乗算や逆行列のような操作のためには、まずはcscかcsrのどちらかに変換せよ。
lil式はrow-basedなので、csr式への変換がより高速である。
csr, csc, coo間では、いずれも定数時間で効率的に変換ができる。
