python - Numpy 矩阵积 - 稀疏矩阵

Question

让我们将矩阵 A 视为对角矩阵，将矩阵 B 视为随机矩阵，大小均为 N x N。我们想利用矩阵 A 的稀疏特性来优化点积，即 dot(B,A)。

但是，如果我们使用矩阵 A 的稀疏性来计算乘积，我们看不到任何优势(而且速度要慢得多)。

import numpy as np
from scipy.sparse import csr_matrix
# Matrix sizes
N = 1000

#-- matrices generation --
A = np.zeros((N,N), dtype=complex)
for i in range(N):
    A[i][i] = np.random.rand()
B = np.random.rand(N,N)

#product
%time csr_matrix(B).dot(A)
%time np.dot(B,A)

结果:

CPU 时间:用户 3.51 秒，系统:8 毫秒，总计:3.52 秒挂墙时间:3.74 秒

CPU 时间:用户 348 毫秒，系统:0 纳秒，总计:348 毫秒挂墙时间:230 毫秒

如何正确操作？

Answer 1

做得对，稀疏点更快 - 如果矩阵确实是稀疏的。但是您不能只是将数组放入 csr_matrix.dot 函数中。

In [68]: N=1000
In [69]: from scipy import sparse
In [70]: A=np.eye(N)         # the diagonal is more interesting than all zeros
In [71]: B=np.random.rand(N,N)

基本情况 - 密集矩阵乘积

In [72]: timeit np.dot(B,A)
10 loops, best of 3: 98.8 ms per loop

对于所有相同大小的数组(例如 dot(B,B)、dot(A,A))，这个时间是相同的。

从两者制作稀疏矩阵。 As 有很多零，Bs 没有，但它是稀疏格式

In [73]: As=sparse.csr_matrix(A)
In [74]: Bs=sparse.csr_matrix(B)

注意转换时间；他们不是微不足道的

In [101]: timeit sparse.csr_matrix(A)
100 loops, best of 3: 13.8 ms per loop
In [102]: timeit sparse.csr_matrix(B)
10 loops, best of 3: 50.1 ms per loop

使用 csr 矩阵的矩阵乘积可以更快。我将使用 Bs.dot(As) 形式，因为它更清晰。 Bs*As 和 np.dot(Bs,As) 是等价的。但是不要尝试 np.dot(Bs,A)

In [107]: timeit Bs.dot(As)
100 loops, best of 3: 19 ms per loop

In [112]: timeit sparse.csr_matrix(B).dot(sparse.csr_matrix(A)).A
10 loops, best of 3: 94.1 ms per loop

明显好于密集版本，但如果我们包括转换时间，则略好一些。

但请注意，时间因矩阵的稀疏性而有很大差异

In [108]: timeit As.dot(Bs)
100 loops, best of 3: 10 ms per loop
In [109]: timeit As.dot(B)
100 loops, best of 3: 5.82 ms per loop
In [110]: timeit As.dot(As)
1000 loops, best of 3: 215 µs per loop
In [111]: timeit Bs.dot(Bs)
1 loop, best of 3: 3.83 s per loop