# Why does partitioning increase Dot execution speed?

I have noticed that multiplying a list of matrices can be significantly sped up by partitioning the list, calculating the product of the partitions matrices, and then multiplying the results.

tab = Table[RandomReal[{0,1},{8,8}],{3960}];

F=Function[{m},
Dot @@ ((Dot @@ #)& /@ Partition[tab,m]) // AbsoluteTiming // First];

times = F /@ Divisors;
ListPlot[times,PlotRange->Full] In this example the computation time can be decreased by nearly two orders of magnitude by choosing the right partition size.

Can anybody explain this effect?

Edit: I think Simon Woods gave the correct explanation for numerical matrices. But the effect happens for symbolic matrices, too!

tab = Table[({{Symbol["a"<>#],Symbol["b"<>#]},{Symbol["c"<>#],Symbol["d"<>#]}})&[ToString[n]],{n,24}];

Dot @@ tab // AbsoluteTiming // First
(* 7.511497 *)

Dot @@ Dot @@@ Partition[tab,2] // AbsoluteTiming // First
(* 0.008224 *)

• I think with symbolic matrices you are just seeing an exponential increase in complexity with the number of matrices in the dot product - the timing is about the same for partitions of n and 24/n. The optimum partition size is probably around Sqrt[n]. – Simon Woods May 10 '15 at 19:55

This happens because of unpacking when the numbers exceed $MaxMachineNumber: fast = Dot @@@ Partition[tab, Divisors[]]; DeveloperPackedArrayQ /@ fast (* {True, True, True, True, True, True, True, True} *) Max[fast] <=$MaxMachineNumber
(* True *)

slow = Dot @@@ Partition[tab, Divisors[]];

DeveloperPackedArrayQ /@ slow
(* {False, False, False, False, False, False} *)

Max[slow] <= \$MaxMachineNumber
(* False *)


The performance is best for the largest partitions which do not overflow machine arithmetic.

• Thank you for your answer! I hope you don't mind, that I extended the question to symbolic matrices. – murphy May 10 '15 at 18:23