NIST

matrix-chain multiplication problem

(classic problem)

Definition: Given a sequence of matrices such that any matrix may be multiplied by the previous matrix, find the best association such that the result is obtained with the minimum number of arithmetic operations. One may use dynamic programming to find the best association.

Author: SKS

More information

Dan Hirschberg's example of using dynamic programming for matrix multiplication, including pseudocode.


Go to the Dictionary of Algorithms and Data Structures home page.

If you have suggestions, corrections, or comments, please get in touch with Paul Black.

Entry modified 17 December 2004.
HTML page formatted Mon Feb 2 13:10:39 2015.

Cite this as:
Sandeep Kumar Shukla, "matrix-chain multiplication problem", in Dictionary of Algorithms and Data Structures [online], Vreda Pieterse and Paul E. Black, eds. 17 December 2004. (accessed TODAY) Available from: http://www.nist.gov/dads/HTML/matrxchnmltp.html