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

不同之处在于您在计时期间将 B 转换为稀疏矩阵（影响较小），更糟糕的是，dot 没有意识到 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)

Asparse = csr_matrix(A)
Bsparse = csr_matrix(B)

%timeit np.dot(B, A)
%timeit csr_matrix(B).dot(A)
%timeit Bsparse.dot(A)
%timeit csr_matrix.dot(B, Asparse)
%timeit csr_matrix.dot(Bsparse, Asparse)

给出：
np.dot(B, A)：1 个循环，3 个循环中的最佳：每个循环 414 毫秒
csr_matrix(B).dot(A)：1 个循环，3 个循环中的最佳：每个循环 2.22 秒
Bsparse.dot(A)：1 个循环，3 个循环中的最佳：每个循环 2.17 秒
csr_matrix.dot(B, Asparse)：10 个循环，最好的 3 个：每个循环 32.5 毫秒
csr_matrix.dot(Bsparse, Asparse)：10 个循环，最好的 3 个：每个循环 28 毫秒

如您所见，在 A 采用稀疏矩阵格式的所有情况下，稀疏点积的速度要快得多，这让 dot 意识到 A稀疏。在您的时间里，该函数实际上是将 B 转换为稀疏格式，然后将点积转换为密集矩阵 A.

Answer 2

做对了，稀疏点更快 - 如果矩阵确实是稀疏的。但是你不能只是将数组放入 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 有 none，但它是稀疏格式

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

Numpy 矩阵积 - 稀疏矩阵

Numpy matrix product - sparse matrices

python

numpy

sparse-matrix