# Matrix-chain multiplication

We are given a sequence (chain) (M1, M2, M3…Mn) of n matrices to be multiplied and we need to find the most efficient way to multiply these matrices together. Now, if the chain of matrices is M1*M2*M3*M4, then it could be evaluated in various distinct ways without affecting the final product:

(M1*(M2*(M3*M4)))
(M1*((M2*M3)*M4))

As we know, that the cost to multiply two matrices A[p][q] and B[q][r] is pqr. Also matrix-multiplication could only be performed if number of columns of A is equal to the number of rows of B.

 Now, the way we parenthesize a chain of matrices can have dramatic impact on the cost of evaluating the product. Consider the following chain of matrices (M1, M2, M3) with dimensions as M1(10 x 100), M2(100 x 5) and M3(5 x 50):

1. Let’s multiply in this order (M1*(M2*M3)). It leads to:

100*5*50 + 10*100*50 = 25000 + 50000 = 75000 computational operations

2. Let’s multiply in the following order ((M1*M2)*M3). It leads to:

10*100*5 + 10*5*50 = 5000 + 2500 = 7500 computational operations

Now, we have to find the most efficient way to multiply a chain of matrices so that we have minimum number of computational operations. This problem could be solved by Dynamic programming paradigm.

###### Optimal substructure
Let M[i][j] = min (i<=k<=j) {M[i, k] + M[k+1, j] + pi-1*pk*pj},
where M[i][j] is the minimum number of multiplication operations needed for matrices from i to j
Let the matrices be:
M1 = 5 x 4
M2 = 4 X 6
M3 = 6 x 2
M4 = 2 x 7
###### Pseudocode and Iterations

Let p = {5, 4, 6, 2, 7}, for matrices M1(5×4), M2(4×6), M3(6×2), M4(2×7). Also M[i][i] = {0} ie M = M = M = M = 0 (Base case, no operation for matrix multiplying with itself).

Referencing the image above, we need to compute M:

Using M[i][j] = min (i<=k<j) {M[i, k] + M[k+1, j] + pi-1*pk*pj}
1. M = min (1<=k<2) {M[1, 1] + M[2, 2] + p0*p1*p2}
= min {0 + 0 + 120} = 120
2. M = min (2<=k<3) {M[2, 2] + M[3, 3] + p1*p2*p3}
= min {0 + 0 + 48} = 48
3. M = min (3<=k<4) {M[3, 3] + M[4, 4] + p2*p3*p4}
= min {0 + 0 + 84} = 84
4. M = min (1<=k<3) {{M[1, 1] + M[2, 3] + p0*p1*p3},
{M[1, 2] + M[3,3] + p0*p2*p3}}
= min {{0 + 48 + 40}, {120 + 0 + 60}} = {88, 180}
= 88 
5. M = min (2<=k<4) {{M[2, 2] + M[3, 4] + p1*p2*p4},
{M[2, 3] + M[4,4] + p1*p3*p4}}
= min {{0 + 84 + 168}, {48 + 0 + 56}} = {252, 104}
= 104 
6. M = min (1<=k<4) {{M[1, 1] + M[2, 4] + p0*p1*p4},
{M[1, 2] + M[3,4] + p0*p2*p4},
{M[1, 3] + M[4,4] + p0*p3*p4}}
= min {{0 + 104 + 140}, {120 + 84 + 210},
{88 + 0 + 70}} = {244, 414, 158}
= 158

###### Matrix-chain multiplication solution

Code Implementation

//
//  main.cpp
//  Matrix Chain Multiplication
//
//  Created by Himanshu on 17/09/21.
//

#include <iostream>

#include <iostream>
using namespace std;
const int N = 5;

void MatrixChainMultiplication (int p[]) {

int M[N][N];
for (int i=0; i<N; i++) {
for (int j=0; j<N; j++) {
if (i == j) {
M[i][j] = 0;
} else {
M[i][j] = INT_MAX;
}
}
}

// c is the length of chained matrices
for (int c=2; c<N; c++) {
for (int i=1; i<(N-c+1); i++) {
int j = i+c-1;
for (int k=i; k<j; k++) {
M[i][j] = min(M[i][j], (M[i][k] + M[k+1][j] + p[i-1]*p[k]*p[j]));
}
}
}

cout<<M[N-1]<<endl;

}

int main() {
//For matrices M1(5x4), M2(4x6), M3(6x2), M4(2x7)
int A[] = {5, 4, 6, 2, 7};
MatrixChainMultiplication(A);
}


Output:

158

Here’s a working example: Ideone

Reference
 Introduction to Algorithms