How can I reduce the computation time of this matrix multiplication like calculation?
20 vues (au cours des 30 derniers jours)
Afficher commentaires plus anciens
Sinwoo Jeong
le 13 Juin 2017
Modifié(e) : Andrei Bobrov
le 15 Juin 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?
2 commentaires
Adam
le 13 Juin 2017
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!
Réponse acceptée
John D'Errico
le 13 Juin 2017
Modifié(e) : John D'Errico
le 13 Juin 2017
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.
2 commentaires
Andrei Bobrov
le 15 Juin 2017
Modifié(e) : Andrei Bobrov
le 15 Juin 2017
+1
Hi Sinwoo! Please accept this answer.
Plus de réponses (0)
Voir également
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!