Re: Order of matrix multiplication

[Nicholas Jankowski]

On Mon, Sep 12, 2016 at 5:05 PM, Bernardo Sulzbach <address@hidden> wrote:

On 09/12/2016 04:54 PM, Nicholas Jankowski wrote:

On Mon, Sep 12, 2016 at 2:59 PM, Yu Liu <address@hidden> wrote:

FYI, numpy has a special function np.linalg.multi_dot to do this.
https://github.com/numpy/numpy/blob/b91e8d8f164731bb710cc1e5173cc8
ec3f8fadf5/numpy/linalg/linalg.py
Their code has very detailed explanation of the well-known algorithm.

definitely looks like something that could be adapted.  That said, I did
just recall that there is an existing bug waiting to have a patch tested
and committed for mtimes related to improperly flattening an ND array. So
if anyone starts looking to make changes it should take the current offered
patch into account: https://savannah.gnu.org/bugs/?47173

from that report it seems fixing mtimes was not the most trivial of tasks,
so 'tread with care'

numpy/linalg/linalg.py is a great resource. It seems to me definitely worth trying to perform such optimizations. Even if we in the end preserve mtimes (lack of) parenthesization for some reason, having another function which would figure out an optimal parenthesization by solving the matrix chain ordering problem (assuming it doesn't already exists around these parts) would be a nice thing.

I think it could definitely be a function of its own. See that the algorithm may introduce some noticeable overhead when determining how to best multiply the matrices while not giving anything back in return. Maybe mtimes docs should then point to this function saying that it does attempt to optimize parenthesization before multiplying the matrices. Also, if this was made into another function, the aforementioned ticked would not be an implementation blocking issue.

True. I personally like the idea of having it built into mtimes, since Octave's mtimes already handles n>2 unlike Matlab's mtimes.  Anything m = 2 would only have the overhead of evaluating a (if nargin > 2), and that may actually already be present. Anything n>2 is already octave only, so speed comparisons are really only against itself. i think the python code had a fast code path for n = 3, so if we can borrow that I think n>3 is the only place overhead would become a big concern. Would be interesting to see how much it would add.

Unfortunately mtimes isn't sitting as m-code (well, thankfully I guess, imagining how slow things would be otherwise) so it's not something I'm setup to play with.