Re: multiplying a list of matrices together
- To: mathgroup at smc.vnet.net
- Subject: [mg23535] Re: multiplying a list of matrices together
- From: "William F. Campbell" <valentin at wam.umd.edu>
- Date: Sat, 20 May 2000 03:10:15 -0400 (EDT)
- Organization: UMD Dept. of Meteorology
- References: <8fqqrr$h3k@smc.vnet.net>
- Sender: owner-wri-mathgroup at wolfram.com
> 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 It's in David Wagner's book Power Programming with Mathematica: The Kernel, page 168-174. Bill Campbell