-Python- 疎行列

数値計算では,ほとんどの要素が零であるような行列(疎行列)を扱うことが多々あります.疎行列は通常の2次元配列を使って扱うとメモリ使用量の面でも,計算量の面でも効率が悪いことから,Scipyには疎行列型専用のデータ型が用意されています.
疎行列に対して,通常の行列を密行列と呼ぶこともあります.疎行列と密行列は数学のレベルでは同じものですが,計算機で計算するときには状況に応じて疎行列専用のデータ型式を使うと便利なことがあります.

以下に,疎行列の操作例を示します.

>>> from scipy import sparse
>>> a = sparse.lil_matrix*1
>>> a[0, 1] = 1
>>> a[0, 3] = 2
>>> a[2, 3] = 3
>>> a[3, 4] = 4
>>> a.toarray()
array([[0., 1., 0., 2., 0.],
       [0., 0., 0., 0., 0.],
       [0., 0., 0., 3., 0.],
       [0., 0., 0., 0., 4.]])
>>> b = sparse.lil_matrix*2
>>> b[0, 2] = 1
>>> b[1, 2] = 2
>>> b[2, 3] = 3
>>> b[3, 3] = 4
>>> b.toarray()
array([[0., 0., 1., 0.],
       [0., 0., 2., 0.],
       [0., 0., 0., 3.],
       [0., 0., 0., 4.],
       [0., 0., 0., 0.]])
>>> c = a.dot(b)
>>> c.toarray()
array([[ 0.,  0.,  2.,  8.],
       [ 0.,  0.,  0.,  0.],
       [ 0.,  0.,  0., 12.],
       [ 0.,  0.,  0.,  0.]])
>>> a1 = a.tocsr()
>>> b1 = b.tocsr()
>>> c1 = a1.dot(b1)
>>> c1.toarray()
array([[ 0.,  0.,  2.,  8.],
       [ 0.,  0.,  0.,  0.],
       [ 0.,  0.,  0., 12.],
       [ 0.,  0.,  0.,  0.]])
>>> a2 = a.tocsc()
>>> b2 = b.tocsc()
>>> c2 = a2.dot(b2)
>>> c2.toarray()
array([[ 0.,  0.,  2.,  8.],
       [ 0.,  0.,  0.,  0.],
       [ 0.,  0.,  0., 12.],
       [ 0.,  0.,  0.,  0.]])
>>> 
疎行列を表す型はモジュール scipy.sparse の下にあります.上記の例では lil_matrix という型を使って行列を設定しています.lil_matrix のコントラクタでは行列のサイズ(行数と列数)を指定します.このようにしてできた疎行列は全要素が0であるので,必要な要素に値を設定していきます.疎行列型を使った計算が威力を発揮するのは,サイズがとても大きく,ほとんどの要素が0の場合ですが,上記の例では使い方を示すために小さいサイズの行列で示しています.
toarray メソッドで疎行列を密行列に変換していますが,これはわかりやすく表示するためであって,通常大きなサイズの疎行列を扱うときにはtoarray メソッドは実用的ではありません.
疎行列a はtocsr メソッドによってcsr_matrix 型に変換されてa1に格納されています.同様に b もcsr_matrix 型に変換します.a とb をcsr_matrix型に変換したものが,a2とb2に格納されています.そして,a2.dot(b2)で積を計算しています.
 
疎行列による計算を行う場合は,csr_matrix型またはcsc_matrix型に変換してから計算を行います.lil_matrixでも計算はできるのですが,計算速度の面ではcsr_matrix とcsc_matrix の方が勝っています.しかし,csr_matrixとcsc_matrixは行列の要素に逐次値を設定することができないので,値の設定にはlil_matrix の方が便利です.
疎行列を扱う場合の一般的な流れは以下のようになります.
  • lil_matrix 型の変数を用意して,各要素に値を設定する
  • 設定したlil_matrixをcsr_matrixまたはcsc_matrixに変換する
  • 変換された疎行列について計算する
csr_matrix とcsc_matrixの違いについて説明します.csr_matrix は行を取り出す操作が高速で,csc_matrix は列を取り出す操作が高速であるという違いがあります.
>>> from scipy import sparse
>>> a = sparse.lil_matrix*3
>>> a[0, 1] = 1
>>> a[1, 2] = 2
>>> a[2, 3] = 3
>>> a[3, 3] = 4
>>> a1 = a.tocsr()
>>> a2 = a.tocsc()
>>> type(a1)
<class 'scipy.sparse.csr.csr_matrix'>
>>> type(a2)
<class 'scipy.sparse.csc.csc_matrix'>
>>> b1 = a1.getrow(1)
>>> b1.toarray(1)
>>> b2 = a2.getcol(3)
>>> b2.toarray()
array([[0.],
       [0.],
       [3.],
       [4.]])
>>> type(a1.T)
<class 'scipy.sparse.csc.csc_matrix'>
>>> type(a2.T)
<class 'scipy.sparse.csr.csr_matrix'>
>>> 
ここではlil_matrix 型にa 値を設定して,それをcsr_matrix に変換したものをa1 に,csc_matrixに変換したものをa2 にそれぞれ格納しています.type関数によってa1 とa2 の型を確かめています.a1 にはcsr_matrix 型が入っているので,getrow メソッドで指定した行の値を取得することが効率よくできます.
a2 についてはcsr_matrixが入っているので,getcolメソッドで指定した列の取得が効率よくできます.csr_matrix にもgetcolメソッドは存在し,csr_matrix にもgetrow メソッドが存在するのですが,効率(計算速度)が良くないので,あまり使うべきではありません.
密行列(2次元配列)と同様に疎行列も .T で転置を取ることができますが,csr_matrix の転置はcsr_matrix になり,csr_matrix の転置は,csc_matrix になるので注意が必要です.

 

*1:4, 5

*2:5, 4

*3:4, 4