Asked by Sinwoo Jeong
on 15 Oct 2018

Hello.

The purpose of my code is solving O.D.E. and in the function I need to do large matrix multiplication every single time step.

Therefore, almost all CPU time taken is consumed in this matrix multiplications.

I think mentioning every detail of my code is not necessary. So, only simplified code is uploaded as follows:

C = rand(10000, 5000);

B = rand(10000, 1000);

for i = 1:1000

A = rand(10000, 1);

D = (A.*B)'*C;

end

Here, B and C are constant matrix but A is changed in every single for loop. That's why I put A into a for loop. (I used function rand here just for a simple example) I've tried GPU, mex file, etc. But I have not been able to find the way which is faster than normal MATLAB .* or * operation. I think I can pre-calculate the value of the multiplication between B and C to avoid multiplying B to A and C to (A.*B) again. But I have no idea. Could you guys please help me?

(The matrix are defined as a sparse matrix in my actual code)

Answer by Bruno Luong
on 15 Oct 2018

Edited by Bruno Luong
on 15 Oct 2018

Accepted Answer

It's actually very memory consuming for full matrix and noticeable slower due to inefficient memory access, even the FPU requirement is less.

However in some cases of SPARSE matrices, it can win, as showed in the test case bellow:

m = 5000;

n = 1000;

p = 10000;

C = sprand(p,m,1e-2);

B = sprand(p,n,1e-2);

A = rand(p,1);

tic

(A.*B).'*C;

toc % Elapsed time is 0.186504 seconds.

% Preparation step, must be carried out only once, since B and C are known

p = size(B,1);

[ib,jb,b] = find(B.');

[ic,jc,c] = find(C.');

commonj = intersect(jb,jc);

keepb=ismember(jb,commonj);

keepc=ismember(jc,commonj);

ib = ib(keepb);

jb = jb(keepb);

b = b(keepb);

ic = ic(keepc);

jc = jc(keepc);

c = c(keepc);

[~,locb]=ismember(jb,commonj);

[~,locc]=ismember(jc,commonj);

cb = accumarray(jb,ib,[p 1],@(x) {x});

cc = accumarray(jc,ic,[p 1],@(x) {x});

ifun = @(cb,cc) reshape(cb(:)+(cc(:).'-1)*size(B,2),[],1);

ibc = cellfun(ifun, cb, cc, 'unif', 0);

jfun = @(j) j+zeros(size(ibc{j}));

jbc = arrayfun(jfun, (1:p).', 'unif', 0);

b = accumarray(jb,b,[p 1],@(x) {x});

c = accumarray(jc,c,[p 1],@(x) {x});

vfun = @(b,c) reshape(b(:).*(c(:).'),[],1);

vbc = cellfun(vfun, b, c, 'unif', 0);

ibc = cat(1,ibc{:});

jbc = cat(1,jbc{:});

vbc = cat(1,vbc{:});

BC = sparse(ibc,jbc,vbc,size(B,2)*size(C,2),p);

%%this should be in the loop

tic

reshape(BC*A,size(B,2),[]);

toc % Elapsed time is 0.072390 seconds.

Stephan
on 15 Oct 2018

Hi,

link is dead - i think due to:

https://de.mathworks.com/matlabcentral/answers/%25%20https://fr.mathworks.com/matlabcentral/answers/416237-how-can-i-improve-the-speed-of-the-following-matrix-multiplication

i think it should be:

https://fr.mathworks.com/matlabcentral/answers/416237-how-can-i-improve-the-speed-of-the-following-matrix-multiplication

Sinwoo Jeong
on 15 Oct 2018

Sinwoo Jeong
on 15 Oct 2018

I think it works very well. You r a great genius.

Well, how did you come up with this brilliant idea?

Sign in to comment.

Opportunities for recent engineering grads.

Apply Today
## 1 Comment

## Stephen Cobeldick (view profile)

Direct link to this comment:https://nl.mathworks.com/matlabcentral/answers/424000-how-can-i-speed-up-this-large-matrix-multiplications#comment_622594

Sign in to comment.