Python Programming – Matrix Chain Multiplication

Python Programming – Matrix Chain Multiplication – Dynamic Programming MCM is an optimization problem that can be solved using dynamic programming

Given a sequence of matrices, find the most efficient way to multiply these matrices together. The problem is not actually to perform the multiplications, but merely to decide in which order to perform the multiplications.

We have many options to multiply a chain of matrices because matrix multiplication is associative. In other words, no matter how we parenthesize the product, the result will be the same. For example, if we had four matrices A, B, C, and D, we would have:

```    (ABC)D = (AB)(CD) = A(BCD) = ....
```

However, the order in which we parenthesize the product affects the number of simple arithmetic operations needed to compute the product, or the efficiency. For example, suppose A is a 10 × 30 matrix, B is a 30 × 5 matrix, and C is a 5 × 60 matrix. Then,

```    (AB)C = (10×30×5) + (10×5×60) = 1500 + 3000 = 4500 operations
A(BC) = (30×5×60) + (10×30×60) = 9000 + 18000 = 27000 operations.
```

Clearly the first parenthesization requires less number of operations.

Given an array p[] which represents the chain of matrices such that the ith matrix Ai is of dimension p[i-1] x p[i]. We need to write a function MatrixChainOrder() that should return the minimum number of multiplications needed to multiply the chain.

```  Input: p[] = {40, 20, 30, 10, 30}
Output: 26000
There are 4 matrices of dimensions 40x20, 20x30, 30x10 and 10x30.
Let the input 4 matrices be A, B, C and D.  The minimum number of
multiplications are obtained by putting parenthesis in following way
(A(BC))D --> 20*30*10 + 40*20*10 + 40*10*30

Input: p[] = {10, 20, 30, 40, 30}
Output: 30000
There are 4 matrices of dimensions 10x20, 20x30, 30x40 and 40x30.
Let the input 4 matrices be A, B, C and D.  The minimum number of
multiplications are obtained by putting parenthesis in following way
((AB)C)D --> 10*20*30 + 10*30*40 + 10*40*30

Input: p[] = {10, 20, 30}
Output: 6000
There are only two matrices of dimensions 10x20 and 20x30. So there
is only one way to multiply the matrices, cost of which is 10*20*30
```
• Optimal Substructure:

A simple solution is to place parenthesis at all possible places, calculate the cost for each placement and return the minimum value. In a chain of matrices of size n, we can place the first set of parenthesis in n-1 ways. For example, if the given chain is of 4 matrices. let the chain be ABCD, then there are 3 ways to place first set of parenthesis outer side: (A)(BCD), (AB)(CD) and (ABC)(D). So when we place a set of parenthesis, we divide the problem into subproblems of smaller size. Therefore, the problem has optimal substructure property and can be easily solved using recursion.

Minimum number of multiplication needed to multiply a chain of size n = Minimum of all n-1 placements (these placements create subproblems of smaller size)

• Overlapping Subproblems

Following is a recursive implementation that simply follows the above optimal substructure property.

[pastacode lang=”c” manual=”%2F*%20A%20naive%20recursive%20implementation%20that%20simply%0A%20%20follows%20the%20above%20optimal%20substructure%20property%20*%2F%0A%23include%3Cstdio.h%3E%0A%23include%3Climits.h%3E%0A%20%0A%2F%2F%20Matrix%20Ai%20has%20dimension%20p%5Bi-1%5D%20x%20p%5Bi%5D%20for%20i%20%3D%201..n%0Aint%20MatrixChainOrder(int%20p%5B%5D%2C%20int%20i%2C%20int%20j)%0A%7B%0A%20%20%20%20if(i%20%3D%3D%20j)%0A%20%20%20%20%20%20%20%20return%200%3B%0A%20%20%20%20int%20k%3B%0A%20%20%20%20int%20min%20%3D%20INT_MAX%3B%0A%20%20%20%20int%20count%3B%0A%20%0A%20%20%20%20%2F%2F%20place%20parenthesis%20at%20different%20places%20between%20first%0A%20%20%20%20%2F%2F%20and%20last%20matrix%2C%20recursively%20calculate%20count%20of%0A%20%20%20%20%2F%2F%20multiplications%20for%20each%20parenthesis%20placement%20and%0A%20%20%20%20%2F%2F%20return%20the%20minimum%20count%0A%20%20%20%20for%20(k%20%3D%20i%3B%20k%20%3Cj%3B%20k%2B%2B)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20count%20%3D%20MatrixChainOrder(p%2C%20i%2C%20k)%20%2B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20MatrixChainOrder(p%2C%20k%2B1%2C%20j)%20%2B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20p%5Bi-1%5D*p%5Bk%5D*p%5Bj%5D%3B%0A%20%0A%20%20%20%20%20%20%20%20if%20(count%20%3C%20min)%0A%20%20%20%20%20%20%20%20%20%20%20%20min%20%3D%20count%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F%2F%20Return%20minimum%20count%0A%20%20%20%20return%20min%3B%0A%7D%0A%20%0A%2F%2F%20Driver%20program%20to%20test%20above%20function%0Aint%20main()%0A%7B%0A%20%20%20%20int%20arr%5B%5D%20%3D%20%7B1%2C%202%2C%203%2C%204%2C%203%7D%3B%0A%20%20%20%20int%20n%20%3D%20sizeof(arr)%2Fsizeof(arr%5B0%5D)%3B%0A%20%0A%20%20%20%20printf(%22Minimum%20number%20of%20multiplications%20is%20%25d%20%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20MatrixChainOrder(arr%2C%201%2C%20n-1))%3B%0A%20%0A%20%20%20%20getchar()%3B%0A%20%20%20%20return%200%3B%0A%7D” message=”C” highlight=”” provider=”manual”/]

Time complexity of the above naive recursive approach is exponential. It should be noted that the above function computes the same subproblems again and again. See the following recursion tree for a matrix chain of size 4. The function MatrixChainOrder(p, 3, 4) is called two times. We can see that there are many subproblems being called more than once.

Since same suproblems are called again, this problem has Overlapping Subprolems property. So Matrix Chain Multiplication problem has both properties (see this and this) of a dynamic programming problem. Like other typical Dynamic Programming(DP) problems, recomputations of same subproblems can be avoided by constructing a temporary array m[][] in bottom up manner.

Dynamic Programming Solution
Following is Python implementation for Matrix Chain Multiplication problem using Dynamic Programming.

[pastacode lang=”python” manual=”%23%20Dynamic%20Programming%20Python%20implementation%20of%20Matrix%0A%23%20Chain%20Multiplication.%20See%20the%20Cormen%20book%20for%20details%0A%23%20of%20the%20following%20algorithm%0Aimport%20sys%0A%20%0A%23%20Matrix%20Ai%20has%20dimension%20p%5Bi-1%5D%20x%20p%5Bi%5D%20for%20i%20%3D%201..n%0Adef%20MatrixChainOrder(p%2C%20n)%3A%0A%20%20%20%20%23%20For%20simplicity%20of%20the%20program%2C%20one%20extra%20row%20and%20one%0A%20%20%20%20%23%20extra%20column%20are%20allocated%20in%20m%5B%5D%5B%5D.%20%200th%20row%20and%200th%0A%20%20%20%20%23%20column%20of%20m%5B%5D%5B%5D%20are%20not%20used%0A%20%20%20%20m%20%3D%20%5B%5B0%20for%20x%20in%20range(n)%5D%20for%20x%20in%20range(n)%5D%0A%20%0A%20%20%20%20%23%20m%5Bi%2Cj%5D%20%3D%20Minimum%20number%20of%20scalar%20multiplications%20needed%0A%20%20%20%20%23%20to%20compute%20the%20matrix%20A%5Bi%5DA%5Bi%2B1%5D…A%5Bj%5D%20%3D%20A%5Bi..j%5D%20where%0A%20%20%20%20%23%20dimension%20of%20A%5Bi%5D%20is%20p%5Bi-1%5D%20x%20p%5Bi%5D%0A%20%0A%20%20%20%20%23%20cost%20is%20zero%20when%20multiplying%20one%20matrix.%0A%20%20%20%20for%20i%20in%20range(1%2C%20n)%3A%0A%20%20%20%20%20%20%20%20m%5Bi%5D%5Bi%5D%20%3D%200%0A%20%0A%20%20%20%20%23%20L%20is%20chain%20length.%0A%20%20%20%20for%20L%20in%20range(2%2C%20n)%3A%0A%20%20%20%20%20%20%20%20for%20i%20in%20range(1%2C%20n-L%2B1)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20j%20%3D%20i%2BL-1%0A%20%20%20%20%20%20%20%20%20%20%20%20m%5Bi%5D%5Bj%5D%20%3D%20sys.maxint%0A%20%20%20%20%20%20%20%20%20%20%20%20for%20k%20in%20range(i%2C%20j)%3A%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%23%20q%20%3D%20cost%2Fscalar%20multiplications%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20q%20%3D%20m%5Bi%5D%5Bk%5D%20%2B%20m%5Bk%2B1%5D%5Bj%5D%20%2B%20p%5Bi-1%5D*p%5Bk%5D*p%5Bj%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20if%20q%20%3C%20m%5Bi%5D%5Bj%5D%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20m%5Bi%5D%5Bj%5D%20%3D%20q%0A%20%0A%20%20%20%20return%20m%5B1%5D%5Bn-1%5D%0A%20%0A%23%20Driver%20program%20to%20test%20above%20function%0Aarr%20%3D%20%5B1%2C%202%2C%203%20%2C4%5D%0Asize%20%3D%20len(arr)%0A%20%0Aprint(%22Minimum%20number%20of%20multiplications%20is%20%22%20%2B%0A%20%20%20%20%20%20%20str(MatrixChainOrder(arr%2C%20size)))” message=”Python” highlight=”” provider=”manual”/]

Output:

`Minimum number of multiplications is 18`

Time Complexity: O(n^3)
Auxiliary Space: O(n^2)

C++ Programming – Program to add two polynomials

C++ Programming – Program to add two polynomials – Mathematical Algorithms – Addition is simpler than multiplication of polynomials. We initialize result

Top 10 Grey Hat Hackers 2018

Grey hat hackers that do hacking bit the ethical and non-ethical. These are the persons who knows extraordinary hacking traps

Branch And Bound | Set 4 (Job Assignment Problem)

Branch And Bound (Job Assignment Problem) – Branch And Bound – It is required to perform all jobs by assigning exactly one worker to each job.

C programming-Lucky Numbers

C programming-Lucky Numbers – Mathematical algorithms – Lucky numbers are subset of integers. let us see the process of arriving at lucky numbers.

C Programming – Subset Sum Problem

C Programming – Subset Sum Problem – Dynamic Programming Given a set of non-negative integers, and a value sum, determine if there is a subset

C Programming – Horner’s Method for Polynomial Evaluation

C Programming Horner’s Method for Polynomial Evaluation – Mathematical Algorithms – Input is in form of array say poly[] where poly[0] represent coefficient