Matrix-Chain-Multiplication
Question 1 |
Let A1, A2, A3 and A4 be four matrices of dimensions 10 × 5, 5 × 20, 20 × 10, and 10 × 5, respectively. The minimum number of scalar multiplications required to find the product A1A2A3A4 using the basic matrix multiplication method is _________.
1500 | |
1501 | |
1502 | |
1503 |
Question 1 Explanation:
→ The minimum number of scalar multiplications required is 1500.
The optimal parenthesized sequence is A1((A2A3)A4) out of many possibilities, the possibilities are
1. ((A1A2)A3)A4
2. ((A1(A2A3))A4)
3. (A1A2)(A3A4)
4. A1((A2A3)A4)
5. A1(A2(A3A4))
→ A1((A2A3)A4) = (5 x 20 x 10) + (5 x 10 x 5) + (10 x 5 x 5) = 1000 + 250 + 250 = 1500
The optimal parenthesized sequence is A1((A2A3)A4) out of many possibilities, the possibilities are
1. ((A1A2)A3)A4
2. ((A1(A2A3))A4)
3. (A1A2)(A3A4)
4. A1((A2A3)A4)
5. A1(A2(A3A4))
→ A1((A2A3)A4) = (5 x 20 x 10) + (5 x 10 x 5) + (10 x 5 x 5) = 1000 + 250 + 250 = 1500
There is 1 question to complete.