Matrix Chain Multiplication in C and C++

Here you will find out about Matrix Chain Multiplication with example and furthermore get a

program that executes matrix chain multiplication in C and C++.

Before going to fundamental issue initially recall some premise.

We realize that to duplicate two networks it is a condition that, number of segments in the first matrix

ought to be equivalent to the number of columns in the second matrix. Let say there are two frameworks

An and B with measurements A (2 x 3) and B (3 x 2).

We should see an example.

Matrix Chain Multiplication

Above we can see the resultant matrix is (2 x 2) matrix, for example, it contains all out 4 components.

To compute every component we completed 3 multiplications (which is equivalent to a

number of sections in the first matrix and number of lines in the second matrix). So absolutely

for 4 components, 4*3 = 12 multiplications are required.

In sum up way grids, A (P x Q) and B(Q x R) will result in the matrix (P x R) which contains P * R components.

To figure every component need a “Q” number of multiplications. Absolute multiplications required are P * Q * R

How about we attempt to increase multiple networks.

In the event that 3 networks A, B , C we can locate the conclusive outcome in two different ways (AB)C or A(BC).

We get the same outcome in any capacity since matrix multiplication fulfils associativity property.

Let A (1 x 2 ), B (2 x 3 ), C ( 3 x 2 ). In the event that we pursue first way, for example (AB)C way.

To ascertain (AB) we need 123 = 6 multiplications. Presently resultant AB get measurements

1 x 3 this increased with C need 132 = 6 multiplications. Absolute 6+6 = 12 multiplications required.

On the off chance that we pursue second way, for example, A(BC) way.

To ascertain (BC) we need 232 = 12 multiplications. Presently resultant BC gets measurements 2 x 3.

A duplicate with this outcome needs 123 = 6. Complete 12+6 = 18 multiplications required.

Here we can see that dependent on the way we parenthesize

the frameworks all outnumber of multiplications is evolving.

On the off chance that 4 frameworks A, B, C, D we can discover conclusive outcome in 5

different ways A(B(CD)) or A((BC)(D)) or (AB)(CD) 4. ((AB)C)D or (A(BC))D. For this situation additionally,

every way requires the distinctive number of multiplications.

General equation to discover a number of ways we can discover an arrangement is (2n)! /[ (n+1)! n! ].

In the wake of parenthesizing these numerous ways, every way requires a diverse number of

multiplications for the conclusive outcome. At the point when measurements are

enormous (200 x 250 like this) with the increasing number of networks, at that point finding

the parenthesizing way which requires the least number of multiplications need will give less time multifaceted nature.

So Matrix Chain Multiplication issue point isn’t to locate the conclusive outcome of multiplication,

it is discovering how to parenthesize grids so that, requires the least number of multiplications.

Proficient method for settling this is utilizing dynamic programming

Matrix Chain Multiplication Using Dynamic Programming

Give we a chance to have “n” number of networks A1, A2, A3 … An and measurements

are d0 x d1, d1 x d2, d2 x d3 … . dn-1 x dn (i.e Dimension of Matrix Ai is di-1 x di

Illuminating a chain of matrix that, Ai Ai+1 Ai+2 Ai+3 … . Aj = (Ai Ai+1 Ai+2 Ai+3 … . Ak ) (Ak+1 Ak+2 … . Aj ) + di-1 dk dj where I <= k < j.

For all the more understanding check beneath example.

Here absolute I to j networks, Matrix I to k and Matrix k+1 to j ought to be unravelled in a

recursive way lastly these two frameworks duplicated and these measurements di-1 DK Dj

(number of multiplications required) included. The variable k is transformed I to j.

Recursive Equation

Note: M[i, j] demonstrates that on the off chance that we split from matrix I to matrix j, at that point least number of scalar multiplications required.

M [ I , j ] = { 0 ; when i=j ; [means it is a solitary matrix . On the off chance that there is just a single

matrix no compelling reason to duplicate with some other. So 0 (zero) multiplications required.]

= { min { M[ I, k ] + M[k+1, j ] + di-1 dk dj } where I <= k< j

Example Problem

Given issue: A1 (10 x 100), A2 (100 x 20), A3(20 x 5), A4 (5 x 80)

To store results, in unique programming we make a table

This table filled utilizing underneath computations.

Here cell 2,3 stores the base number of scalar multiplications required to.

Utilizing above recursive condition we can fill whole first column with every one of 0’s (zeros)

on the grounds that i=j (for example split occurred at just a single matrix which requires zero multiplications)

Table [1,2] = 1010020 = 20000

Table [2,3] = 100205 = 10000

Table [3,4] = 20580 = 8000

Table [1,3] = least of

= { (1,1) + (2,3) + 10* 100*5 = 0+10000+5000 = 15000

= { (1,2) + (3,3) + 10205 = 20000+0+1000 = 21000

In this manner Table[1,3] is 15000 and part occurred at 1

Table [2,4] = least of

= { (2,2) +(3,4) + 1002080 = 0 + 8000 + 160000 = 168000

= { (2,3) + (4,4) + 100580 = 10000 + 0 + 40000 = 50000

In this way Table of [2,4] is 50000 and part occurred at 3

Table of [1,4] = least of

= { (1,1) +(2,4) + 1010080 = 0 + 50000 + 80000 = 130000

= { (1,2) +(3,4) + 10* 20* 80 = 20000 + 8000 + 16000 = 44000

= { (1,3) + (4,4) + 10580 = 15000+0+4000 = 19000

In this way table of [1,4] is 19000 which is last answer and part occurred at 3.

Parting way: (1234) is unique in the ultimate result where 19000 answers we got split

occurred at 3 so ( 1 2 3 ) (4). Split for (123) implies see at Table [1,3] that one least 15000 splits at 1.

So ( 1 ) ( 2 3 ) ( 4). That implies first do 2 x 3 and this 1 x first outcome and afterwards this outcome x 4.

Time Complexity

In the event that there are n number of frameworks we are making a table contains [(n) (n+1) ]/2

cells that are in most pessimistic scenario absolute number of cells n*n = n2 cells we need figure = O (n2)

For every single one of the section, we need to discover the least number of multiplications taking

most exceedingly awful (it occurs finally cell in a table) that is Table [1,4] which equivalents to O (n) time.

At long last O (n2) * O (n) = O (n3) is time intricacy.

Space Complexity

We are making a table of n x n so space multifaceted nature is O (n2).

Program for Matrix Chain Multiplication in C

// This code implemented using Algorithm in Coremen book
 
#include<stdio.h>
#include<limits.h>
 
// Matrix Ai has dimension p[i-1] x p[i] for i = 1..n
 
int MatrixChainMultiplication(int p[], int n)
{
    int m[n][n];
    int i, j, k, L, q;
 
    for (i=1; i<n; i++)
        m[i][i] = 0;    //number of multiplications are 0(zero) when there is only one matrix
 
    //Here L is chain length. It varies from length 2 to length n.
    for (L=2; L<n; L++)
    {
        for (i=1; i<n-L+1; i++)
        {
            j = i+L-1;
            m[i][j] = INT_MAX;  //assigning to maximum value
 
            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;    //if number of multiplications found less that number will be updated.
                }
            }
        }
    }
 
    return m[1][n-1];   //returning the final answer which is M[1][n]
 
}
 
int main()
{
    int n,i;
    printf("Enter number of matrices\n");
    scanf("%d",&n);
 
    n++;
 
    int arr[n];
 
    printf("Enter dimensions \n");
 
    for(i=0;i<n;i++)
    {
        printf("Enter d%d :: ",i);
        scanf("%d",&arr[i]);
    }
 
    int size = sizeof(arr)/sizeof(arr[0]);
 
    printf("Minimum number of multiplications is %d ", MatrixChainMultiplication(arr, size));
 
    return 0;
}

Output

Enter number of matrices
4
Enter dimensions
Enter d0 :: 10
Enter d1 :: 100
Enter d2 :: 20
Enter d3 :: 5
Enter d4 :: 80
Minimum number of multiplications is 19000

Program for Matrix Chain Multiplication in C++

// This code implemented using Algorithm in Coremen book
 
#include<iostream>
#include<limits.h>
 
using namespace std;
 
// Matrix Ai has dimension p[i-1] x p[i] for i = 1..n
 
int MatrixChainMultiplication(int p[], int n)
{
    int m[n][n];
    int i, j, k, L, q;
 
    for (i=1; i<n; i++)
        m[i][i] = 0;    //number of multiplications are 0(zero) when there is only one matrix
 
    //Here L is chain length. It varies from length 2 to length n.
    for (L=2; L<n; L++)
    {
        for (i=1; i<n-L+1; i++)
        {
            j = i+L-1;
            m[i][j] = INT_MAX;  //assigning to maximum value
 
            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;    //if number of multiplications found less that number will be updated.
                }
            }
        }
    }
 
    return m[1][n-1];   //returning the final answer which is M[1][n]
 
}
 
int main()
{
    int n,i;
    cout<<"Enter number of matrices\n";
    cin>>n;
 
    n++;
 
    int arr[n];
 
    cout<<"Enter dimensions \n";
 
    for(i=0;i<n;i++)
    {
        cout<<"Enter d"<<i<<" :: ";
        cin>>arr[i];
    }
 
    int size = sizeof(arr)/sizeof(arr[0]);
 
    cout<<"Minimum number of multiplications is "<<MatrixChainMultiplication(arr, size));
 
    return 0;
}

Remark beneath on the off chance that you have any questions identified with the above program for matrix chain multiplication in C and C++.