Fast sparse matrix-vector multiplication?

Hi,

I need to perform large sparse matrix-vector multiplications (matrix size up to 100mX100m). The matrix need of course to be sparse (otherwise I would have problems with the memory), and I noticed that the operator * does NOT support multithreading with sparse matrices. Hence, when I run my program on a cluster I do not get significant speedups. Can you help me? Thanks a lot!

Answer 1

[John D'Errico]

As usual, people want huge operations to run in milliseconds, as if their computer was infinitely large and infinitely fast. No matter how fast you get it running, tomorrow or next week you will want to solve problems 10 times as big in the same amount of time.

Sorry, but get a faster computer. What else can be realistically said here?

[Salvatore Lo Bello]

This is not the point, here. I am not complaining about MATLAB performance on my computer. I am just asking whether the multiplication can be made in such a way to be scalable: right now, if I were to run it on a 300-core cluster, it would NOT be much faster, this is the issue. I hope it is clear now, thanks.

[José-Luis]

openblas offers multi-threaded matrix multiplication. I have no idea what Matlab uses under the hood. Might be the same thing. You could always try to optimize the compilation for your system. You might need to adapt the code to your sparse needs, but it's open source.

10^8 * 10^8 is MASSIVE. Even if it is sparse, this is bound to take a long time, if at all possible.

[Bjorn Gustavsson]

If your matrix stays the same one idea might be to split the matrix-vector multiplication up into a sum of smaller matrix-vector multiplications and distribute the "smaller" matrices. To me this sounds like a bit of extra data-transfer so might not be faster, but it would be a way to parallelize your computations...

HTH

[John D'Errico]

Sparse matrix multiplies run in only one core in MATLAB, at least at the current time. That may change in the future, but I did recently verify that MATLAB uses one core only here.

[Bjorn Gustavsson]

What I had in mind was to instead of doing:

V = randn(9,1);
M = randn(9,9);
MV = M*V;

it might be possible to manually partition the calculations similar to:

M1 = M(:,1:3);                           
M2 = M(:,(1:3)+3);
M3 = M(:,(1:3)+6);
MV123 = M1*V(1:3) + M2*V(4:6) + M3*V(7:9);

If it is beneficial to do this "manual" parallelization or not depends on whether the increase of data-transfer and so on, but it is trivially possible to parallelize also sparse multiplications.