How to perform Matrix Chain Multiplication

Problem

We are given 'n' matrices, and we have to multiply them in such a way that the total number of operations is minimum.

Solution

The matrix chain ordering problem, also known as matrix chain multiplication, is an optimization issue that asks what is the most effective way to multiply a given series of matrices. Choosing the order of the matrix multiplications involved is the challenge; doing the multiplications is not the problem. Dynamic programming may help to find a solution to the issue.

# Top-down Solution # C++ code

// TOP DOWN APPROACH 

// BOARD INFINITY 

#include<bits/stdc++.h>
using namespace std;
// Function to find the minimum number of Multiplication
//  steps required in multiplying a chain of n matrices.

int MatrixChainMultiplication(int mat[],int low, int high){
    // If we are left with one matrix then
    // we don't need any multiplication steps.
    if(low==high)
        return 0;
   
    // Initializing minCost with very
    // large value.
    int minCost=INT_MAX;
   
    // Iterating from low to high - 1
    for(int k=low;k<high;k++){
        /*
        Cost = Cost of Multiplying chain on left side +
                Cost of Multiplying chain on right side +
                Cost of Multiplying matrix obtained from left
                and right side.
        */
        int cost=MatrixChainMultiplication(mat, low, k)+
            MatrixChainMultiplication(mat, k+1, high)+
            mat[low-1]*mat[k]*mat[high];
       
        // If the above cost is less than
        // minCost find so far then update minCost.
        if(cost<minCost)
            minCost=cost;
    }
    // Returning the minCost
    return minCost;
}
// Main Function
int main(){
    // This matrix chain of length 5 represents
    // 4 matrices of dimensions as follows -
    // 2*4, 4*6, 6*8, and 8*6.
    int mat[]={2, 4, 6, 8, 6};
    int n=sizeof(mat)/sizeof(mat[0]);

    cout<<"Minimum number of steps are - ";
    cout<<MatrixChainMultiplication(mat, 1, n-1);
    return 0;
}

write your code here: Coding Playground

Time Complexity: O(n^3)

Space Complexity: O(n^2)

# Bottom-up Solution # C++

// BOTTOM UP APPROACH 

// BOARD INFINITY

#include<bits/stdc++.h>
using namespace std;

// Function to find the minimum number of Multiplication
//  steps required in multiplying chain of n matrices.
int MatrixChainMultiplication(int mat[],int n){
    // Making 2d DP array of dimensions
    // (n-1)*(n-1)
    int dp[n-1][n-1];
   
    // Iterating while gap between first
    // length vary from 0 to n-1.
    for(int gap=0;gap<n-1;gap++){
        // Starting i from 0 and j=gap.
        // Iterating till j<n-1.
        for(int i=0,j=gap;j<n-1;i++,j++){
            // If gap is 0 (single matrix)
            // then assigning 0 to dp[i][j].
            if(gap==0)
                dp[i][j]=0;
            // Else if the gap is (2 matrices)
            // i.e. only once choice (mat1*mat2)
            else if(gap==1){
                dp[i][j]=mat[i]*mat[j]*mat[j+1];
            }
            // Else if gap>1, then we need to
            // find the optimal method.
            else{
                // Initializing minCost with very large value.
                int minCost=INT_MAX;
               
                // Iterating from k=i to
                // k = j-1 and finding cost.
                /*
                Cost = Cost of Multiplying chain on left side +
                        Cost of Multiplying chain on right side +
                        Cost of Multiplying matrix obtained from left
                        and right side.
                */
                for(int k=i;k<j;k++){
                    int leftCost=dp[i][k];
                    int rightCost=dp[k+1][j];
                    int thisCost=mat[i]*mat[k+1]*mat[j+1];
                   
                    minCost=min(minCost,leftCost
                            +rightCost+thisCost);
                }
                // Assigning minCost find to dp[i][j].
                dp[i][j]=minCost;
            }
        }
    }
    // Returning dp[0][n-2].
    return dp[0][n-2];
}
// Main Function
int main(){
    // This matrix chain of length 5 represents
    // 4 matrices of dimensions as follows -
    // 2*4, 4*6, 6*8, and 8*6.
    int mat[]={2, 4, 6, 8, 6};
    int n=sizeof(mat)/sizeof(mat[0]);
   
    cout<<"Minimum number of steps are - ";
    cout<<MatrixChainMultiplication(mat, n);
    return 0;
}

write your code here: Coding Playground

Time Complexity: O(n^3)

Space Complexity: O(n^2)

Conclusion

  • The bare minimum of multiplication operations necessary to multiply a chain of matrices has been determined in the matrix chain multiplication problem.
  • Finding the bare minimum of steps needed can significantly speed up multiplication.
  • The dynamic programming method requires additional space to determine the smallest number of steps needed to multiply a series of matrices.
  • To complete the operation effectively, choosing the order of matrix multiplication is crucial.
  • Therefore, it has been calculated how many multiplication steps are necessary to multiply a chain matrix of length n.
  • Since it would take a very long time to exhaustively test every possibility, dynamic programming is utilized to find the same.