Dynamic Programming Matrix Chain Multiplication

Introduction to Matrix Chain Multiplication algorithm with an example. Matrix Chain Products algorithm comes under Dynamic Programming concept. Done for the course Advanced Data Structures and Algorithms.

1. Dynamic Dynamic Programming: Matrix Chain Products By Krishnakoumar C M.Tech DS (I Year) Puducherry Technological University

2. What is Dynamic Programming? Dynamic Programming refers to simplifying a complicated problem by breaking it down into simpler sub-problems in a recursive manner. Dynamic Programming techniques: Simple Subproblems Subproblems Optimality Subproblem Overlap

3. Matrix Chain Product Matrix chain multiplication is an optimization problem concerning the most efficient way to multiply a given sequence of matrices The problem is not actually to perform the multiplications, but merely to decide the sequence of the matrix multiplications involved. 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.

4. Consider 2x3 matrices A, B, and C: We, can perform matrix Multiplication in the following ways: i ) (A x B) x C ii) A x (B x C) Note: Matrix Multiplication is Associative .

5. Matrix Multiplication Let us consider two matrices A and B: 2 x 3 3 x 2  

6. Matrix Multiplication Let us consider two matrices A and B of dimensions 2 x 3: 2 x 3 3 x 2 Condition for Matrix Multiplication  

7. Matrix Multiplication So, the product of two matrices A and B is given by:  

8. Matrix Multiplication So, the product of two matrices A and B is given by: 1 2 3 4 5 6 7 8 9 10 11 12  

9. Matrix Multiplication To calculate the number of multiplication operations required for a given matrix, we can use the below technique: 2 x 3 3 x 2 Total Number of Multiplication required = 2 x 3 x 2 = 12 operations  

10. Parenthesization Let us consider an example: A 1 x A 2 x A 3 2 3 3 4 4 2 d0 d1 d1 d2 d2 d3

11. Parenthesization Parenthesization of given matrices: A 1 x A 2 x A 3 2 3 3 4 4 2 d0 d1 d1 d2 d2 d3 ( A 1 x A 2 ) x A 3 A 1 x ( A 2 x A 3 )

12. Parenthesization Parenthesization of given matrices: A 1 x A 2 x A 3 2 3 3 4 4 2 d0 d1 d1 d2 d2 d3 ( A 1 x A 2 ) x A 3 A 1 x ( A 2 x A 3 )

13. Parenthesization ( A 1 x A 2 ) x A 3 2 3 3 4 4 2 Number of Operations: C[1, 2] = 2 x 3 x 4 = 24 C[3, 3] = 0 New Dimension: 2 x 4 4 x 2 Number of Operations: 2 x 4 x 2 = 16 Total Number of operations: 24 + 16 = 40 Multiplications General Notation for this operation: C[1, 2] + C[3, 3] + d + d 2 + d 3 = 40 ------------------------------ ( i )

14. Parenthesization Parenthesization of given matrices: A 1 x A 2 x A 3 2 3 3 4 4 2 d0 d1 d1 d2 d2 d3 ( A 1 x A 2 ) x A 3 A 1 x ( A 2 x A 3 )

15. Paranthesization A 1 x ( A 2 x A 3 ) 2 3 3 4 4 2 Number of Operations: C[1, 1] = 0 C[2, 3] = 3 x 4 x 2 = 24 New Dimension: 2 x 3 3 x 2 Number of Operations: 2 x 3 x 2 = 12 Total Number of operations: 24 + 12 = 38 Multiplications General Notation for this operation: C[1, 1] + C[2, 3] + d + d 1 + d 3 = 38 ------------------------------ (ii)

16. Parenthesization From Equation ( i ) and (ii): C[1, 2] + C[3, 3] + d + d 2 + d 3 = 40 C[1, 1] + C[2, 3] + d + d 1 + d 3 = 38 >

17. Parenthesization From Equation ( i ) and (ii): C[1, 2] + C[3, 3] + d + d 2 + d 3 = 40 C[1, 1] + C[2, 3] + d + d 1 + d 3 = 38 > This is the optimal solution among the two ways

18. Parenthesization From Equation ( i ) and (ii), we can derive the generalized form C[1, 2] + C[3, 3] + d + d 2 + d 3 = 40 C[1, 1] + C[2, 3] + d + d 1 + d 3 = 38 > C[ i , j] = min { C[ i , k] + C[k + 1, j] + d i-1 x d k x d j } I ≤ k < j

19. Parenthization The possible number of ways the given matrices can be parenthized using the below formula: Where: n – Number of matrices for multiplication  

20. Example Problem: Let us consider four matrices namely A 1 , A 2 , A 3 , and A 4 of dimensions d , d 1 , d 2 , d 3 , and d 4 respectively. Find the optimal matrix multiplication. A1 x A2 x A3 x A4 d0 d1 d1 d2 d2 d3 d3 d4 3 2 2 4 4 2 2 5 The number of possible ways the matrices can be parenthesized: Here, n = 4 = = = = 5. Hence there are 5 five possible ways of parenthesization .  

21. Example Problem The following are 5 different ways of parenthesization : A 1 X (A 2 X (A 3 X A 4 )) A 1 X ((A 2 X A 3 ) X A 4 ) (A 1 X A 2 ) X (A 3 X A 4 ) (A 1 X (A 2 X A 3 )) X A 4 ((A 1 X A 2 ) X A 3 ) X A 4

22. Example Problem Let us consider 2 tables to arrange the resultant cost and k-values. 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 i j k C i j

23. Example Problem Let us find the C[1, 2]:  C[ i , j] = min { C[ i , k] + C[k + 1, j] + d i-1 x d k x d j } I ≤ k < j C[1, 2] = min { C[1, 1] + C[2, 2] + d x d 1 x d 2 } 1 ≤ 1< 2 K = 1 = 0 + 0 + 3 x 2 x 4 = 24 24 1 Cost K value 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4

24. Example Problem Let us find the C[2, 3]:  C[ i , j] = min { C[ i , k] + C[k + 1, j] + d i-1 x d k x d j } I ≤ k < j C[2, 3] = min { C[2, 2] + C[3, 3] + d 1 x d 2 x d 3 } 2 ≤ 2< 3 K = 2 = 0 + 0 + 2 x 4 x 2 = 16 24 16 1 2 Cost K value 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4

25. Example Problem Let us find the C[3, 4]:  C[ i , j] = min { C[ i , k] + C[k + 1, j] + d i-1 x d k x d j } I ≤ k < j C[3, 4] = min { C[3, 3] + C[4, 4] + d 2 x d 3 x d 4 } 3 ≤ 3< 4 K = 3 = 0 + 0 + 4 x 2 x 5 = 40 24 16 40 1 2 3 Cost K value 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4

26. Example Problem Let us find the C[1, 3]:  C[ i , j] = min { C[ i , k] + C[k + 1, j] + d i-1 x d k x d j } I ≤ k < j C[1, 3] = min C[1, 1] + C[2, 3] + d x d 1 x d 3 = 0 + 16 + 3 x 2 x 2 = 28 C[1, 2] + C[3, 3] + d x d 2 x d 3 = 24 + 0 + 3 x 4 x 2 = 48 When, K = 2 24 28 16 40 1 1 2 3 Cost K value 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 When, K = 1 1 ≤ k < 3

27. Example Problem Let us find the C[2, 4]:  C[ i , j] = min { C[ i , k] + C[k + 1, j] + d i-1 x d k x d j } I ≤ k < j C[2, 4] = min C[2, 2] + C[3, 4] + d 1 x d 2 x d 4 = 0 + 40 + 2 x 4 x 5 = 80 C[2, 3] + C[4, 4] + d 1 x d 3 x d 4 = 16 + 0 + 2 x 2 x 5 = 36 When, K = 3 24 28 16 36 40 1 1 2 3 3 Cost K value 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 When, K = 2 2 ≤ k < 4

28. Example Problem Let us find the C[1, 4]:  C[ i , j] = min { C[ i , k] + C[k + 1, j] + d i-1 x d k x d j } I ≤ k < j C[1, 4] = min C[1, 1] + C[2, 4] + d x d 1 x d 4 = 0 + 36 + 3 x 2 x 5 =66 C[1, 2] + C[3, 4] + d x d 2 x d 4 = 24 + 40 + 3 x 4 x 5 = 124 C[1, 3] + C[4, 4] + d x d 3 x d 4 = 28 + 0 + 3 x 2 x 5 = 58 When, K = 2 24 28 58 16 36 40 1 1 3 2 3 3 Cost K value 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 When, K = 1 When, K = 3 1 ≤ k < 4

29. Example Problem 24 28 58 16 36 40 1 1 3 2 3 3 Cost K value 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 From the k-value table, we can parenthesize the given matrices: A 1 x A 2 x A 3 x A 4 (A 1 x A 2 x A 3 ) x A 4 (A 1 x (A 2 x A 3 )) x A 4 ((A 1 ) x (A 2 x A 3 )) x A 4 A 1 A 2 A 3 A 4

30. Effectiveness of Parenthesization Example: B is 3 x 100 C is 100 x 5 D is 5 x 5 (B x C) x D takes 1500 + 75 = 1575 operations B x (C x D) takes 1500 + 2500 = 4000 operations

31. Naïve Approach In naïve approach, we try the brute-force method of finding all possible parenthesization methods and then to choose the optimal method. The number of paranthesizations will be equal to number of binary trees with n nodes. This is Exponential in time This is called the Catalan number, and it is almost 4 n

32. Greedy Approach - 1 Repeatedly select the product that uses the most operations. A is 10 x 5 B is 5 x 10 C is 10 x 5 D is 5 x 10 (A x B) x (C x D) takes 500 + 1000 + 500 = 2000 operations A x ((B x C) x D) takes 500 + 250 + 250 = 1000 operations

33. Greedy Approach - 2 Repeatedly select the product that uses the fewest operations. A is 101 x 11 B is 11 x 9 C is 9 x 100 D is 100 x 99 A x ((B x C) x D)) takes 109989 + 9900 + 108900 = 228789 operations. (A x B) x (C x D) takes 9999 + 89991 + 89100 = 189090 operations

34. Dynamic Programming Algorithm: Matrix-Chain Multiplication Algorithm matrixChain (S): Input: sequence S of n matrices to be multiplied Output: number of operations in an optimal parentheization of S for i <- 1 to n-1 do N i,i <- 0 for b <- 1 to n-1 do for i <- 0 to n-b-1 do j <- i + b N i,j <- +infinity for k <- i to j-1 do N i,j <- min { N i,j , N i,k + N k+1,j + d i x d k+1 x d j+1 }

35. Dynamic Programming Algorithms: The subproblems here are not independent , the subproblems overlap . Since subproblems overlaps, we don’t use recursion . Instead we construct optimal subproblems “bottom-up”. The running time is O(n 3 ).

36. Reference Matrix Chain Multiplication - Dynamic Programming – Abdul Bari.  https://youtu.be/prx1psByp7U?si=bvn_xBi78xEl3HQI Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest, and Clifford Stein. 2009. Introduction to Algorithms, Third Edition (3rd. ed.). The MIT Press. Steven S. Skiena . 2008. The Algorithm Design Manual (2nd. ed.). Springer Publishing Company, Incorporated.