块矩阵乘积-稀疏矩阵 [英] Numpy matrix product - sparse matrices

问题描述

让我们考虑矩阵A为对角矩阵，矩阵B为随机矩阵，两者的大小均为N xN. 我们想利用矩阵A的稀疏属性来优化点积，即dot(B，A).

Let us consider a matrix A as a diagonal matrix and a matrix B a random matrix, both with size N x N. We want to use the sparse properties of the matrix A to optimize the dot product, i.e. dot(B,A).

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

However if we compute the product using the sparcity properties of the matrix A, we cannot see any advantage (and it is much slower).

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 s，sys:8毫秒，总计:3.52 s 挂墙时间:3.74 s

CPU times: user 3.51 s, sys: 8 ms, total: 3.52 s Wall time: 3.74 s

CPU时间:用户348毫秒，sys:0 ns，总计:348毫秒 挂墙时间:230毫秒

CPU times: user 348 ms, sys: 0 ns, total: 348 ms Wall time: 230 ms

如何正确执行?

推荐答案

差异源于您在计时(轻微影响)期间将B转换为稀疏矩阵的事实，更糟糕的是，dot不是意识到A是稀疏的事实.如果您要在点积之前进行转换，那么稀疏点积实际上会更快:

The difference stems from the fact that you convert B to a sparse matrix during the timing (minor effect) and even worse, that dot is not aware of the fact, that A is sparse. If you were to do the conversion before the dot product the sparse dot product is actually faster:

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毫秒

Gives:
np.dot(B, A): 1 loop, best of 3: 414 ms per loop
csr_matrix(B).dot(A): 1 loop, best of 3: 2.22 s per loop
Bsparse.dot(A): 1 loop, best of 3: 2.17 s per loop
csr_matrix.dot(B, Asparse): 10 loops, best of 3: 32.5 ms per loop
csr_matrix.dot(Bsparse, Asparse): 10 loops, best of 3: 28 ms per loop

您可以看到，在A为稀疏矩阵格式的所有情况下，稀疏点积都快得多，这使dot意识到了A是稀疏的事实.在您的时间安排中，该函数实际上是将B转换为稀疏格式，然后将其转换为具有密集矩阵A的点积.

As you can see the sparse dot product is much faster in all cases where A is in a sparse matrix format which is making dot aware of the fact, that A is sparse. In your timing, the function is actually doing a conversion of B to a sparse format and then a dot product with a dense matrix A.

这篇关于块矩阵乘积-稀疏矩阵的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！