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


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 4 March 2019.
HTML page formatted Wed Mar 13 12:42:46 2019.

Cite this as:
Sandeep Kumar Shukla, "matrix-chain multiplication problem", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed. 4 March 2019. (accessed TODAY) Available from: https://www.nist.gov/dads/HTML/matrxchnmltp.html