A question about the efficiency of matrix multiplication in MATLAB.

3 views (last 30 days)
Helu Yu on 9 Nov 2021
Commented: Helu Yu on 10 Nov 2021
If we have the following two matrices in MATLAB:
A=rand(100,100);
B=rand(100,1000);
Now we consider the following two cases of calculations:
(1) A*B, which is performed 10000 times:
tic
for k=1:10000
A*B;
end
toc
(2) A*B(:,1), A*B(:,2), ..., A*B(:,1000), each of which is performed 10000 times:
tic
for j=1:1000
b_j=B(:,j);
for k=1:10000
A*b_j;
end
end
toc
It is obvious that the total times of multiplication required in the two cases are the same. However, a comparison made in MATLAB indicates that the computational time used by case-1 is significantly less than that by case-2. Could someone please make some explanations or comments about this question?

Steven Lord on 9 Nov 2021
If you were going to the grocery store to pick up a bunch of items for dinner, which process would be more efficient?
1. Go to the grocery store, fill your shopping cart with all the items you need, buy them, and take them home.
2. Go to the grocery store, buy one item, take it home. Go to the grocery store, buy the second item on your list, take it home. Go to the grocery store, buy the third item on your list, take it home. etc.
Your first example calls the * operator 10,000 times. Your second calls it 1000*10,000 times. Sure, that second example is calling the function on smaller arrays, but the fact that in your second shopping process your grocery bag will be lighter each trip doesn't outweigh the extra trips between your house and the store.
Helu Yu on 10 Nov 2021
Thank you very much, your simple example enlightens me. But could you give me some theoretical explanations? Is it because that the matrix-vector operations performed in case-2 is achieved using the Level 2 Basic Linear Algebra Subprograms (BLAS), while the matrix- matrix operations performed in case-1 is achieved using the more efficient Level 3 BLAS?

Chris on 9 Nov 2021
Matlab was built to do matrix math first, with the highly optimized LAPACK library at its heart. That's what it's using for case 1. Matlab is not as optimized for iterating through loops.
Vectorized operations are faster than loops as well. If you need to apply the same set of operations to all elements of a multi-dimensional array, it is nearly always going to be faster if you can find a way to do it without loops. For example, the element-wise operators
.* ./ .^
and relational operators
< > <= >= == ~=
can operate on entire arrays without introducing loops, and are thus quite fast.
Helu Yu on 9 Nov 2021
Dear Chris, many thanks for your valuable explanation.