Asked by Sinwoo Jeong
on 13 Jun 2017

For example, we have arbitrary matrix A, B, and C.

A = [1 2 3 3; 4 5 6 5; 7 8 9 9]

B = [2 4 6 1; 6 9 0 6; 1 2 5 8]

C = [2; 3; 4]

What I want to do is the operation as follows:

for k = 1:4

for i = 1:4

f = A(:,k).*B(:,i).*C;

sum_f= sum(f);

out(k,i) = sum_f;

end

end

The problem is that with this for loop operation, CPU time increases exponentially when the matrix size gets larger.

I'd like to do this operation with matrix multiplication, and I want to do it more efficiently.

Does anyone have an idea?

Answer by John D'Errico
on 13 Jun 2017

Edited by John D'Errico
on 13 Jun 2017

Accepted Answer

Assuming you really want this to be faster, not an increase in the time required, you can just do this:

A'*diag(C)*B

If you have the current releae of MATLAB, thus R2017a (or later), then you could have done it like this:

A'*(C.*B)

That should be slightly faster for larger matrices, saving some multiplies by zero. For 4x4 matrices, in fact the version that uses diag seems fastest.

A = rand(100);

C = rand(100,1);

B = rand(100);

timeit(@() A'*diag(C)*B)

ans =

0.00020056

timeit(@() A'*(C.*B))

ans =

0.00018636

For 1000x1000 matrices, the difference is more dramatic.

A = rand(1000);

C = rand(1000,1);

B = rand(1000);

timeit(@() A'*diag(C)*B)

ans =

0.10736

timeit(@() A'*(C.*B))

ans =

0.055341

Even these computations are O(N^3) in time. But the constant in front is pretty small.

Oh, you state your code was exponentially increasing with size. That is wrong. While you need to learn to preallocate matrices like out, since if you do not, it will be slow. The matrix multiplies that you wrote as loops are O(N^3) in time. But what was worse is that if you do not preallocate the out array, the computation time will grow as O(N^4), since the size of the array will grow as N^2, but the time to dynamically reallocate the memory at each step grows as the square of that.

Regardless, O(N^4) is NOT exponential growth, merely polynomial growth. And you can cut all of that dramatically, merely by learning to use array operations instead of loops.

Sinwoo Jeong
on 15 Jun 2017

Thank you so much for your perfect answer.

Andrei Bobrov
on 15 Jun 2017

+1

Hi Sinwoo! Please accept this answer.

Sign in to comment.

Opportunities for recent engineering grads.

Apply Today
## 2 Comments

## Adam (view profile)

Direct link to this comment:https://nl.mathworks.com/matlabcentral/answers/344545-how-can-i-reduce-the-computation-time-of-this-matrix-multiplication-like-calculation#comment_461331

## Stephen Cobeldick (view profile)

Direct link to this comment:https://nl.mathworks.com/matlabcentral/answers/344545-how-can-i-reduce-the-computation-time-of-this-matrix-multiplication-like-calculation#comment_461333

Sign in to comment.