Re: Order of matrix multiplication

[Bernardo Sulzbach]

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.