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)

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

矩阵：

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查看您的感受。