Redirected
recategorized by
21,921 views
2 votes
2 votes
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 ?
recategorized by

4 Answers

9 votes
9 votes

19000 is the ryt ans

5 votes
5 votes

Answer is 19000 multiplication

On multiplying M110*100 M2100*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 .

2 votes
2 votes
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
​​​​​​​                                                     }

Related questions

2 votes
2 votes
2 answers
1
0 votes
0 votes
1 answer
3
Rohan Mundhey asked Nov 11, 2016
1,492 views
Matrix multiplication is associative and matrix chain multiplication uses following matricesA1 is 30×35A2 is 35×15A3 is 15×5A4 is 5×10A5 is 10×20A6 is 20×25Find the...
0 votes
0 votes
1 answer
4
jenny101 asked Oct 26, 2016
1,074 views