Matrix Chain Multiplication

Matrix Chain Multiplication follows the dynamic programming.

Matrix Chain follows the dynamic programming. It is used for solving Optimization Problems where as it follows the principle of optimality.

Chain means one matrix’s column is equal to the second matrix’s row. Since matrix multiplication is associative and we have more options for multiplying a chain of matrices. In other sentences, we are parenthesizing the product, but outcome will be same.

Example If there are 4 matrices A1, A2,A3 and A4 Then the no of possibilities are

1. (A1A2)A3)A4
2. (A1(A2A3))A4
3. (A1A2) (A3A4)
4. A1((A2A3)A4)
5. A1(A2(A3A4))

The sequence in which we parenthesize the product, on the other hand, has an impact on the number of simple arithmetic operations needed to compute the product as well as its efficiency.

Note: Two matrices can only be multiplied if the number of columns in the first matrix equals the number of rows in the second matrix.

Where as here, c1=r2, r1=r3 and c2=c3.

So, Total Multiplication=r1.c1.c2.

Example:

As a result, we must identify a matrix multiplication sequence with the fewest possible multiplications.

The problem of matrix chain multiplication is addressed by dynamic programming as it is a optimization problem and greedy method in which we found the most appropriate optimal solution of multiplying the matrices.

The number of possible parenthesizations of a series of n matrices is denoted by P(n). When n=1, the matrix product has only one matrix and hence only one way to fully parenthesize it. When n = 1, 2,….n-1, a fully parenthesized matrix product is made up of two fully parenthesized matrix subproducts, with the split happening between the kth and (k+1)st matrices. As a result, the recurrence is obtained.

No of possibilities in matrix chain multiplications is :

Here, C(n) is the nth Catalon number.

Dynamic Programming:

To determine the optimum approach to parenthesize a matrix chain, we can utilise dynamic programming. We’ll do it by following the four-step approach.

1. Determine the structure of a good solution.
2. Define the value of an optimal solution in a recursive manner.
3. Calculate the value of the best solution.
4. Create an optimal solution using the data you’ve gathered.

Solve one example it make you exact sense about how to do matrix chain multiplication using dynamic programming.

Example:

In Dynamic Programming, ‘0’ is used to initialise every method. As a result, we changed the value to ‘0’. It will be organised in a diagonal fashion.

We must filter through all of the options, but only the one with the lowest output is taken into account.

Calculation of Product of 2 matrices

M₁ . M₂ = 5.3.7 = 105
M₂ . M₃ = 3.7.4 = 84
M₃ . M₄ = 7.4.6 = 168

Calculation of Product of 3 matrices

M₁ . M₂ . M₃ = MIN(((M₁ . M₂) . M₃), (M₁ . (M₂ . M₃)))
M₁ . M₂ . M₃ = MIN((105 + (5.7.4)),((5.3.4) + 84))
M₁ . M₂ . M₃ = MIN(245, 144)
M₁ . M₂ . M₃ = 144M₂ . M₃ . M₄ = MIN(((M₂ . M₃) . M₄), (M₂ . (M₃ . M₄)))
M₂ . M₃ . M₄ = MIN((84 + (3.4.6)), ((3.7.6) + 168))
M₂ . M₃ . M₄ = MIN(156, 294)
M₂ . M₃ . M₄ = 156

Calculation of Product of 4 matrices

M₁ . M₂ . M₃ . M₄ = MIN(((M₁ . M₂ . M₃) . M₄), (M₁ . M₂) . (M₃ . M₄), (M₁ . (M₂ . M₃ . M₄)))
M₁ . M₂ . M₃ . M₄ = MIN((144 + (5.4.6)), (105 + (5.7.6)), ((5.3.6) + 156))
M₁ . M₂ . M₃ . M₄ = MIN(264, 315, 246)
M₁ . M₂ . M₃ . M₄ = 246

As a result, 246 multiplications are required.
The matrix index in this example denotes a set of matrices’ multiplication sequence, and the associated value represents the needed minimum multiplications.

Time Complexity: Theta(n**3).

Code:
#include <bits/stdc++.h>
using namespace std;
int MatrixChainOrder(int p[], int i, int j)
{
if (i == j)
return 0;
int k;
int min = INT_MAX;
int count;
for (k = i; k < j; k++)
{
count = MatrixChainOrder(p, i, k)
+ MatrixChainOrder(p, k + 1, j)
+ p[i — 1] * p[k] * p[j];

if (count < min)
min = count;
}
return min;
}

int main()
{
int arr[] = { 1, 2, 3, 4, 3 };
int n = sizeof(arr) / sizeof(arr[0]);

cout << “Minimum number of multiplications is “
<< MatrixChainOrder(arr, 1, n — 1);
}

I will not say Matrix chain Multiplication is a easy topic but if u understand the concept and technique how it was derived u can do the questions easily.

I hope u all understand about matrix chain multiplication

Thank You.