Matrix Chain Multiplication

Introduction

Matrix chain multiplication is a method where we take the previous output and consider it as the input for the next.

Here, the Chain signifies that the size of one matrix’s column is equal to the size of the second matrix’s row [always].

In general:

If A = ⌊aij⌋ is considered to be a p x q matrix 

   B = ⌊bij⌋ is considered to be a q x r matrix

   C = ⌊cij⌋ is considered to be a p x r matrix

Then

Suppose we are given the following matrices {A1, A2, A3,…An} and we are supposed to perform the matrix multiplication on these matrices. Then, this can be obtained by performing a series of matrix multiplications. That is,

A1 x A2 x,A3 x.....x An

In general, the matrix multiplication operation is associative in nature rather than commutative. By saying this, we mean that we must follow the above matrix order for multiplication but we are free to parenthesize the above multiplication based upon our need.

In general, for the case  1≤ i≤ p and 1≤ j ≤ r

We can observe that the total number of entries in matrix C are p times r as the matrix is of dimension p x r. Also, each entry takes O (q) times to be computed, thus the total time taken in order to compute all the possible entries for the matrix ‘C’ which is a multiplication of ‘A’ and ‘B’ is proportional to the product of the dimensions p q and r.

Also, here we notice that we can save the number of operations by only reordering the parenthesis.

Example1:

Let us say, we are given 3 matrices, A1, A2, and A3 of order (10 x 100), (100 x 5), and (5 x 50) respectively.

3 Matrices can be multiplied in two ways as follows:

A1,(A2, A3): We first multiply A2 and A3 and then multiply the resultant with A1.

(A1,A2),A3: We first multiply A1 and A2 and then multiply the resultant withA3.

No of Scalar multiplications in Case 1 will be equal to:

(10 x 100 x 50)  + (100 x 5 x 50) 

= 50000 + 25000

= 75000  

No of Scalar multiplications in Case 2 will be equal to:

(10 x 5 x 50) + (100 x 10 x 5)

= 2500 + 5000 

= 7500  

I order to find out the best way possible for calculating the product, we can simply apply parenthesis for the expression in every possible fashion and also make a count of how many scalar multiplications are required each time.

For your competitive exams or any other exams, the Matrix Chain Multiplication Problem can be stated as follows: 

“find the optimal parenthesization of a chain of matrices that are to be multiplied in such a way that the number of scalar multiplications is minimized”.

A number of ways for parenthesizing the matrices:

There are many ways to apply parenthesizing to these matrices. If there are n items, then there will be (n-1) ways in which the outermost pair of parenthesis can be placed.

(A1) (A2, A3, A4,…………….An)

Or (A1, A2)  (A3, A4 ……………..An)

Or (A1, A2, A3)  (A4 ……………An)

……………………

Or(A1,A2,A3………….An-1) (An)

As we can see from the above set of equations after we split the kth matrices, we will be only left with the two parenthesized sequences of matrices, where: 

1. i) one consists of ‘k’ matrices and 
2. ii) another consists of ‘n-k’ matrices.

Now there are ‘L’ ways in which we can apply parenthesis to the left sublist and ‘R’ ways to apply parenthesis to the right sublist then the Total will be L.R as shown below:

Also, we can observe that p (n) = c (n-1) 

where c (n) is said to be the nth Catalon number

On applying Stirling’s formula we have

This tells us that 4n grows faster, as it is an exponential function and then n1.5.

Development of the Dynamic Programming Algorithm

1. To develop the algorithm, we have to characterize the structure of an optimal solution.
2. Also, we have to define the value of an optimal solution recursively.
3. Later, compute the value of an optimal solution using a bottom-up approach.
4. Finally, construct the optimal solution making use of the computed information.

Dynamic Programming Approach

Let Ai, j be the result we get by performing multiplication of matrices i through j. It can be observed that the dimension of Ai, j is pi-1 x pj matrix.

As discussed in the previous article, a dynamic programming solution will involve breaking up the given problem into subproblems so that the solutions to these sub-problems can be combined to solve the global problem.

At the greatest level of parenthesization, we will be multiplying two matrices

A1…..n = A1….k x Ak+1….n

This is the Dynamic approach to the Matrix chain multiplication problem.