[SciPy-Dev] scipy.sparse vs. pysparse

[Pauli Virtanen]

Hi,

Here is some optimization reducing the runtime overhead of scipy.sparse
matrix-vector multiplication by a factor of 5.

     https://github.com/pv/scipy-work/compare/master...enh/sparse-speedup

And a patch against Scipy 0.9.0 (@Tony: maybe you want to try it out?):

https://github.com/pv/scipy-work/compare/v0.9.0...enh/sparse-speedup-0.9.patch

     ***

Quick benchmark: http://dl.dropbox.com/u/5453551/bench_sparse.py
(Multiply vector with 1-D CSR Laplacian operator.)

After:

% N       scipy.sparse        pysparse
32           7.169e-06       1.048e-06
64           7.367e-06       1.787e-06
128          7.814e-06       3.284e-06
256          8.633e-06       6.336e-06
512          1.025e-05       1.241e-05
1024         1.435e-05       2.455e-05
2048         1.989e-05       4.882e-05
4096         3.384e-05       9.798e-05
8192         6.098e-05       0.0001959

Before:

% N       scipy.sparse        pysparse
32           3.708e-05       1.032e-06
64           3.736e-05       1.803e-06
128          3.777e-05       3.368e-06
256           3.95e-05       6.324e-06
512          4.116e-05       1.267e-05
1024         4.661e-05       2.455e-05
2048          5.38e-05       4.873e-05
4096         6.946e-05       9.763e-05
8192         9.563e-05       0.0001959

The cross-over occurs around N ~ 300 instead of around N ~ 3000. The 
main reason for the overhead is that multiplication with a sparse 
Laplacian is a pretty lightweight operation, so the fact that some of 
scipy.sparse is written in pure Python starts to matter.

-- 
Pauli Virtanen