Matrix multiplication speed-up trick on MATLAB

I was recently working on some code with Manchester University’s David McCormick.  Buried deep within this code was a function that was called many,many times…taking up a significant amount of overall run time.  We managed to speed up an important part of this function by almost a factor of two (on his machine) simply by inserting two brackets….a new personal record in overall application performance improvement per number of keystrokes.
The code in question is hugely complex, but the trick we used is really very simple.  Consider the following MATLAB code
>> a=rand(4000);
>> c=12.3;
>> tic;res1=c*a*a';toc
Elapsed time is 1.472930 seconds.
With the insertion of just two brackets, this runs quite a bit faster on my Ivy Bridge quad-core desktop.
>> tic;res2=c*(a*a');toc
Elapsed time is 0.907086 seconds.
So, what’s going on? Well, we think that in the first version of the code, MATLAB first calculates c*a to form a temporary matrix (let’s call it temp here) and then goes on to find temp*a’.  However, in the second version, we think that MATLAB calculates a*a’ first and in doing so it takes advantage of the fact that which is where we get the speedup.
Another demonstration of this phenomena can be seen as follows
>> a=rand(4000);
>> b=rand(4000);
>> tic;a*a';toc
Elapsed time is 0.887524 seconds.
>> tic;a*b;toc
Elapsed time is 1.473208 seconds.
>> tic;b*b';toc
Elapsed time is 0.966085 seconds.
Note that the symmetric matrix-matrix multiplications are faster than the general, non-symmetric one.
- Full Post