- DAA - Discussion
- DAA - Useful Resources
- DAA - Quick Guide
- DAA - Hill Climbing Algorithm
- NP Hard & NP-Complete Classes
- DAA - Cook’s Theorem
- DAA - P and NP Class
- DAA - Vertex Cover
- DAA - Max Cliques
- Deterministic vs. Nondeterministic Computations
- DAA - Sublist Search
- DAA - Fibonacci Search
- DAA - Exponential Search
- DAA - Jump Search
- DAA - Interpolation Search
- DAA - Binary Search
- DAA - Linear Search
- Searching Techniques Introduction
- DAA - Radix Sort
- DAA - Counting Sort
- DAA - Bucket Sort
- DAA - Heap Sort
- DAA - Shell Sort
- DAA - Selection Sort
- DAA - Insertion Sort
- DAA - Bubble Sort
- DAA - Extract Method
- DAA - Heapify Method
- DAA - Insert Method
- DAA - Binary Heap
- Optimal Cost Binary Search Trees
- DAA - Multistage Graph
- DAA - Shortest Paths
- DAA - Spanning Tree
- Travelling Salesperson Approximation Algorithm
- Set Cover Problem
- Vertex Cover Problem
- Approximation Algorithms
- Fisher-Yates Shuffle
- Karger’s Minimum Cut
- Randomized Quick Sort
- Randomized Algorithms
- Travelling Salesman Problem | Dynamic Programming
- Longest Common Subsequence
- DAA - 0-1 Knapsack
- Floyd Warshall Algorithm
- Matrix Chain Multiplication
- DAA - Dynamic Programming
- DAA - Optimal Merge Pattern
- DAA - Job Sequencing with Deadline
- DAA - Fractional Knapsack
- Map Colouring Algorithm
- Dijkstra’s Shortest Path Algorithm
- Kruskal’s Minimal Spanning Tree
- Travelling Salesman Problem
- DAA - Greedy Method
- Towers of Hanoi
- Karatsuba Algorithm
- Strassen’s Matrix Multiplication
- DAA - Binary Search
- DAA - Merge Sort
- DAA - Max-Min Problem
- DAA - Divide & Conquer
- DAA - Space Complexities
- Master’s Theorem
- Time Complexity
- Asymptotic Notations & Apriori Analysis
- DAA - Methodology of Analysis
- DAA - Analysis of Algorithms
- DAA - Introduction
- Home
Selected Reading
- Who is Who
- Computer Glossary
- HR Interview Questions
- Effective Resume Writing
- Questions and Answers
- UPSC IAS Exams Notes
Design and Analysis - Matrix Chain Multippcation
Matrix Chain Multippcation is an algorithm that is appped to determine the lowest cost way for multiplying matrices. The actual multippcation is done using the standard way of multiplying the matrices, i.e., it follows the basic rule that the number of rows in one matrix must be equal to the number of columns in another matrix. Hence, multiple scalar multippcations must be done to achieve the product.
To brief it further, consider matrices A, B, C, and D, to be multipped; hence, the multippcation is done using the standard matrix multippcation. There are multiple combinations of the matrices found while using the standard approach since matrix multippcation is associative. For instance, there are five ways to multiply the four matrices given above −
(A(B(CD)))
(A((BC)D))
((AB)(CD))
((A(BC))D)
(((AB)C)D)
Now, if the size of matrices A, B, C, and D are l × m, m × n, n × p, p × q respectively, then the number of scalar multippcations performed will be lmnpq. But the cost of the matrices change based on the rows and columns present in it. Suppose, the values of l, m, n, p, q are 5, 10, 15, 20, 25 respectively, the cost of (A(B(CD))) is 5 × 100 × 25 = 12,500; however, the cost of (A((BC)D)) is 10 × 25 × 37 = 9,250.
So, dynamic programming approach of the matrix chain multippcation is adopted in order to find the combination with the lowest cost.
Matrix Chain Multippcation Algorithm
Matrix chain multippcation algorithm is only appped to find the minimum cost way to multiply a sequence of matrices. Therefore, the input taken by the algorithm is the sequence of matrices while the output achieved is the lowest cost parenthesization.
Algorithm
Count the number of parenthesizations. Find the number of ways in which the input matrices can be multipped using the formulae −
$$P(n)=left{egin{matrix} 1 & if: n=1\ sum_{k=1}^{n-1} P(k)P(n-k)& if: ngeq 2\ end{matrix} ight.$$
(or)
$$P(n)=left{egin{matrix} frac{2(n-1)C_{n-1}}{n} & if: ngeq 2 \ 1 & if: n= 1\ end{matrix} ight.$$
Once the parenthesization is done, the optimal substructure must be devised as the first step of dynamic programming approach so the final product achieved is optimal. In matrix chain multippcation, the optimal substructure is found by spaniding the sequence of matrices A[i….j] into two parts A[i,k] and A[k+1,j]. It must be ensured that the parts are spanided in such a way that optimal solution is achieved.
Using the formula, $C[i,j]=left{egin{matrix} 0 & if : i=j\ displaystyle min_{ ileq k< j}egin{cases} C [i,k]+C[k+1,j]+d_{i-1}d_{k}d_{j} end{cases} &if : i< j \ end{matrix} ight.$ find the lowest cost parenthesization of the sequence of matrices by constructing cost tables and corresponding k values table.
Once the lowest cost is found, print the corresponding parenthesization as the output.
Pseudocode
Pseudocode to find the lowest cost of all the possible parenthesizations −
MATRIX-CHAIN-MULTIPLICATION(p) n = p.length ─ 1 let m[1…n, 1…n] and s[1…n ─ 1, 2…n] be new matrices for i = 1 to n m[i, i] = 0 for l = 2 to n // l is the chain length for i = 1 to n - l + 1 j = i + l - 1 m[i, j] = ∞ for k = i to j - 1 q = m[i, k] + m[k + 1, j] + pi-1pkpj if q < m[i, j] m[i, j] = q s[i, j] = k return m and s
Pseudocode to print the optimal output parenthesization −
PRINT-OPTIMAL-OUTPUT(s, i, j ) if i == j print “A”i else print “(” PRINT-OPTIMAL-OUTPUT(s, i, s[i, j]) PRINT-OPTIMAL-OUTPUT(s, s[i, j] + 1, j) print “)”
Example
The apppcation of dynamic programming formula is spghtly different from the theory; to understand it better let us look at few examples below.
A sequence of matrices A, B, C, D with dimensions 5 × 10, 10 × 15, 15 × 20, 20 × 25 are set to be multipped. Find the lowest cost parenthesization to multiply the given matrices using matrix chain multippcation.
Solution
Given matrices and their corresponding dimensions are −
A5×10×B10×15×C15×20×D20×25
Find the count of parenthesization of the 4 matrices, i.e. n = 4.
Using the formula, $Pleft ( n ight )=left{egin{matrix} 1 & if: n=1\ sum_{k=1}^{n-1}P(k)P(n-k) & if: ngeq 2 \ end{matrix} ight.$
Since n = 4 ≥ 2, apply the second case of the formula −
$$Pleft ( n ight )=sum_{k=1}^{n-1}P(k)P(n-k)$$
$$Pleft ( 4 ight )=sum_{k=1}^{3}P(k)P(4-k)$$
$$Pleft ( 4 ight )=P(1)P(3)+P(2)P(2)+P(3)P(1)$$
If P(1) = 1 and P(2) is also equal to 1, P(4) will be calculated based on the P(3) value. Therefore, P(3) needs to determined first.
$$Pleft ( 3 ight )=P(1)P(2)+P(2)P(1)$$
$$=1+1=2$$
Therefore,
$$Pleft ( 4 ight )=P(1)P(3)+P(2)P(2)+P(3)P(1)$$
$$=2+1+2=5$$
Among these 5 combinations of parenthesis, the matrix chain multippcatiion algorithm must find the lowest cost parenthesis.
Step 1
The table above is known as a cost table, where all the cost values calculated from the different combinations of parenthesis are stored.
Another table is also created to store the k values obtained at the minimum cost of each combination.
Step 2
Applying the dynamic programming approach formula find the costs of various parenthesizations,
$$C[i,j]=left{egin{matrix} 0 & if : i=j\ displaystyle min_{ ileq k< j}egin{cases} C [i,k]+Cleft [ k+1,j ight ]+d_{i-1}d_{k}d_{j} end{cases} &if : i< j \ end{matrix} ight.$$
$Cleft [ 1,1 ight ]=0$
$Cleft [ 2,2 ight ]=0$
$Cleft [ 3,3 ight ]=0$
$Cleft [ 4,4 ight ]=0$
Step 3
Applying the dynamic approach formula only in the upper triangular values of the cost table, since i < j always.
$C[1,2]=displaystyle min_{ 1leq k< 2}egin{Bmatrix} C[1,1]+C[2,2]+d_{0}d_{1}d_{2} end{Bmatrix}$
$C[1,2]=0+0+left ( 5 imes 10 imes 15 ight )$
$C[1,2]=750$
$C[2,3]=displaystyle min_{ 2leq k< 3}egin{Bmatrix} C[2,2]+C[3,3]+d_{1}d_{2}d_{3} end{Bmatrix}$
$C[2,3]=0+0+left ( 10 imes 15 imes 20 ight )$
$C[2,3]=3000$
$C[3,4]=displaystyle min_{ 3leq k< 4}egin{Bmatrix} C[3,3]+C[4,4]+d_{2}d_{3}d_{4} end{Bmatrix}$
$C[3,4]=0+0+left ( 15 imes 20 imes 25 ight )$
$C[3,4]=7500$
Step 4
Find the values of [1, 3] and [2, 4] in this step. The cost table is always filled diagonally step-wise.
$C[2,4]=displaystyle min_{ 2leq k< 4}egin{Bmatrix} C[2,2]+C[3,4]+d_{1}d_{2}d_{4},C[2,3] +C[4,4]+d_{1}d_{3}d_{4}end{Bmatrix}$
$C[2,4]=displaystyle minleft{ ( 0 + 7500 + (10 imes 15 imes 20)), (3000 + 5000) ight}$
$C[2,4]=8000$
$C[1,3]=displaystyle min_{ 1leq k< 3}egin{Bmatrix} C[1,1]+C[2,3]+d_{0}d_{1}d_{3},C[1,2] +C[3,3]+d_{0}d_{2}d_{3}end{Bmatrix}$
$C[1,3]=minleft{ ( 0 + 3000 + 1000), (1500+0+750) ight}$
$C[1,3]=2250$
Step 5
Now compute the final element of the cost table to compare the lowest cost parenthesization.
$C[1,4]=displaystyle min_{ 1leq k< 4}egin{Bmatrix} C[1,1]+C[2,4]+d_{0}d_{1}d_{4},C[1,2] +C[3,4]+d_{1}d_{2}d_{4},C[1,3]+C[4,4] +d_{1}d_{3}d_{4}end{Bmatrix}$
$C[1,4]=minleft{0+8000+1250,750+7500+1875,2200+0+2500 ight}$
$C[1,4]=4700$
Now that all the values in cost table are computed, the final step is to parethesize the sequence of matrices. For that, k table needs to be constructed with the minimum value of ‘k’ corresponding to every parenthesis.
Parenthesization
Based on the lowest cost values from the cost table and their corresponding k values, let us add parenthesis on the sequence of matrices.
The lowest cost value at [1, 4] is achieved when k = 3, therefore, the first parenthesization must be done at 3.
(ABC)(D)
The lowest cost value at [1, 3] is achieved when k = 2, therefore the next parenthesization is done at 2.
((AB)C)(D)
The lowest cost value at [1, 2] is achieved when k = 1, therefore the next parenthesization is done at 1. But the parenthesization needs at least two matrices to be multipped so we do not spanide further.
((AB)(C))(D)
Since, the sequence cannot be parenthesized further, the final solution of matrix chain multippcation is ((AB)C)(D).
Example
Following is the final implementation of Matrix Chain Multippcation Algorithm to calculate the minimum number of ways several matrices can be multipped using dynamic programming −
#include <stdio.h> #include <string.h> #define INT_MAX 999999 int mc[50][50]; int min(int a, int b){ if(a < b) return a; else return b; } int DynamicProgramming(int c[], int i, int j){ if (i == j) { return 0; } if (mc[i][j] != -1) { return mc[i][j]; } mc[i][j] = INT_MAX; for (int k = i; k < j; k++) { mc[i][j] = min(mc[i][j], DynamicProgramming(c, i, k) + DynamicProgramming(c, k + 1, j) + c[i - 1] * c[k] * c[j]); } return mc[i][j]; } int Matrix(int c[], int n){ int i = 1, j = n - 1; return DynamicProgramming(c, i, j); } int main(){ int arr[] = { 23, 26, 27, 20 }; int n = sizeof(arr) / sizeof(arr[0]); memset(mc, -1, sizeof mc); printf("Minimum number of multippcations is %d", Matrix(arr, n)); }
Output
Minimum number of multippcations is 26000
#include <bits/stdc++.h> using namespace std; int mc[50][50]; int DynamicProgramming(int* c, int i, int j){ if (i == j) { return 0; } if (mc[i][j] != -1) { return mc[i][j]; } mc[i][j] = INT_MAX; for (int k = i; k < j; k++) { mc[i][j] = min(mc[i][j], DynamicProgramming(c, i, k) + DynamicProgramming(c, k + 1, j) + c[i - 1] * c[k] * c[j]); } return mc[i][j]; } int Matrix(int* c, int n){ int i = 1, j = n - 1; return DynamicProgramming(c, i, j); } int main(){ int arr[] = { 23, 26, 27, 20 }; int n = sizeof(arr) / sizeof(arr[0]); memset(mc, -1, sizeof mc); cout << "Minimum number of multippcations is " << Matrix(arr, n); }
Output
Minimum number of multippcations is 26000
import java.io.*; import java.util.*; pubpc class Main { static int[][] mc = new int[50][50]; pubpc static int DynamicProgramming(int c[], int i, int j) { if (i == j) { return 0; } if (mc[i][j] != -1) { return mc[i][j]; } mc[i][j] = Integer.MAX_VALUE; for (int k = i; k < j; k++) { mc[i][j] = Math.min(mc[i][j], DynamicProgramming(c, i, k) + DynamicProgramming(c, k + 1, j) + c[i - 1] * c[k] * c[j]); } return mc[i][j]; } pubpc static int Matrix(int c[], int n) { int i = 1, j = n - 1; return DynamicProgramming(c, i, j); } pubpc static void main(String args[]) { int arr[] = { 23, 26, 27, 20 }; int n = arr.length; for (int[] row : mc) Arrays.fill(row, -1); System.out.println("Minimum number of multippcations is " + Matrix(arr, n)); } }
Output
Minimum number of multippcations is 26000
mc = [[-1 for n in range(50)] for m in range(50)] def DynamicProgramming(c, i, j): if (i == j): return 0 if (mc[i][j] != -1): return mc[i][j] mc[i][j] = 999999 for k in range (i, j): mc[i][j] = min(mc[i][j], DynamicProgramming(c, i, k) + DynamicProgramming(c, k + 1, j) + c[i - 1] * c[k] * c[j]); return mc[i][j] def Matrix(c, n): i = 1 j = n - 1 return DynamicProgramming(c, i, j); arr = [ 23, 26, 27, 20 ] n = len(arr) print("Minimum number of multippcations is ") print(Matrix(arr, n))
Output
Minimum number of multippcations is 26000Advertisements