Code covered by the BSD License

### Highlights from mmtimes: matrix chain product

4.5
4.5 | 2 ratings Rate this file 1 Download (last 30 days) File Size: 2.81 KB File ID: #27950 Version: 1.5

# mmtimes: matrix chain product

### Bruno Luong (view profile)

19 Jun 2010 (Updated )

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

File Information
Description

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.

MATLAB release MATLAB 7.10 (R2010a)
Other requirements Matlab version that supports CELLFUN
27 Aug 2010 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.

Comment only
27 Aug 2010 Derek O'Connor

### Derek O'Connor (view profile)

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.

11 Aug 2010 Ged Ridgway

### Ged Ridgway (view profile)

11 Aug 2010 Ged Ridgway

### Ged Ridgway (view profile)

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.

Comment only
21 Jun 2010 1.1

quicker top-down algorithm

23 Jun 2010 1.3

Treat the case of scalar matrices

16 Aug 2010 1.5

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