Matrix chain multiplication (or Matrix Chain Ordering Problem, MCOP) is an optimization problem that can be solved using dynamic programming. Given a sequence of matrices, the goal is to find the most efficient way to multiply these matrices. The problem is not actually to perform the multiplications, but merely to decide the sequence of the matrix multiplications involved.
This problem is also known as Matrix-Chain Multiplication Problem.
There are many options because matrix multiplication is associative. In other words, no matter how the product is parenthesized, the result obtained will remain the same. For example, for four matrices A, B, C, and D, we would have:
((AB)C)D = (A(BC))D = (AB)(CD) = A((BC)D) = A(B(CD)).
However, the order in which the product is parenthesized affects the number of simple arithmetic operations needed to compute the product, that is the computational complexity. For example, if A is a 10 × 30 matrix, B is a 30 × 5 matrix, and C is a 5 × 60 matrix, then
computing (AB)C needs (10×30×5) + (10×5×60) = 1500 + 3000 = 4500 operations, while
computing A(BC) needs (30×5×60) + (10×30×60) = 9000 + 18000 = 27000 operations.
Clearly, the first method is more efficient. With this information, the problem statement can be refined as "how to determine the optimal parenthesization of a product of n matrices?" Checking each possible parenthesization (brute force) would require a run-time that is exponential in the number of matrices, which is very slow and impractical for large n. A quicker solution to this problem can be achieved by breaking up the problem into a set of related subproblems. By solving subproblems once and reusing the solutions, the required run-time can be drastically reduced. This concept is known as dynamic programming.
package dp;
public class MatrixProductParenthesization {
public static void main(String[] args) {
int arr[] = {1, 2, 3, 4};
long startTime = System.nanoTime();
System.out.println(FindMatrixProduct(arr));
long endTime = System.nanoTime();
long totalTime = endTime - startTime;
System.out.println("Total Time (nanoseconds) : " + (totalTime));
}
private static int FindMatrixProduct(int[] arr) {
int n = arr.length;
int[][] dp=new int[n][n];
int i, j, k, L, q;
for (L=2; L<n; L++)
{
for (i=1; i<n-L+1; i++)
{
j = i+L-1;
dp[i][j] = Integer.MAX_VALUE;
for (k=i; k<=j-1; k++)
{
q = dp[i][k] + dp[k+1][j] + arr[i-1]*arr[k]*arr[j];
if (q < dp[i][j])
dp[i][j] = q;
}
}
}
return dp[1][n-1];
}
}
output:
18
Total Time (nanoseconds) : 266194
The time complexity of the above solution is O(n^3) and Space complexity is O(n^2).
