Why sparse matrix computing on python is too slow

Question

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?

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)]

and the result shows

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

hpaulj hpaulj · Accepted Answer · 2016-10-19T05:17:13

Both sets of operations use compiled code. But the data is stored quite differently.

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

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

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

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.

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.

Why sparse matrix computing on python is too slow

1 Answers