[SciPy-dev] sparse matrix multiplication - poor performance

Nathan Bell wnbell at gmail.com
Wed Dec 6 16:16:39 CST 2006


There appears to be something terribly wrong with the current
implementation of sparse matrix multiplication.  Consider the test
below done in both MATLAB and scipy.

MATLAB is  [660.5872  936.8530  702.5506  650.2876] times faster for
these four problems.  Changing N = 100,000 puts the ratio in the
neighborhood of 4000.

Also, doing "B = A*A.T" takes *hundreds* of times longer than "B =
A*A" or "B = A.T*A".  This is more than the time required for dense
matrix multiplication (try N=1000).

Can anyone comment on this?  Is the SPARSKIT code really that slow?


Also, I made an improvement [1] to the coo_matrix.tocsr() and
coo_matrix.tocsr() methods.  Is there a reason it hasn't been
included?  I'd commit it myself, but I don't have the privileges.  Who
do I need so speak to about SVN commit access?  FWIW I've contributed
a few bug reports and some additional SWIG wrappers for UMFPACK (via
Robert Cimrman).  The sparse matrix functionality is especially
important for my work, so I'd like to help on that front.

Thanks.


[1] http://projects.scipy.org/scipy/scipy/ticket/326




--------------------MATLAB CODE--------------------
% 10K identity
N = 10*1000;
A = speye(N);
tic; B = A'*A; toc;
tic; B = A*A; toc;

% 10K tridiagonal
M = repmat((1:N)',1,3);
A = spdiags(M,[-1 0 1],N,N);
tic; B = A'*A; toc;
tic; B = A*A; toc;

--------------------MATLAB OUTPUT--------------------

Elapsed time is 0.004496 seconds.
Elapsed time is 0.001932 seconds.
Elapsed time is 0.011017 seconds.
Elapsed time is 0.010257 seconds.

--------------------SCIPY CODE--------------------

from scipy import *
import time
N = 10*1000

A = sparse.speye(N,N)
start = time.clock()
B = A.T*A
print time.clock() - start
start = time.clock()
B = A*A
print time.clock() - start


A = sparse.spdiags(rand(3,N),[-1,0,1],N,N)
start = time.clock()
B = A.T*A
print time.clock() - start
start = time.clock()
B = A*A
print time.clock() - start

--------------------SCIPY OUTPUT--------------------

2.97
1.81
7.74
6.67

---------------------------------------------------------------

-- 
Nathan Bell wnbell at gmail.com


More information about the Scipy-dev mailing list