11
$\begingroup$

This question already has an answer here:

Consider this list of $2\times 2$ matrices:

list=RandomReal[{-2,2},{500,2,2}];

Now compare timings of Apply and FoldList for matrix multiplication:

t1=FoldList[Dot,list];//AbsoluteTiming
(* 0.000324, Null *)
t2=Apply[Dot,list];//AbsoluteTiming
(* 0.001526, Null *)

Clearly, as it should be, Last@t1==t2 returns True. I wonder why FoldList is 5 times faster than Apply although it does also compute the same matrix multiplication... Is it maybe because FoldList effectively only computes the Dot product of only two matrices to get the next element - whereas Apply maybe uses some partitioning?

There is some evidence for the latter, since

t3=Apply[Dot,Dot@@@Partition[list,20,20,1,{}]];//AbsoluteTiming
(* 0.000944, Null *)

achieves much better timing than the standard Apply, but is still a little bit slower than FoldList (it seems that 20 is kind of the optimal value for manually partitioning list in order to speed up Apply[Dot,...]).

$Version="10.0 for Linux x86 (64-bit) (December 4, 2014)"
(* actually, it is 10.0.2 *)

So, in brief:

  1. Am I right that FoldList is faster because it only computes Dot product between two matrices?
  2. Is there another way to achieve the output of FoldList but even faster?
$\endgroup$

marked as duplicate by Oleksandr R., MarcoB, m_goldberg, user9660, Mr.Wizard May 9 '16 at 9:07

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ Why not t3 = Fold[Dot, list]? $\endgroup$ – kglr Apr 8 '16 at 8:04
  • $\begingroup$ @kglr This is a nice alternative to the result for Apply. However, I also need the intermediate results of Dot between all previous matrices and the following one, as FoldList does. $\endgroup$ – Lukas Apr 8 '16 at 8:08
  • $\begingroup$ I am using version 10.0.2 on 64bit Linux (edited that into the question) $\endgroup$ – Lukas Apr 8 '16 at 8:11
  • 7
    $\begingroup$ Maybe some clue is in the relative sizes of the files produced when you execute Trace[Dot @@ list] >> "tr1.txt"; Trace[Fold[Dot, list]] >> "tr2.txt"; FoldList seems to know that it is only going to use the next $2\times2$ list at each step, but Dot carries the full list at each step $\endgroup$ – Jason B. Apr 8 '16 at 8:27
  • 4
    $\begingroup$ Related: (83072), (83412) $\endgroup$ – Mr.Wizard May 6 '16 at 1:33
6
$\begingroup$

The answer is as you suspect - when you evaluate Dot[m1, m2, m3, m4, m5, ......m1000] the process is something like this:

  1. Look at the input: Dot[m1, m2, m3, m4, m5, ......m1000]
  2. Evaluate the first matrix product, m12=m1.m2
  3. Look at the input: Dot[m12, m3, m4, m5, ......m1000]
  4. Evaluate the first matrix product, m123=m12.m3
  5. Look at the input: Dot[m123, m4, m5, ......m1000]

and so on. When you use Fold, the process is

  1. Look at the input Fold[ Dot, {m1, m2, m3, m4, m5, ......m1000]
  2. Evaluate m12 = m1.m2
  3. Evaluate m123 = m12.m3
  4. Evaluate m1234 = m123.m4

and so on. So you don't have to carry the whole list of matrices with you at each step, you only ask for the next element of the list of matrices. This is verified by evaluating:

Trace[Dot @@ list] >> "tracedot.txt";

The full result is 11MB, and uploaded here, but we can just look at the last few steps to see the process:

 HoldForm[{{-5.321520990180708*^61, 6.819103101378474*^62}, 
   {-2.114430818780517*^61, 2.7094738103263247*^62}} . {{-1.7819423969909707, 
   -1.6334482227548142}, {0.6782967903343957, -1.147772651519678}} . 
   {{1.9417458764159523, -0.6657483830965161}, {0.1976190389456658, 
   -1.5228205915198982}} . {{1.498197940123715, -0.6704111046106744}, 
   {1.9988680712366937, -1.2709354099712966}} . {{0.9483227326875721, 
   -0.9780900034931443}, {1.2872284244010022, 1.4851315661557898}} . 
   {{0.1761339992709079, -0.4328681525925324}, {-1.8705391562731704, 
   0.17175870343138833}}], HoldForm[{{5.5736401335123805*^62, 
   -6.957537147278919*^62}, {2.214606781188385*^62, 
   -2.7644786131938665*^62}} . {{1.9417458764159523, -0.6657483830965161}, 
   {0.1976190389456658, -1.5228205915198982}} . {{1.498197940123715, 
   -0.6704111046106744}, {1.9988680712366937, -1.2709354099712966}} . 
   {{0.9483227326875721, -0.9780900034931443}, {1.2872284244010022, 
   1.4851315661557898}} . {{0.1761339992709079, -0.4328681525925324}, 
   {-1.8705391562731704, 0.17175870343138833}}], 
 HoldForm[{{9.447650941400094*^62, 6.884438927293232*^62}, 
   {3.753889978530132*^62, 2.735434073217245*^62}} . {{1.498197940123715, 
   -0.6704111046106744}, {1.9988680712366937, -1.2709354099712966}} . 
   {{0.9483227326875721, -0.9780900034931443}, {1.2872284244010022, 
   1.4851315661557898}} . {{0.1761339992709079, -0.4328681525925324}, 
   {-1.8705391562731704, 0.17175870343138833}}], 
 HoldForm[{{2.7915536339558937*^63, -1.5083487314081891*^63}, 
   {1.1091842063211788*^63, -5.9932095523871395*^62}} . {{0.9483227326875721, 
   -0.9780900034931443}, {1.2872284244010022, 1.4851315661557898}} . 
   {{0.1761339992709079, -0.4328681525925324}, {-1.8705391562731704, 
   0.17175870343138833}}], HoldForm[{{7.057044096191614*^62, 
   -4.970487017372562*^63}, {2.804016286699628*^62, 
   -1.9749524531188776*^63}} . {{0.1761339992709079, -0.4328681525925324}, 
   {-1.8705391562731704, 0.17175870343138833}}], 
 HoldForm[{{9.421789131712158*^63, -1.15920136959471*^63}, 
  {3.74361415559633*^63, -4.6059220767264225*^62}}]}

The entire list of remaining matrices is carried through to each evaluation step. Compare this with

Trace[Fold[Dot, list]] >> "tracefolddot.txt";

which is only 93kb, uploaded here and essentially looks like

{{HoldForm[list], HoldForm[(* List of matrices here *)]}, 
 HoldForm[Fold[Dot, (*List of matrices here again *)]], 
 HoldForm[{{9.421789131712158*^63, -1.15920136959471*^63}, 
  {3.74361415559633*^63, -4.6059220767264225*^62}}]}

This carrying through of all the remaining matrices in the list is enough to account for the performance difference I think.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.