Numpy 행렬 곱셈 - 희소 행렬

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 MS, 총 : 3.52의 벽 시간 : 3.74의

CPU 시간 : 사용자 348 MS, SYS : 0 NS , 합계 : 348 ms 벽 시간 : 230 ms

올바르게 수행하는 방법?

Answer 1

차이점은 B을 타이밍 (사소한 효과) 중에 변환하고 사실상 dot은 희박하다는 사실을 알지 못한다는 사실에서 유래합니다. 당신은 내적 전에 변환 작업을 수행하는 경우 스파 스 내적 빠른 실제로 :

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) : 루프 당 414 MS
csr_matrix(B).dot(A) : 1, 루프 3의 최고의 1 루프, (3) 최고 : 루프 당 2.22의
Bsparse.dot(A) : 1 루프, 3 최고 : 루프 당 2.17의
csr_matrix.dot(B, Asparse) : 10 개 루프, 3 최고 : 루프 당 32.5 MS
csr_matrix.dot(Bsparse, Asparse) : 10 개 루프, 3 최고 : 28 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