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*r 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
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.
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:
Time complexity of the Matrix chain multiplication algorithm is O(n3).
Topic : Matrix chain multiplication