Re: multiplying a list of matrices together
- To: mathgroup at smc.vnet.net
- Subject: [mg23522] Re: [mg23503] multiplying a list of matrices together
- From: Jack Goldberg <jackgold at math.lsa.umich.edu>
- Date: Tue, 16 May 2000 22:29:54 -0400 (EDT)
- Sender: owner-wri-mathgroup at wolfram.com
Dave Wagner's book! Jack On Tue, 16 May 2000, Wagner Truppel wrote: > Hello, > > on a previous message someone asked how to multiply a list of > matrices together. Two solutions suggested were: > > MapThread[Dot, list, 0] > Dot@@list > > Both of these work, but I'd like to point out that Mathematica does > NOT choose the best ordering for the multiplications, thereby > unnecessarily spending too much computation time if the matrices > aren't all of the same dimensions. > > There's a standard dynamic programming algorithm to choose the order > in which to perform the multiplications so as to minimize the total > operation count. Any decent book on data structures and algorithms, > such as "Introduction to Algorithms" by Cormen, Leiserson and Rivest, > will have a description of the algorithm in question. I remember > seeing a Mathematica implementation once, but I can't remember where. > > Wagner >