# Matrix Chain Multiplication C Program

By | October 31, 2016

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

1. Input n matrices.
2. Separate it into two sub-sequences.
3. Find out the minimum cost of multiplying every set.
4. Calculate the sum of these costs, and add in the cost of multiplying the two matrices.
5. Repeat the above steps for every possible position at which the sequence of matrices can split, and take the minimum cost.

#### 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.

## 2 thoughts on “Matrix Chain Multiplication C Program”

1. prosenjit mlondal

int minimum_cost(int matrix, int t)
{
int x, small;
if(t == 1)
{
return matrix;
}
else
{
small = matrix;
for(x = 1; x < t; x++)
{
if(matrix[x] < small)
{
small = matrix[x];
}
}
return small;
}
}

i can't understand pls tell …

2. Mihir Nandgaonkar

The chained matrix multiplication problem can be solved using Recursion too.