Matrix chain multiplication problem: Determine the optimal parenthesization of a product of n matrices.
Matrix chain multiplication (or Matrix Chain Ordering Problem, MCOP) is an optimization problem that to find the most efficient way to multiply given sequence of matrices. The problem is not actually to perform the multiplications, but merely to decide the sequence of the matrix multiplications involved.
The matrix multiplication is associative as 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, or the efficiency. 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.
The idea is to break the problem into a set of related subproblems which group the given matrix in such a way that yields the lowest total cost.
Below is the recursive algorithm to find the minimum cost –
- Take the sequence of matrices and separate it into two subsequences.
- Find the minimum cost of multiplying out each subsequence.
- Add these costs together, and add in the cost of multiplying the two result matrices.
- Do this for each possible position at which the sequence of matrices can be split, and take the minimum over all of them.
For example, if we have four matrices ABCD, we compute the cost required to find each of (A)(BCD), (AB)(CD), and (ABC)(D), making recursive calls to find the minimum cost to compute ABC, AB, CD, and BCD. We then choose the best one. Better still, this yields not only the minimum cost, but also demonstrates the best way of doing the multiplication.
Below is C++ and Java implementation of the idea:
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 |
#include <iostream> #include <climits> using namespace std; // Function to find the most efficient way to multiply // given sequence of matrices int MatrixChainMultiplication(int dims[], int i, int j) { // base case: one matrix if (j <= i + 1) return 0; // stores minimum number of scalar multiplications (i.e., cost) // needed to compute the matrix M[i+1]...M[j] = M[i..j] int min = INT_MAX; // take the minimum over each possible position at which the // sequence of matrices can be split /* (M[i+1]) x (M[i+2]..................M[j]) (M[i+1]M[i+2]) x (M[i+3.............M[j]) ... ... (M[i+1]M[i+2]............M[j-1]) x (M[j]) */ for (int k = i + 1; k <= j - 1; k++) { // recurse for M[i+1]..M[k] to get a i x k matrix int cost = MatrixChainMultiplication(dims, i, k); // recurse for M[k+1]..M[j] to get a k x j matrix cost += MatrixChainMultiplication(dims, k, j); // cost to multiply two (i x k) and (k x j) matrix cost += dims[i] * dims[k] * dims[j]; if (cost < min) min = cost; } // return min cost to multiply M[j+1]..M[j] return min; } // Matrix Chain Multiplication Problem int main() { // Matrix M[i] has dimension dims[i-1] x dims[i] for i = 1..n // input is 10 × 30 matrix, 30 × 5 matrix, 5 × 60 matrix int dims[] = { 10, 30, 5, 60 }; int n = sizeof(dims) / sizeof(dims[0]); cout << "Minimum cost is " << MatrixChainMultiplication(dims, 0, n - 1); return 0; } |
Output:
Minimum cost is 4500
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 |
class MatrixChainMultiplication { // Function to find the most efficient way to multiply // given sequence of matrices public static int MatrixChainMultiplication(int[] dims, int i, int j) { // base case: one matrix if (j <= i + 1) { return 0; } // stores minimum number of scalar multiplications (i.e., cost) // needed to compute the matrix M[i+1]...M[j] = M[i..j] int min = Integer.MAX_VALUE; // take the minimum over each possible position at which the // sequence of matrices can be split /* (M[i+1]) x (M[i+2]..................M[j]) (M[i+1]M[i+2]) x (M[i+3.............M[j]) ... ... (M[i+1]M[i+2]............M[j-1]) x (M[j]) */ for (int k = i + 1; k <= j - 1; k++) { // recurse for M[i+1]..M[k] to get a i x k matrix int cost = MatrixChainMultiplication(dims, i, k); // recurse for M[k+1]..M[j] to get a k x j matrix cost += MatrixChainMultiplication(dims, k, j); // cost to multiply two (i x k) and (k x j) matrix cost += dims[i] * dims[k] * dims[j]; if (cost < min) { min = cost; } } // return min cost to multiply M[j+1]..M[j] return min; } // main function public static void main(String[] args) { // Matrix M[i] has dimension dims[i-1] x dims[i] for i = 1..n // input is 10 × 30 matrix, 30 × 5 matrix, 5 × 60 matrix int[] dims = { 10, 30, 5, 60 }; System.out.print("Minimum cost is " + MatrixChainMultiplication(dims, 0, dims.length - 1)); } } |
Output:
Minimum cost is 4500
The time complexity of above solution is exponential as we’re doing a lot of redundant work. For example, for matrix ABCD we will make a recursive call to find the best cost for computing both ABC and AB. But finding the best cost for computing ABC also requires finding the best cost for AB. As the recursion grows deeper, more and more of this type of unnecessary repetition occurs. The idea is to use memoization. Now each time we compute the minimum cost needed to multiply out a specific subsequence, we save it. If we are ever asked to compute it again, we simply give the saved answer, and do not recompute it.
Memoized C++/Java implementation –
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 |
#include <iostream> #include <climits> using namespace std; #define MAX 10 // lookup table to store the solution to already computed // sub-problems int lookup[MAX][MAX]; // Function to find the most efficient way to multiply // given sequence of matrices int MatrixChainMultiplication(int dims[], int i, int j) { // base case: one matrix if (j <= i + 1) return 0; // stores minimum number of scalar multiplications (i.e., cost) // needed to compute the matrix M[i+1]...M[j] = M[i..j] int min = INT_MAX; // if sub-problem is seen for the first time, solve it and // store its result in a lookup table if (lookup[i][j] == 0) { // take the minimum over each possible position at which the // sequence of matrices can be split /* (M[i+1]) x (M[i+2]..................M[j]) (M[i+1]M[i+2]) x (M[i+3.............M[j]) ... ... (M[i+1]M[i+2]............M[j-1]) x (M[j]) */ for (int k = i + 1; k <= j - 1; k++) { // recurse for M[i+1]..M[k] to get a i x k matrix int cost = MatrixChainMultiplication(dims, i, k); // recurse for M[k+1]..M[j] to get a k x j matrix cost += MatrixChainMultiplication(dims, k, j); // cost to multiply two (i x k) and (k x j) matrix cost += dims[i] * dims[k] * dims[j]; if (cost < min) min = cost; } lookup[i][j] = min; } // return min cost to multiply M[j+1]..M[j] return lookup[i][j]; } // Matrix Chain Multiplication Problem int main() { // Matrix M[i] has dimension dims[i-1] x dims[i] for i = 1..n // input is 10 x 30 matrix, 30 x 5 matrix, 5 x 60 matrix int dims[] = { 10, 30, 5, 60 }; int n = sizeof(dims) / sizeof(dims[0]); cout << "Minimum cost is " << MatrixChainMultiplication(dims, 0, n - 1); return 0; } |
Output:
Minimum cost is 4500
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 |
class MatrixChainMultiplication { // Function to find the most efficient way to multiply // given sequence of matrices public static int MatrixChainMultiplication(int dims[], int i, int j, int[][] T) { // base case: one matrix if (j <= i + 1) { return 0; } // stores minimum number of scalar multiplications (i.e., cost) // needed to compute the matrix M[i+1]...M[j] = M[i..j] int min = Integer.MAX_VALUE; // if sub-problem is seen for the first time, solve it and // store its result in a lookup table if (T[i][j] == 0) { // take the minimum over each possible position at which the // sequence of matrices can be split /* (M[i+1]) x (M[i+2]..................M[j]) (M[i+1]M[i+2]) x (M[i+3.............M[j]) ... ... (M[i+1]M[i+2]............M[j-1]) x (M[j]) */ for (int k = i + 1; k <= j - 1; k++) { // recurse for M[i+1]..M[k] to get a i x k matrix int cost = MatrixChainMultiplication(dims, i, k, T); // recurse for M[k+1]..M[j] to get a k x j matrix cost += MatrixChainMultiplication(dims, k, j, T); // cost to multiply two (i x k) and (k x j) matrix cost += dims[i] * dims[k] * dims[j]; if (cost < min) min = cost; } T[i][j] = min; } // return min cost to multiply M[j+1]..M[j] return T[i][j]; } // main function public static void main(String[] args) { // Matrix M[i] has dimension dims[i-1] x dims[i] for i = 1..n // input is 10 x 30 matrix, 30 x 5 matrix, 5 x 60 matrix int[] dims = { 10, 30, 5, 60 }; // lookup table to store the solution to already computed // sub-problems int[][] T = new int[dims.length][dims.length]; System.out.print("Minimum cost is " + MatrixChainMultiplication(dims, 0, dims.length - 1, T)); } } |
Output:
Minimum cost is 4500
The time complexity of above solution is O(n3) and auxiliary space used by the program is O(1).
The following bottom-up approach computes, for each 2 <= k <= n, the minimum costs of all subsequences of length k, using the costs of smaller subsequences already computed. It has the same asymptotic runtime and requires no recursion.
Below is C++ and Java implementation of the idea:
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 |
#include <iostream> #include <climits> using namespace std; // Function to find the most efficient way to multiply // given sequence of matrices int MatrixChainMultiplication(int dims[], int n) { // c[i,j] = Minimum number of scalar multiplications (i.e., cost) // needed to compute the matrix M[i]M[i+1]...M[j] = M[i..j] // The cost is zero when multiplying one matrix int c[n + 1][n + 1]; for (int i = 1; i <= n; i++) c[i][i] = 0; for (int len = 2; len <= n; len++) // Subsequence lengths { for (int i = 1; i <= n - len + 1; i++) { int j = i + len - 1; c[i][j] = INT_MAX; for (int k = i; j < n && k <= j - 1; k++) { int cost = c[i][k] + c[k + 1][j] + dims[i - 1]*dims[k]*dims[j]; if (cost < c[i][j]) c[i][j] = cost; } } } return c[1][n - 1]; } // Matrix Chain Multiplication Problem int main() { // Matrix M[i] has dimension dims[i-1] x dims[i] for i = 1..n // input is 10 x 30 matrix, 30 x 5 matrix, 5 x 60 matrix int dims[] = { 10, 30, 5, 60 }; int n = sizeof(dims) / sizeof(dims[0]); cout << "Minimum cost is " << MatrixChainMultiplication(dims, n); return 0; } |
Output:
Minimum cost is 4500
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 |
class MatrixChainMultiplication { // Function to find the most efficient way to multiply // given sequence of matrices public static int matrixChainMultiplication(int[] dims) { int n = dims.length; // c[i,j] = minimum number of scalar multiplications (i.e., cost) // needed to compute the matrix M[i]M[i+1]...M[j] = M[i..j] // The cost is zero when multiplying one matrix int[][] c = new int[n + 1][n + 1]; for (int len = 2; len <= n; len++) // Subsequence lengths { for (int i = 1; i <= n - len + 1; i++) { int j = i + len - 1; c[i][j] = Integer.MAX_VALUE; for (int k = i; j < n && k <= j - 1; k++) { int cost = c[i][k] + c[k + 1][j] + dims[i - 1] * dims[k] * dims[j]; if (cost < c[i][j]) { c[i][j] = cost; } } } } return c[1][n - 1]; } // main function public static void main(String[] args) { // Matrix M[i] has dimension dims[i-1] x dims[i] for i = 1..n // input is 10 x 30 matrix, 30 x 5 matrix, 5 x 60 matrix int[] dims = { 10, 30, 5, 60 }; System.out.print("Minimum cost is " + matrixChainMultiplication(dims)); } } |
Output:
Minimum cost is 4500
Source: https://en.wikipedia.org/wiki/Matrix_chain_multiplication
(1 votes, average: 5.00 out of 5)
Loading...
Thanks for reading.
Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂
Leave a Reply
Great problem!
Hi, how is the time complexity for the DP solution N^3. Could you please explain?
Thanks Anshul for sharing your concerns. The complexity is O(n3) as MatrixChainMultiplication() function can be called for any combination of i and j (total n2 combinations) and each function call takes linear time. Hope you’re clear now.