File Exchange

image thumbnail

mmtimes: matrix chain product

version 1.5 (2.81 KB) by

Return matrix chain product P = M1*M2* ... *Mn

2 Downloads

Updated

View License

Because the matrix multiplication is associative; the product can be carried with different order, leading to the same result up to round-off error, MMTIMES usings "optimal" order of binary product to reduce the computational effort (probably accuracy is also improved)

The function assumes the cost of the product of (m x n) with (n x p) matrices is (m*n*p). This assumption is typically true for full matrix.

Comments and Ratings (4)

Bruno Luong

Bruno Luong (view profile)

Dear Derek,
Great educational writing, I enjoy reading it a lot.
Yes, the complexity of the implemented code is not optimal. It's still perfectly alright for product of less than 10 matrices, which is sufficient in most of the practical use. When I have time I'll take a look at methods based on non-overlapping polygonal partition.

Dear Bruno,

Great stuff.

I have found that most mathematicians and 'numerical' people do not know that the <<complexity>> of matrix chain multiplication is not associative. Here is a Matlab exercise I gave to students 5 years ago to demonstrate this point:

http://www.scribd.com/derekroconnor4276

or

http://www.scribd.com/doc/36488330/Matrix-Chain-Multiplication

My mathematical friends liked this exercise and were very impressed that the solution to the optimum ordering involved Catalan Numbers. Also, they pointed out that these numbers did not come from Catalonia.

I agree with Ged Ridgway's comments and thank him for the pointer to a more efficient algorithm.

Derek O'Connor

Donard, Co Wicklow, Ireland.

Ged Ridgway

Ged Ridgway (view profile)

Ged Ridgway

Ged Ridgway (view profile)

I'm glad someone has implemented this. Two comments:

Apparently an O(N*log(N)) algorithm is available:
http://en.wikipedia.org/wiki/Matrix_chain_multiplication#An_Even_More_Efficient_Algorithm
though I don't know how this compares to the current O(N^3) one for typical values of N (e.g. the constants could make N*log(N) worse until N gets above a certain level).

More importantly (for me, anyway), I think the computation of the ordering should be a separate function, and a set ordering should then be usable in a multiplication function. E.g. if I have some code which repeatedly computes a chain multiplication in a loop, where the matrices' sizes are always the same and are known in advance, but their values vary, then much better than using mmtimes(A,B,C,...) would be to find the correct ordering first, and then hard-code that ordering in the loop. Similarly, if their sizes are constant but not known in advance, then a two-function division of labour would allow the ordering to be computed on the first iteration of the loop, and then reused without recomputation in successive iterations.

Updates

1.5

Update, optimal order can be input/output according to Ged Ridgway's suggestion

1.3

Treat the case of scalar matrices

1.1

quicker top-down algorithm

MATLAB Release
MATLAB 7.10 (R2010a)

Download apps, toolboxes, and other File Exchange content using Add-On Explorer in MATLAB.

» Watch video