scipy.sparse の公式ドキュメント (https://docs.scipy.org/doc/scipy/reference/sparse.html) をもとに、7種類のスパース行列について自分用に整理しておきます。
目次・全体像
- COO
- CSR
- CSC
- LIL
- DOK
- DIA
- BSR
| 形式 | 正式名 | 保存の考え方 | 得意 | 苦手 |
|---|---|---|---|---|
| COO | Coordinate |
(row, col, data) の並び |
構築、重複許容、変換 | 演算、スライス |
| CSR | Compressed Sparse Row | 行ごと圧縮 | 行アクセス、A@x、演算 |
列アクセス、構造変更 |
| CSC | Compressed Sparse Column | 列ごと圧縮 | 列アクセス、演算 | 行アクセス、構造変更 |
| LIL | List of Lists | 行ごとの列リスト＋値リスト | 構築、編集、行ベース操作 | 高速計算 |
| DOK | Dictionary of Keys |
(i,j)→値 の辞書 |
1要素更新 | 本格的計算 |
| DIA | Diagonal | 対角線ごと保存 | 帯行列、対角中心 | 一般疎行列、スライス |
| BSR | Block Sparse Row | ブロックごと CSR | ブロック疎行列 | 一般疎行列、スライス |
1. COO (COOrdinate format)
「作成」専用の座標リスト形式
非ゼロ要素の「行・列・値」を並べる形式 ( ijv or triplet format)。
重複した座標 (i, j) は、CSRやCSCへの変換時に足し合わされる。
row = np.array([0, 3, 1, 0])
col = np.array([0, 3, 1, 2])
data = np.array([4, 5, 7, 9])
coo_matrix((data, (row, col)), shape = (4, 4)).toarray()
✔ 利点
- 要素が重複してもOK
- CSR, CSCへの高速な変換が可能
✖ 欠点
- 算術演算全般
- スライシング操作
COOはあくまでも「作成」用であり、「演算」を行う際は CSR/CSC に変換するのが基本的な使い方。
2. CSR (Compressed Sparse Row)
「演算」用の標準的な行指向形式
名前の通り、スパース行列の非ゼロ要素を行ごとに圧縮して保存する。
CSRは (data, indices, indptr) の3つで構成される。(indptr = index pointer)
-
data: 非ゼロ要素 -
indices: 非ゼロ要素の列番号 -
indptr: 各行がdataのどこから始まるか。indptr[i]:indptr[i+1]がi行目に対応する。
data = np.array([1, 2, 3, 4, 5, 6])
indices = np.array([0, 2, 2, 0, 1, 2])
indptr = np.array([0, 2, 3, 6])
csr_matrix((data, indices, indptr), shape = (3, 3)).toarray()
indptr = [0, 2, 3, 6]
[0, 2] : dataの 0, 1番目が 0行目.
[2, 3] : dataの 2番目が 1行目.
[3, 6] : dataの 3, 4, 5番目が 2行目.
\begin{pmatrix}
1 & 0 & 2 \\
0 & 0 & 3 \\
4 & 5 & 6 \\
\end{pmatrix}
✔ 利点
- 効率的な演算が可能 (CSR+CSR, CSR*CSR など)
- 効率的な行スライシング
- 高速な行列-ベクトル積
A @ x演算
✖ 欠点
- 列スライシングは処理速度が遅くなる場合がある (CSCを使用)
- スパース行列の構造そのものを変更する場合は高コスト。つまり、
A[i, j] = ...を大量に繰り返すような「作成」段階では不向き。この場合はLILやDOKを使用する。
3. CSC (Compressed Sparse Column)
CSRの列指向バージョン
4. LIL (row-based List of Lists)
「作成」専用の行ベース形式
行列の作成が完了したら、CSRやCSCに変換してから演算を行う。
lil = lil_matrix((3, 3))
lil[0, 1] = 10
lil[1, 1] = 20
lil[2, 2] = 30
print(lil)
print(lil.toarray())
Coords Values
(0, 1) 10.0
(0, 2) 20.0
(2, 2) 30.0
\begin{pmatrix}
0 & 10 & 20 \\
0 & 0 & 0 \\
0 & 0 & 30
\end{pmatrix}
5. DOK (Dictionary Of Keys)
辞書ベースの編集用形式
ほぼ辞書そのもので、キーが (row, col)、バリューが要素値となる。
スパース行列のインクリメンタルな作成を効率的にできる。
dok = dok_matrix((3, 3))
for i in range(3):
for j in range(3):
dok[i, j] = i + j # update element
\begin{pmatrix}
0 & 1 & 2 \\
1 & 2 & 3 \\
2 & 3 & 4
\end{pmatrix}
参考