Re: Slow sparse matrix multiplication

[Richard Hindmarsh]

Thanks for your comments. I tried repeating your test (x86-64,  Fedora, 
Kernel 2.4.22, Opteron 242, 1.6GHz). It seems that there is a 
granularity at low densities. I suppose the granularity depends upon the 
exact sparsity patterning.

For 3D PDE applications, e.g. the 3D Laplacian on a cubic grid, 
densities are 7/m^3 where m is the number of grids along the size. 
Densities are < 0.001 for m <~19. There may be a case for investigating 
a density-dependent multipication strategy.

octave:1> adlersmmtest
0.000001 0.200925 0.000516
0.000010 0.731498 0.000461
0.000100 0.735778 0.000892
0.001000 0.806021 0.009376
0.010000 5.453526 0.166891
octave:2> adlersmmtest
0.000001 0.732628 0.000419
0.000010 0.732120 0.000431
0.000100 0.735853 0.000885
0.001000 0.806065 0.009366
0.010000 5.470995 0.165118
octave:3> adlersmmtest
0.000001 0.140497 0.000427
0.000010 0.732410 0.000433
0.000100 0.735816 0.000890
0.001000 0.805692 0.009357
0.010000 5.471080 0.164358
octave:4> adlersmmtest
0.000001 0.732933 0.000422
0.000010 0.732137 0.000440
0.000100 0.735111 0.000886
0.001000 0.805907 0.009366
0.010000 5.464071 0.163557

Here are some Matlab tests. Your qualitative results reobtained. Note 
timings non-monotone at low density.

>> adlersmmtest
0.000001 0.001506 0.000975
0.000010 0.000763 0.000816
0.000100 0.002069 0.001575
0.001000 0.250859 0.017305
0.010000 24.036473 0.368844
>> adlersmmtest
0.000001 0.004521 0.000819
0.000010 0.000777 0.000809
0.000100 0.002059 0.001637
0.001000 0.251042 0.017393
0.010000 24.045148 0.273525
>>

Regards
Richard

Andy Adler wrote:

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