Matrix chain multiplication | Algorithm

Matrix chain multiplication

Matrix chain multiplication is nothing but it is a  sequence or chain A1, A2, …, An of n matrices to be multiplied. i.e, we want to compute the product A1A2…An. we need to find the optimal way to parenthesize the chain of matrices.

Example 1:
Let A be a p*q matrix, and B be a q*matrix. Then the complexity is p*q*r
A1 : 10*100, 
A2: 100*5, 
A3: 5 *50.

Two ways to parenthesize the matrices are:
((A1A2)A3): 10 *100 *5 + 10 *5 *50 = 5000 + 2500 = 7500 scalar multiplications.
(A1(A2A3)): 100 *5 *50 + 10 *100 *50 = 75000 scalar multiplications.
First way is 10 times faster than the second way.

Example 2
Different ways to parenthesize a chain of 4 matrices A1, A2, A3, A4 are:
1 way           =  ( A1 ( A2 ( A3 A4 ))),
2nd way     =  ( A1 ((A2 A3 ) A4 )),
3rd way      =  ((A1 A2 )(A3 A4 )),
4th way      =  ((A1 ( A2 A3 ))A4 ),
5th way      =  (((A1 A2 ) A3 ) A4 ).

An optimal solution should minimize the no.of scalar multiplications

An optimal parenthesization of the product A1A2…An splits the product between Ak and Ak+1 for some integer k where  1 ≤ k < n

First compute matrices A1..k and Ak+1..n ; then multiply them to get the final matrix A1..n
Let m[i, j] be the minimum number of scalar multiplications necessary to compute Ai..j

Matrix chain multiplication

First computes costs for chains of length l=1. Then for chains of length l=2,3, … and so on…. Computes the optimal cost bottom-up.

Matrix chain multiplication

k value is the parenthesis breaking point
k value for m[1,3] is 2 thus the optimal order for multiplication is ((A1A2)A3)

An algorithm for this approach is given below:

Matrix chain multiplication

Time complexity of the Matrix chain multiplication algorithm is O(n3).


Topic : Matrix chain multiplication

Leave a Reply