Numpy matrix乘積 - 稀疏矩陣

Question

讓我們考慮一個矩陣A作爲對角矩陣和一個矩陣B一個隨機矩陣，它們的大小均爲N×N。 我們希望使用矩陣A的稀疏屬性來優化點產品，即點（B，A）。然而，如果我們使用矩陣A的sparcity屬性來計算產品，我們就看不到任何優勢（而且速度慢得多）。

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小號 牆時間：3.74小號

CPU時間：用戶348毫秒，SYS：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每人S環
Bsparse.dot(A)：1循環，最好的3：每次循環2.17小號
csr_matrix.dot(B, Asparse)：10個循環，最好的3：每次循環32.5毫秒
csr_matrix.dot(Bsparse, Asparse)：10個循環，最好的3：28 ms per loop

正如您所看到的，在所有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現在沒有，但它是在稀疏格式

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