Csr_matrix.dot与Numpy.dot

Question

我有一个大（N = 50000）块对角线csr_matrix中号表示一组图形的邻接矩阵。我必须多次乘以M的致密numpy.arrayv。因此我使用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。