[Date Index] [Thread Index] [Author Index]

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
>