Re: Slow sparse matrix multiplication

[Andy Adler]

On Wed, 9 Mar 2005, Richard Hindmarsh wrote:

> Matrix-matrix multiplication for very sparse matrices seems a bit slow.
> The results below apply also to very sparse matrix/vector multiplications.
>
> CVS downloaded 9th March 2005, x86-64, gcc3.3.2
>
> octave:17> a = sparse(10000,10000);
> octave:18> a(1,1) = 1;
>
> octave:19> tic;a*a;toc
> ans = 0.73152
> octave:20> tic;a+a;toc
> ans = 0.00047300
>
> Given that the number of f.p. operations are the same, one would expect
> similar timings. I'd be happy to have a look at the matrix
> multiplication routines if pointed too them.

Sparse multiply is inherently slower because of the tricky indexing,
and the memory management. For C=A+B, nnz(C) <= nnz(A) + nnz(B),
for multiply, there is no such limit.

The algorithm is in liboctave/Sparse-op-defs.h (SPARSE_SPARSE_MULTIPLY).
If you look at the code in octave-forge (main/sparse/sparse_ops.cc
and main/sparse/sparse_ops.h), you will see another algorithm commented
out (I thought it would be faster, but it wasn't).

Here is a comparison with matlab (on 2.8GHz debian linux)

CODE:
    for d=[1e-6,1e-5,1e-4,1e-3,1e-2]; % sparse densities
        a=sprand(1e4,1e4,d);
        tic;a*a;   t1=toc;
        tic;a+a;   t2=toc;
        fprintf('%f %f %f\n',d,t1,t2);
    end

Octave (latest cvs)
    0.000001  0.198402  0.000817
    0.000010  0.666243  0.000765
    0.000100  0.653231  0.001149
    0.001000  0.733525  0.008373
    0.010000  4.891503  0.173296


Matlab 7.0.1
    0.000001  0.001259  0.000932
    0.000010  0.000940  0.000970
    0.000100  0.002911  0.002459
    0.001000  0.277165  0.023974
    0.010000 20.477461  0.549163

This seems to indicate that my algorithm beats Matlab's for sparse densities
 > .001. I definitely designed it with this in mind.

If you have any improvements, that would be appreciated.

--
Andy Adler




-------------------------------------------------------------
Octave is freely available under the terms of the GNU GPL.

Octave's home on the web:  http://www.octave.org
How to fund new projects:  http://www.octave.org/funding.html
Subscription information:  http://www.octave.org/archive.html
-------------------------------------------------------------