How can I reduce the computation time of this matrix multiplication like calculation?

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?

[Adam]

I'm assuming you don't really mean you want to 'increase the computation time' as your title suggests. There are any number of increasingly creative ideas to do that!

[Stephen23]

"How can I increase the computation time"

pause(realmax)

Answer 1

[John D'Errico]

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]

Thank you so much for your perfect answer.

[Andrei Bobrov]

+1

Hi Sinwoo! Please accept this answer.