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.
Dan Hirschberg's example of using dynamic programming for matrix multiplication, including pseudocode.
If you have suggestions, corrections, or comments, please get in touch with Paul E. Black.
Entry modified 17 December 2004.
HTML page formatted Tue Dec 6 16:16:32 2011.
Cite this as:
Sandeep Kumar Shukla, "matrix-chain multiplication problem", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed., U.S. National Institute of Standards and Technology. 17 December 2004. (accessed TODAY) Available from: http://www.nist.gov/dads/HTML/matrxchnmltp.html