Module McopSource

A problem instance is given as an array of integers, representing the dimensions of matrices. The product of matrices M1 : M[i,j] x M2[j,k] is specified by the array [|i; j; k|]. Thus, the multiplication of n matrices is represented by an array of length (n+1).

The solution is given as a binary tree of matrices. Only the shape of the binary tree matters, the 'a parameter is provided as a convenience for user to store custom information. Initially, the 'a is just an integer that represents the index of the matrix to multiply (the values grows from 0 to n-1).

This exception is raised when an empty problem is submitted, as it has no solution.

Map a solution to a user-chosen representation, to make it more convenient to interpret

Left-leaning product tree. This solution is naive solution, the dimensions are not even looked at so nothing is optimized. For benchmarking purposes.

Right-leaning product tree. This solution is naive solution, the dimensions are not even looked at so nothing is optimized. For benchmarking purposes.

An implementation of the algorithm described in "An O(n) algorithm for determining a near-optimal computation order of matrix chain products" by Francis Y. Chin. It gives an approximate solution in O(n) time that does less than 25% more operations that the optimal one (and much less in practice).

An implementation of the dynamic programming algorithm. It gives an optimal solution in O(n^3). A formal description can be found in "Introduction to Algorithms" by Cormen et al.