Find he minimum number of scalar multiplications in matrix multiplication

Question

Four matrices M1, M2, M3, and M4 have dimensions p x q, q x r, r x s, and s x t respectively can be multiplied in several ways with different number of total scalar multiplications. For example, when multiplied as ((M1 x M2) x (M3 x M4)) total number of scalar multiplications is pqr + rst + prt.

When multiplied as (((Mi x M2) x M3) x M4) the total number of scalar multiplications is pqr + prs + pst.

If p = 10, q = 100, r = 20, s = 5, and t = 80, then what is the minimum number of scalar multiplications needed ?

Comments

Answer is 19000

How to solve this?

---

ans = 19000  ??

---

Is there any shortcut or Trick to get min number of multiplication faster? I mean if we could know the right split.

---

$ https://gateoverflow.in/2140/gate-cse-2011-question-38 $

Answer 1

19000 is the ryt ans

Comments

which algorithm you are using ...bro

i mean name of this algo?

---

Your Answer Is Correct but m[2,4] is Wrong -> (p1*p2*p4) = 1,60,000 not 16k .

---

Consider,

(2,4)= min{ (2,2) + (3,4) + p1+p2+p4,

                    (2,3)+ (4,4) + p1+p3+p4

                    }

       = min{0+8000 + 100*20*80,

                 10000 + 0 + 100*5*80

               }

           = min{    8000 + 160000,

                     10000 + 40000

                 }

          = min {168000, 50000}

            = 50000

 

You calculated  p1*p2*p4 as 16000 but  it is 160000

 p1 =100, p2= 20, p3= 80

100*20*80 = 100*1600 = 160000

Answer 2

Answer is 19000 multiplication

On multiplying M1_10*100 M2_100*20 Number of scalar multiplications needed is 10*100*20 = 20000
M1  M2  M3  M4 can be multiplie in 5 different ways depicted in the following figure . We need to take the minimum of them all .

Comments

you can also refer https://gateoverflow.in/57553/minimum-number-multiplications-required-compute-matrices

---

Is there any shortcut or Trick to get min number of multiplication faster? I mean if we could know the right split.

---

Depends on the input given in the question, so sadly you have to consider all the cases to derive at the optimal answer ;(

Answer 3

A=10*100

B=100*20

C=20*5

D=5*80

m going to use DP bottom up evaluation tabular approach to find min no of scalar multiplication...

we will start with

(1,1),(2,2),(3,3),(4,4)....they all will be 0
now, compute

(1,2)=10*100*20=20.000
(2,3)=100*20*5=10,000
(3,4)=20*5*80=8000

now,

(1,3)=min{      (1,1)+(2,3)+10*100*5                         =15,000
                     (1,2)+(3,3)+10*20*5
                                                     }  

(2,4)=min{      (2,2)+(3,4)+100*20*80                       =50,000
                     (2,3)+(4,4)+100*5*80
                                                    }  

finally compute

(1,4)=min {     (1,1)+(2,4)+10*100*80
                     (1,2)+(4,4)+10*20*80            =19,000(Ans!!)
                     (1,3)+(4,4)+10*5*80
​​​​​​​                                                     }

Comments

Is there any shortcut or Trick to get min number of multiplication faster? I mean if we could know the right split.

Answer 4

19000 is the correct answer.