I want to multiply a sparse vector and a huge matrix. How the position of nonzero elements of the vector could be employed to obtain a meaningful speed up.

I want to multiply a vector t and a Matrix T : Z=t’*T. t is a n dimensional vector and T is a n by m matrix with large m (e.g. 10^5) and n (e.g. 400). I know that t contains a few (say s) nonzeros. Then I have attempted to reduce the computation time as follows:

ind=find(t~=0); Z=t(ind)’*T(ind,:);

Surprisingly the computation time increases. I have extended my test for different values of n as follows, and get the following graph.

for s=1:100

    T=[rand(s,100000);zeros(400-s,100000)];
    t=T(:,1);

    tic
    Z1=t(1:s)'*T(1:s,:);
    time1=toc;

    tic
    Z2=t'*T;
    time2=toc;

    speedup(s)=time2/time1;
end
plot(speedup)

The graph indicates that for s>0.1*n the new algorithm is slower than ordinary multiplication. Even for s<0.1*n the achieved speed up is very smaller than what expected considering the number of required multiplications in each case.

Note that most of the time is dedicated to formation of the submatrix T2=T(1:s,:) and if we precompute the submatrix the achieved speed up would be much larger. For example if we replace the first piece of the code with the following,

    T2=T(1:s,:);
    tic
    Z1=t(1:s)'*T(1:s,:);
    time1=toc;

we will achieve a speed up of 7.2 for s=40. However despite simplified piece of code used here for test, the position of nonzero elements are unknown in general. Hence, I cannot precompute the submatrix T2=T(ind,:) and it should be formed in the loop.

I also tested the effect of sparse matrices, but didn’t get considerable improvement. The question is: how a reasonable speed up can be achieved employing the prior knowledge about position of zeros and nonzeros of t.

Thank you very much, Mohammad