matrix_chain_dynamic, a C++ code which finds the cost of the most efficient ordering to use when multiplying a sequence of matrices, using dynamic programming.
We are given a sequence of n matrices of conformable dimensions. Matrix Ai has D(i) rows and D(i+1) columns. The product A1 * A2 * ... * An is to be computed. In terms of scalar multiplications, the cost of computing A(i) * A(i+1) is D(i) * D(i+1) * D(i+2). We may carry out the pairs of multiplication in any order we wish. The total cost of the computation will, in general, vary depending on the order in which we compute the individual matrix multiplications. The goal of the algorithm is simply to determine the cost of the most efficient ordering.
Given n matrices, there are (n-1)! possible orderings for the sequence of matrix multiplications. One approach to determining the minimum cost would be to consider each of these orderings, but this is considered a wasteful and inefficient approach for large values of n. The code given here depends instead on a dynamic programming approach. As such, it requires several n by n arrays in order to store intermediate information. Thus it needs n^2 space, and the algorithm takes on the order of n^3 operations to determine the result.
The information on this web page is distributed under the MIT license.
matrix_chain_dynamic is available in a C version and a C++ version and a Fortran90 version and a MATLAB version and an Octave version and a Python version.
change_dynamic, a C++ code which uses dynamic programming to solve the change making problem, which counts the number of ways a given sum can be formed using coins of various denominations.
football_dynamic, a C++ code which uses dynamic programming to count the ways of achieving a given score in football, respecting the order of events.
mxm, a C++ code which sets up a matrix multiplication problem A=B*C of arbitrary size, and compares the time required for IJK, IKJ, JIK, JKI, KIJ and KJI orderings of the loops.