疎行列

非0値(Number of Non-Zero, NNZ)が少なく、要素の大半が0で埋められているような行列です。
例えばこんなの。

この程度の行数×列数であれば大丈夫ですが、行も列も数十万・数百万・あるいはそれ以上のオーダーがある場合、メモリに載せられないといったことも起こりえます。無駄な計算も増えます。

CSRは疎行列を表現する形式の一つ

ということで「効率良く疎行列を表記しましょう」という形式の一つがCSR形式です。
他にも色々ありますがCOOとCSR以外省きます。

COOについて

効率良く疎行列を表現するためには0以外の値がどの座標にあるかを示してそれ以外を0とみなせば良いですよね。
例えば

こんな行列があったとすると、値と行と列の対応は

このようになります。(0インデックス)
座標で書くとこうなりますね。

(0,0) 1
(0,3) 2
(1,1) 3
(2,0) 1
(3,2) 5

4行4列程度なのであまり違いはないですが、行・列が増えていくと顕著に差が出ます。

CSRについて

次にCSRです。こいつを理解するのに時間がかかりました。

CSRでは、「その行に属する値と列がどこから始まるか」をポインタで表す

ここが肝要で、理解できていなかった原因でした。
CSRでは、行のインデックスではなく「Index Pointer」と値・列で行列を表します。

先ほどの行列、

の値・行・列を、行ごとに着色してみましょう。

このようになります。
各行に属する値がどこから始まるかわかりやすくなりました。

この表は、こう書き直すこともできますよね。

そう、このポインタの矢印が「Index Pointer」となります。

つまり、配列「Index Pointer」は [0,2,3,4,5] と表され、図にすると

となるわけです。
実際、

import numpy as np
from scipy import sparse

data = np.array([[1,0,0,2],[0,3,0,0],[1,0,0,0],[0,0,5,0]])
sparse_data = sparse.csr_matrix(data)

print("sparse_data.data = {}".format(sparse_data.data))
print("sparse_data.indices = {}".format(sparse_data.indices))
print("sparse_data.indptr = {}".format(sparse_data.indptr))

sparse_data.data = [1 2 3 1 5]
sparse_data.indices = [0 3 1 0 2]
sparse_data.indptr = [0 2 3 4 5]

なるほどねー！

…じゃあ、値が全部0の行(空の行)があったらどうなるんですか？

はい、ここでめっっっっっちゃ詰まりました。
「ポインタで表す」が理解できていなかったからですね。

例えば、こういう全ての値が0の行を含む行列があったとします。

この場合、Index Pointerはどうなるでしょうか？

まずCOO形式で確認してみましょう。

こうなります。

これをCSR形式で表す場合、空の行である1行目と3行目の開始位置はどこになるでしょうか？
答えは

こうです。
なぜなら、 その行に1つもNNZが無いので、ポインタは動かない からです。
したがって、Index Pointerの配列は [0,3,3,4,4] になります。

import numpy as np
from scipy import sparse

test_empty = np.array([[1,0,5,2],[0,0,0,0],[1,0,0,0],[0,0,0,0]])
sparse_empty = sparse.csr_matrix(test_empty)

print("sparse_empty.data = {}".format(sparse_empty.data))
print("sparse_empty.indices = {}".format(sparse_empty.indices))
print("sparse_empty.indptr = {}".format(sparse_empty.indptr))

sparse_empty.data = [1 5 2 1]
sparse_empty.indices = [0 2 3 0]
sparse_empty.indptr = [0 3 3 4 4]

「行ごとにポインタで表す」をちゃんと理解してないと腑に落ちないですねー。

「CSR形式」を理解するのに時間がかかったので自分なりにまとめてみた

疎行列

CSRは疎行列を表現する形式の一つ

COOについて

CSRについて

CSRでは、「その行に属する値と列がどこから始まるか」をポインタで表す

…じゃあ、値が全部0の行(空の行)があったらどうなるんですか？