Why sparse matrix computing on python is too slow
<p>The format I have used is the csr sparse matrix, which is recommended to be the fastest sparse structure for add and dot opertor. I compared its performance with the add and dot operator of np.array. However, it seems very weird that the computing for sparse matrix is much slower than the case under dense format. Why is it? And is there any more efficient way to implement sparse computing?</p>

<pre><code>import numpy as np
import scipy.sparse as sp
import random

#%% generate dense vector
vector_length = 10000
nonzero_term = 200

x = np.zeros((vector_length, ))
y = np.zeros((vector_length, ))

index = random.sample(range(vector_length), nonzero_term)
x[index] = np.random.rand(nonzero_term)
index = random.sample(range(vector_length), nonzero_term)
y[index] = np.random.rand(nonzero_term)

#%% transform to sparse vector
x_sp = sp.csr_matrix(x)
y_sp = sp.csr_matrix(y)

#%% test

# dense add
%timeit [x + y]
# sparse add
%timeit [x_sp + y_sp]     
# dense dot
%timeit [x.dot(y)]
# sparse dot
%timeit [x_sp.dot(y_sp.T)] 
</code></pre>

<p>and the result shows</p>

<pre><code>100000 loops, best of 3: 6.06 Âµs per loop
10000 loops, best of 3: 97.8 Âµs per loop
100000 loops, best of 3: 3.45 Âµs per loop
1000 loops, best of 3: 225 Âµs per loop
</code></pre>

<p>Both sets of operations use compiled code. But the data is stored quite differently.</p>

<p><code>x.shape</code> is (10000,); <code>y</code> likewise.  <code>x+y</code> just has to allocate an array of the same shape, and efficiently in <code>c</code> step through the 3 data buffers.</p>

<p><code>x_sp</code> has 200 nonzero values, the values are in <code>x_sp.data</code> and their column indices in <code>x_sp.indices</code>.  There is a third array, <code>x_sp.indptr</code> but with only 2 values.  Similarly for <code>y_sp</code>.  But to add them, it has to step through 4 arrays, and assign values to two arrays.  Even when coded in <code>c</code> there's a lot more work.  In my test case <code>x_sp+y_sp</code> has 397 nonzero values.  </p>

<p>With these 1d arrays (1 row matrices), the <code>dot</code> involves the same sort of stepping through values, only summing them all to one final value.</p>

<p>If the density of the matrices is low enough sparse calculations can be faster.  That's true, I think, of matrix multiplication more so than addition.  </p>

<p>In sum, the per element calculation is more complicated with sparse matrices.  So even if there are few elements, the overall time tends to longer.</p>

python performance numpy scipy sparse-matrix