Dynamic Programming - Matrix Chain Multiplication

Slide on "Matrix Chain Multiplication" as an example of "Dynamic Programming".

1. Md. Saidul Islam ~ Dynamic Programming ~ Chain Matrix Multiplication

2. In mathematics or computer science, Dynamic Programming is a method for solving complex problems by breaking them down into simpler sub-problems. So, Matrix chain multiplication is an ideal example that demonstrates utility of dynamic programming. Engineering applications often have to multiply a large chain of matrices with large dimensions, for example: 100 matrices of dimension 100×100. We can multiply this chain of matrices in many different ways, but we will go for that way which takes lower computations. Dynamic Programming and Chain Matrix Multiplication

3. For example, we are going to multiply 4 matrices: M 1 = 2 x 3 M 2 = 3 x 4 M 3 = 4 x 5 M 4 = 5 x 7 And we have conditions for multiplying matrices: We can multiply only two matrices at a time. When we go to multiply 2 matrices, the number of columns of 1 st matrix should be same as the number of rows of 2 nd matrix. Dynamic Programming of Chain Matrix Multiplication

4. M 1 = 2 x 3 M 2 = 3 x 4 M 3 = 4 x 5 M 4 = 5 x 7 ( M 1 M 2 )( M 3 M 4 ) = 220 (( M 1 M 2 ) M 3 ) M 4 = 134 M 1 ( M 2 ( M 3 M 4 ) = 266 ( M 1 ( M 2 M 3 ) M 4 = 160 M 1 (( M 2 M 3 ) M 4 ) = 207 We can multiply the chain of matrices by following those conditions in these ways: Numbers of the rightmost side is number of total scalar multiplication. So we have realized that we can reduce the number of total multiplication and this reduced time is a fact for a large chain of matrices.

5. Renaming matrices as M i and dimensions as P i - 1 x P i , we have got: M 1 = P x P 1 M 2 = P 1 x P 2 M 3 = P 2 x P 3 M 4 = P 3 x P 4 | | | M i = P i – 1 x P i Algorithm and Mechanism

6. We will use a formula: Where C i, j means M i to M j . i.e.: C 1, 4 means M 1 to M 4 . And we will use a variable 'k' as follows: M 1 | k=1 M 2 M 3 M 4 M 1 M 2 | k=2 M 3 M 4 M 1 M 2 M 3 | k=3 M 4

7. The thing we’re going to do is to apply above formula for every 'k' in the range 'i' to 'j' and pick the lowest value every step. C 1 , 4 = min ( C 1 , 1 + C 2 , 4 + P * P 1 * P 4 , C 1 , 2 + C 3 , 4 + P * P 2 * P 4 , C 1 , 3 + C 4 , 4 + P * P 3 * P 4 ) = min ( 207, 220, 134 ) = 134 C 2, 4 = min ( C 2 , 2 + C 3 , 4 + P 1 * P 2 * P 4 , C 2 , 3 + C 4 , 4 + P 1 * P 3 * P 4 ) = min ( 224, 165 ) = 165 C 1, 3 = min ( C 1 , 1 + C 2 , 3 + P * P 1 * P 3 , C 1 , 2 + C 3 , 3 + P * P 2 * P 3 ) = min ( 90, 64 ) = 64 C 1, 2 = P * P 1 * P 2 = 24 C 2, 3 = P 1 * P 2 * P 3 = 60 C 3, 4 = P 2 * P 3 * P 4 = 140

8. int Chain( int i, int j ) { int min = 10000, value, k; if( i == j ){ return 0; } else{ for( k = i; k < j; k++ ){ value = (Chain(i, k) + Chain(k + 1, j) + (dimensions[i-1] * dimensions[k ] * dimensions[j])); if( min > value ){ min = value; mat[i][j] = k ; } } } return min; } Pseudocode

9. int main(void) { int result, i; printf (" Enter number of matrices: "); scanf ("%d", &n); printf (" Enter dimensions : "); for( i = 0; i <= n; i++ ){ scanf ("%d", &dimensions[i]); } result = Chain(1, n); printf ("\ n Total number of multiplications: %d and \n", result); printf (" Multiplication order is: "); PrintOrder ( 1, n ); printf ("\n"); }

10. Input and Output in Console App

11. Thank You!