Numpy matrix product - sparse matrix

Question

行列Aを対角行列、行列Bを両方ともサイズN x Nのランダム行列としましょう。行列Aのスパースプロパティを使用して、ドットを最適化します。すなわちドット（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秒、SYS：8ミリ秒、合計：3.52 S 壁時間：3.74秒

CPU時間：ユーザー348ミリ秒、SYS：0 NS 、合計：348 ms ウォールタイム：230 ms

正しく行う方法は？

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ループを、ループ当たり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 3のベストループ毎のms

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