
From:  Bernardo Sulzbach 
Subject:  Re: Order of matrix multiplication 
Date:  Mon, 12 Sep 2016 18:05:26 0300 
Useragent:  Mozilla/5.0 (X11; Linux x86_64; rv:45.0) Gecko/20100101 Thunderbird/45.2.0 
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 wellknown 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.
[Prev in Thread]  Current Thread  [Next in Thread] 