MATRIX CHAIN MULTIPLICATION | What is matrix chain multiplication? | Matrix chain multiplication problem solving techniques | Implementation | Time complexity

CONTENTS

List of topics that we cover in this article:

  • What is matrix chain multiplication?
  • Matrix chain multiplication problem solving techniques.
  • Implementation
  • Time complexity

MATRIX CHAIN MULTIPLICATION

  • What is matrix chain multiplication?

Matrix chain multiplication problem is the most popular problem can be solved by using dynamic programming. In this problem set of matrices are given and we must figure out how many minimum operations need to perform to multiply all these matrices. The main goal is not to multiply the matrices, but we must know which pair should select such that total cost of multiplication is minimum. So, you can clearly understand that the problem is not to find the multiplication, but we must know how to multiply them.

  • Matrix chain multiplication can also be solved by using:
  • Recursion
  • Top down dynamic programming
  • Bottom up dynamic programming
  • For example, let’s take three matrices A, B, C size of
  • A=10*30
  • B=30*5
  • C=5*60

 

Now we need to find the product of A.B.C

Actually, we don’t need the resultant matrix instead we should tell what the minimum number of operations will take to get the result.

When we multiply A.B.C

Firstly, I may take (AB) and later multiply with C i.e. (AB)C or I can multiply (BC) first and later multiply with A i.e A(BC)

 

Before going to this first know what the minimum number of operations are required to multiply matrices.

Two matrices can be multiplied by if the value of K is same.

And we know that resultant size of matrix is

          For example, the matrix size of A is 1*2 and matrix size of B is 2*3 then the resultant size of matrix is 1*3

So therefore, number of operations required to multiply two matrices is i*k*j 

Back to our possibilities that we made earlier (AB)C and A(BC)

(AB)C -> 1500+3000= 4500 number of operations required to multiply.

A(BC)-> (30*5*60) +(10*30*60) = 2700 number of operations are required.

 So now we can clearly say that 2700 is the minimum we will select A(BC) possibility to perform multiplication.

  • Implementation:

 

Now let’s solve a problem to get a clear idra

                             A1*A2*A3*A4

                            5*4  4*6  6*2  2*7

 

We can solve this problem by many ways. Let’s say for example

  • ((A1*A2) *A3) *A4
  • (A1*A2) *(A3*A4)

See this possibility in tree structure:

T(n)=2nCn/n+1

Now if i give n=3 then T (3) =5

So, these matrices can be multiplied in five different ways. We must find the minimum operation in those 5 ways. How can we know which one will give minimum result?   We will try all possible five ways, but we follow easy method that is given by dynamic programming. Dynamic programming always says that try all possible ways and pick up the best solution.

Let’s observe the example:

Dynamic programming uses tabulation method

A1. A2. A3. A4

5*4 4*6 6*2 2*7

Now let’s say only A1 its not multiplied with anyone so m [1,1] = 0

If we say only A2 it is not multiplied anyone so m [2,2] = 0

Similarly, m [3,3] and m [4,4] are also 0

Calculate m [1,2] that is multiplying two matrices 1 to 2

A1. A2 the dimensions of A1 and A2 are

5*4 4*6 =120 update the value at m[1,2] =120 so here we have multiplied with 1 and update the same value at the same position in S table

Calculate m [2, 3] i.e A2. A3 4*6 6*2 = 48   

Similarly, m [3,4] i.e A3. A4 6*2 2*7 = 84    

Next, m [1,3] that is multiplying three matrices 1 to 3

A1. A2. A3 this can be solved in two ways

A1. (A2. A3) & (A1. A2). A3

Now their dimensions are

5*4 (4*6 6*2)   & (5*4 4*6) 6*2

A1 is nothing but m [1, 1]

(A2. A3) is m [2, 3]

 m [1, 1] +m [2, 3] +5*4*2 = 0+48+40 = 88

And the next way is (A1. A2). A3

m [1, 2] +m [3,3] +5*6*2 = 120+0+60 = 180

By comparing two values, 88 is the minimum so we consider this value and update

m[1, 3] = 88

To understand this in simple way follow the procedure

Calculate m [2,4]

M[2,2]+m[3,4]+4*6*7    m[2,3]+m[4,4]+4*2*7

     0+84+168                    48+0+56

       252                                 104

104 is the minimum so m [2,4] is 104

 

Calculate m [1,4]

= {0 104+140, 120+84+210, 88+70}

= {244, 414, 158}

158 is the minimum so m [1,4] is 158.

 

We have only calculated only half of the table but not the full table.

  • Time complexity:

We are generating n(n-1)/2 and this going to be n^2 approximately. And we must know how each element we are getting, calculating all and we are considering only minimum and how much time it will take atmost is n

Time complexity for matrix chain multiplication is

n(n-1)/2=n^2*n=n^3

Time complexity for matrix chain multiplication is

0Comment

What to read next

Please Go through all these linksW3Schools – HTML Tutorial

DefinitionFiber optics is the technology used to transmit information as pulses of light through strands of fiber made of glass or plastic over long