WAP to Implement Matrix Chain Multiplication in C - AskTheCode

Code for Matrix Chain Multiplication in C | Matrix Chain Multiplication Program | Ask The Code

---

Problem:

You are given a sequence of n matrices A1, A2, A3, ..., An, having dimensions DIM1, DIM2, DIM3, ..., DIMn such that dimension of Ai is DIMi-1 x DIMi. You are assigned a task to find the most efficient method to perform matrix multiplication on these matrices. Here, you are not asked to perform the matrix multiplication, but to decide the most effective way to do the multiplications.

You already know that there is a condition to multiply two given matrices, and i.e., the number of columns in the first matrix must be equal to the number of rows in the second matrix.

And as matrix multiplication is associative, so we can do matrix multiplication in many ways, i.e., parenthesizing the product in any manner will not affect the result.

Write a C program to display the required minimum number of multiplicative operations for multiplying the given matrices.

---

Explanation:

Let's understand this matrix chain multiplication problem using examples.

Let's assume two matrices A and B having dimensions (m x n) and (n x p) respectively.

Then, operation A x B will need a total of m * n * p multiplications.

Now, let's take three matrices A, B, and C having dimensions (3 x 4), (4 x 2), and (2 x 5) respectively. Then, in this case, we can perform matrix multiplication in two ways:

1. (AB) C First, evaluate A x B: We'll need to perform a total of 3 * 4 * 2 multiplications, and it'll result in a matrix AB having dimension 3 x 2. Now, evaluate AB x C: Here, we'll need to perform a total of 3 * 2 * 5 multiplications. In summing up, there is total (3 * 4 * 2) + (3 * 2 * 5) = (24 + 30) = 54 multiplications are required using this approach.
   

2. A (BC) First, evaluate B x C: We'll need to perform a total of 4 * 2 * 5 multiplications, and it'll result in a matrix BC having dimension 4 x 5. Now, evaluate A x BC: Here, we'll need to perform a total of 3 * 4 * 5 multiplications. In summing up, there is total (4 * 2 * 5) + (3 * 4 * 5) = (40 + 60) = 100 multiplications are required using this approach.

From this example, one can easily observe that on changing the parenthesis, the total number of required multiplications changes.

Now, let's assume four matrices A, B, C, and D. Then, we could perform the matrix chain multiplication in the following ways:

1. A (B (CD))

2. A ((BC) (D))

3. ((A) (BC)) D

4. ((AB) (C)) D

5. (AB) (CD)

We'll be getting different numbers of multiplications based on the position of parenthesis in this case as well.

Thus, from the examples, we can conclude that Matrix Chain Multiplication is not used for multiplying matrices, instead, it helps to find the approach in which the minimum multiplication is to be done.

---

Input / Output Sample:

Input: 1 1 2 6

Output: Minimum number of multiplications is 14

---

Input: 2 5 4 1 2 7

Output: Minimum number of multiplications is 58

---

Code:

#include <stdio.h>
#include "random.h"
#include <limits.h>

void print(char []);
int MCO(int [], int);

int main(){
    int a[] = {2, 5, 4, 1, 2, 7};
    int n = 4;

    print("Minimum number of multiplications is ");
    printf("%d\n", MCO(a, n));
    return 0;
}
int MCO(int p[], int n){
    int m[n][n];
    int i, j, k, L, q;
    for (i = 1; i < n; i++)
        m[i][i] = 0;

    for (L = 2; L < n; L++){
        for (i = 1; i < n - L + 1; i++){
            j = i + L - 1;
            m[i][j] = INT_MAX;
            for (k = i; k <= j - 1; k++){
                q = m[i][k] + m[k + 1][j] + p[i - 1] * p[k] * p[j];
                if (q < m[i][j])
                    m[i][j] = q;
             }
         }
    }
    return m[1][n-1];
}

void print(char s[]){
    printf("%s",s);
}