|
From: | Richard Hindmarsh |
Subject: | Re: Slow sparse matrix multiplication |
Date: | Thu, 10 Mar 2005 02:40:47 -0600 |
User-agent: | Mozilla/5.0 (Windows; U; WinNT4.0; en-US; rv:1.7.1) Gecko/20040707 |
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.163557Here 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 -------------------------------------------------------------
[Prev in Thread] | Current Thread | [Next in Thread] |