Let us learn how to implement matrix chain multiplication algorithm in C programming language.
For this algorithm to work efficiently, the number of rows and columns of consecutive matrices should be equivalent. This algorithm is also known as Matrix Chain Ordering Problem.
What is Chained Matrix Multiplication?
When you’re given n number of matrices, it is important to find out an efficient way to multiply these matrices. If you need to multiply two matrices, then the order does not matter.
But, if there are more than two matrices to be multiplied, there needs to be a proper and efficient algorithm that helps in deciding the order in which the matrices should be multiplied.
A brute-force algorithm may prove to be time consuming and inefficient. But, a recursive approach using dynamic programming could be much more efficient.
Example
((WX)Y)Z = ((W(XY))Z) = (WX)(YZ) = W((XY)Z) = W(X(YZ))
Algorithm To Determine Optimal Parenthesization of a Product of N Matrices
- Input n matrices.
- Separate it into two sub-sequences.
- Find out the minimum cost of multiplying every set.
- Calculate the sum of these costs, and add in the cost of multiplying the two matrices.
- Repeat the above steps for every possible position at which the sequence of matrices can split, and take the minimum cost.
C Program For Implementation of Chain Matrix Multiplication using Dynamic Algorithm
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 | #include<stdio.h> #include<stdlib.h> int minimum_cost(int matrix[20], int t) { int x, small; if(t == 1) { return matrix[0]; } else { small = matrix[0]; for(x = 1; x < t; x++) { if(matrix[x] < small) { small = matrix[x]; } } return small; } } int main() { int t, i, l, j, k, limit; int matrix[30], multiplier[10][15], columns[15], rows[15], temp[15]; printf("\nEnter Total Number of Matrices:\t"); scanf("%d", &limit); for(i = 0; i < limit; i++) { printf("\nEnter Number of Columns of Matrix %d:\t", i + 1); scanf("%d", &columns[i]); printf("Enter Number of Rows of Matrix %d:\t", i + 1); scanf("%d", &rows[i]); } for(i = 0; i < limit; i++) { temp[i] = columns[i]; } temp[i] = rows[i - 1]; printf("\n"); for(k = 1; k <= limit; k++) { for(j = k, i = 1; j <= limit; j++, i++) { multiplier[i][j] = 0; } } for(l = 2; l <= limit; l++) { for(j = l, i = 1; j <= limit; j++, i++) { t = 0; for(k = i; k < j; k++) { matrix[t++] = (multiplier[i][k] + multiplier[k + 1][j]) + (temp[i - 1] * temp[k] * temp[j]); } multiplier[i][j] = minimum_cost(matrix, t); } } printf("\nMinimum Scalar Multiplications:\t%d\n", multiplier[1][limit]); return 0; } |
Output
In case you get any compilation errors or any doubts in this C program for Matrix Chain Multiplication using Dynamic Programming, let us know about it in the comment section below.
int minimum_cost(int matrix[20], int t)
{
int x, small;
if(t == 1)
{
return matrix[0];
}
else
{
small = matrix[0];
for(x = 1; x < t; x++)
{
if(matrix[x] < small)
{
small = matrix[x];
}
}
return small;
}
}
i can't understand pls tell …
The chained matrix multiplication problem can be solved using Recursion too.