
From:  Nicholas Jankowski 
Subject:  Re: Order of matrix multiplication 
Date:  Mon, 12 Sep 2016 13:06:03 0400 
I noticed today that Octave always performs multiplication from left to right.
This is, as one could expect, properly documented:
 Builtin Function: mtimes (X1, X2, ...)
Return the matrix multiplication product of inputs.
This function and x * y are equivalent. If more arguments are
given, the multiplication is applied cumulatively from left to
right (...)
This is evidently not the best solution from a performance point of view if a multiplication substantially reduces the size of the product.
Locally, profiling
m * m * m * m * x
against
m * (m * (m * (m * x)));
when the size of m is [2048 2048] and the size of x is [2048 1] produces the following results
Took 9.752126 seconds when using the default order.
Took 0.035902 seconds when going from right to left.
Maximum difference is 0.000732422.
I may be oversimplifying the analysis of numerical error here, but I would say that the second solution introduces less error as the number of floatingpoint operations is much smaller.

Understanding that trying to determine the "best" order of matrix multiplication during execution may not be a trivial task, I still wonder why Octave approach is so naive.
Additionally, would there be any function out there which I could use instead of mtimes which performed some analysis on the dimensions of the input matrices and optimized the order of multiplication without requiring me to do it manually?
[Prev in Thread]  Current Thread  [Next in Thread] 