Speed of matrix storage

If I have a matrix

 A=[A11 A12; A21 A22]

why is it faster in Matlab to store it like

 A=A11*[1 0; 0 0] + A12*[0 1; 0 0] + A21*[0 0; 1 0] +  A22*[0 0; 0 1];?

[Stephen23]

Are A11 A12 A21 A22 scalar numeric?

[dpb]

1. How did you time it to test the hypothesis?
2. Have you studied result with size of Aij?
3. If so for certain size A, I'd guess it would be owing to a particular implementation of the code parser and wouldn't necessarily hold for perpetuity. But, best guess is it's related to allocation order in the two; the latter can "see" the array size of the terms and may allocate that prior to the calculation whereas the former does a reallocation/concatenation of the elements.

[Philipp Metsch]

Yes, all components of A are scalars. I timed the code using tic and toc in a for loop to test not only one execution, but 1e6.

Answer 1

[Philip Borghesani]

Analyzing a snippet of code out of context has little value and often leads to improper conclusions. In this code creating a new matrix takes the majority of the time. I believe that the matrix operation is doing a better job of reusing the existing variable that is going out of scope. When attempting to find the fastest way to do something don't try to break it down line by line, look at a useful block of code and think about how to make that faster.

The fastest way to do this by far is with direct indexing and to reuse the matrix but that may not be representative of the final requirements:

 A_11=4;
 A_12=6;
 A_21=7;
 A_22=17;
  loops=1e6;
 tic;
 for i=1:loops 
    A3(2,2)=A_22;A3(2,1)=A_21;A3(1,2)=A_12;A3(1,1)=A_11;
 %    A3=[];
 end
 toc;

If the comment on the line A3=[] is removed and similar lines are added to the other loops then direct assignment seems to be half way between concatenation and the matrix operations.

The version of MATLAB used for testing this also make a significant difference. Micro optimizing based on the results of a command line or script test with one version of matlab is a particularly bad idea.

Answer 2

[dpb]

I can't reproduce the result...

metch.m
tic,B=[A A;A A];t1=toc;
tic,B=A*[1 0; 0 0] + A*[0 1; 0 0] + A*[0 0; 1 0] +  A*[0 0; 0 1];t2=toc;

>> N=100;
>> t=zeros(N,2);
>> for i=1:N,metch,t(i,:)=[t1 t2];end
>> [mean(t);std(t)]
ans =
   1.0e-04 *
    0.2349    0.2365
    0.1026    0.0276
>> mean(t)
ans =
 1.0e-04 *
  0.2349    0.2365
>> (ans(2)/ans(1)-1)*100
ans =
  0.6959
>>

While it's small (<1% difference on average), the second is longer than the first.

>>  sum(t(:,2)<t(:,1))
ans =
   1
>>

Only one case where the first didn't win...

ADDENDUM

What can't try here that may be the problem/cause might be the automatic singleton expansion in lastest revisions??? The above code only works without if the A are 2x2; I think the expansion would run for any compatible sizes maybe??? If that were the case, I'd not be surprised at all.

Answer 3

[Philipp Metsch]

In my case the code looks like this:

A_11=4;
A_12=6;
A_21=7;
A_22=17;

tic;
for i=1:1e6;
    A1=[A_11 A_12; A_21 A_22];
end;
toc;

tic;
for i=1:1e6;
    A2=A_11*[1 0; 0 0] + A_12*[0 1; 0 0] + A_21*[0 0; 1 0] + A_22*[0 0; 0 1];
end;
toc;

The result of tic/toc gives "Elapsed time is 1.697598 seconds." for the first loop and "Elapsed time is 0.098466 seconds." for the second loop. If I run the code with profiler on, the result is qualitatively the same.

I think this difference is quite dramatic, but I am not able to figure out where it comes from.

[James Tursa]

It could be simply how the parser is dealing with the two cases. In the first loop maybe concatenation is done for each iteration, whereas in the second loop maybe the parser pre-forms each 2x2 since there are only constants inside and then the only calculations done for each iteration are scalar multiplies and adds. Or something like that. And you may get different results depending on where this code is run. If run directly from the command line the first case might be faster, but if run from inside an m-file (where the parser can pre-calculate things) the second case might be faster.

[dpb]

From command line your above yields

Elapsed time is 0.819344 seconds.
Elapsed time is 3.773874 seconds.
>>

If I put it in a script or make a function--

>>  metch
Elapsed time is 0.795618 seconds.
Elapsed time is 0.145393 seconds.
>>

So the first isn't amenable to JIT optimizer it seems whereas the second is.

[per isakson]

Only The MathWorks knows!

The loop is kind of meaningless. A1 and A2 are overwritten a million times. Replacing them by A=zeros(2,2,N); gives a different result.