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

multiplying a list of matrices together

• To: mathgroup at smc.vnet.net
• Subject: [mg23503] multiplying a list of matrices together
• From: Wagner Truppel <wtruppel at uci.edu>
• Date: Tue, 16 May 2000 02:44:52 -0400 (EDT)
• Sender: owner-wri-mathgroup at wolfram.com

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