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