Csr_matrix.dot 对比 Numpy.dot

Question

我有一个大的 (n=50000) 块对角线 csr_matrix M 表示一组的邻接矩阵图。我必须将 M 乘以密集的 numpy.array v 几次。因此我使用 M.dot(v).

令人惊讶的是，我发现先将 M 转换为 numpy.array 然后使用 numpy.dot 会快得多。

知道为什么会这样吗？

Answer 1

我没有足够的内存来保存 50000x50000 密集矩阵并将其乘以 50000 向量。但是在这里找到一些维度较低的测试。

设置：

import numpy as np
from scipy.sparse import csr_matrix

def make_csr(n, N):
    rows = np.random.choice(N, n)
    cols = np.random.choice(N, n)
    data = np.ones(n)
    return csr_matrix((data, (rows, cols)), shape=(N,N), dtype=np.float32)

上面的代码在 NxN 矩阵中生成具有 n 个非零元素的稀疏矩阵。

矩阵：

N = 5000

# Sparse matrices
A = make_csr(10*10, N)     # ~100 non-zero
B = make_csr(100*100, N)   # ~10000 non-zero
C = make_csr(1000*1000, N) # ~1000000 non-zero
D = make_csr(5000*5000, N) # ~25000000 non-zero
E = csr_matrix(np.random.randn(N,N), dtype=np.float32) # non-sparse

# Numpy dense arrays
An = A.todense()
Bn = B.todense()
Cn = C.todense()
Dn = D.todense()
En = E.todense()

b = np.random.randn(N)

时间：

>>> %timeit A.dot(b)       # 9.63 µs per loop
>>> %timeit An.dot(b)      # 41.6 ms per loop

>>> %timeit B.dot(b)       # 41.3 µs per loop
>>> %timeit Bn.dot(b)      # 41.2 ms per loop

>>> %timeit C.dot(b)       # 3.2 ms per loop
>>> %timeit Cn.dot(b)      # 41.2 ms per loop

>>> %timeit D.dot(b)       # 35.4 ms per loop
>>> %timeit Dn.dot(b)      # 43.2 ms per loop

>>> %timeit E.dot(b)       # 55.5 ms per loop
>>> %timeit En.dot(b)      # 43.4 ms per loop

对于高度稀疏矩阵（A和B）它比1000x倍快。
对于不是很稀疏的矩阵（C），它仍然得到10x加速。
对于几乎非稀疏矩阵（D由于索引中的重复会有一些0，但从概率上讲并不多），它还是更快，不多，但是更快
对于真正的非稀疏矩阵（E），运算速度较慢，但不会慢很多。

结论： 您获得的加速取决于矩阵的 稀疏性 ，但是 N = 5000 稀疏矩阵是总是更快（只要他们有一些零条目）。

由于内存问题，我无法尝试 N = 50000。您可以尝试上面的代码，看看 N.

对您来说是什么样的

Csr_matrix.dot 对比 Numpy.dot

Csr_matrix.dot vs. Numpy.dot

python

numpy

scipy

sparse-matrix