Assume that multiplying a matrix \(G_1\) of dimension \(𝑝 × 𝑞\) with another…
2018
Assume that multiplying a matrix \(G_1\) of dimension \(𝑝 × 𝑞\) with another matrix \(G_2\) of dimension \(𝑞 × 𝑟\) requires \(𝑝𝑞𝑟\) scalar multiplications. Computing the product of n matrices \(G_1G_2G_3…G_n\) can be done by parenthesizing in different ways. Define \(G_i G_{i+1}\) as an explicitly computed pair for a given paranthesization if they are directly multiplied. For example, in the matrix multiplication chain \(G_1G_2G_3G_4G_5G_6\) using parenthesization \((G_1(G_2G_3))(G_4(G_5G_6)), G_2G_3\) and \(G_5G_6\) are the only explicitly computed pairs.
Consider a matrix multiplication chain \(F_1F_2F_3F_4F_5\), where matrices \(F_1, F_2, F_3, F_4\) and \(F_5\) are of dimensions \(2×25, 25×3, 3×16, 16×1\) and \(1×1000\), respectively. In the parenthesization of \(F_1F_2F_3F_4F_5\) that minimizes the total number of scalar multiplications, the explicitly computed pairs is/are
- A.
\(F_1F_2\)Â andÂ\(F_3F_4\)only - B.
\(F_2F_3\)Â only - C.
\(F_3F_4\)Â only - D.
\(F_1F_2\)Â andÂ\(F_4F_5\)only
Attempted by 63 students.
Show answer & explanation
Correct answer: C
Key insight: choose the small adjacent product first and use dynamic programming to find the minimal total cost.
Matrix dimensions: F1 is 2Ă—25, F2 is 25Ă—3, F3 is 3Ă—16, F4 is 16Ă—1, F5 is 1Ă—1000.
Costs for adjacent pair multiplications:
F1Ă—F2: 2Ă—25Ă—3 = 150; F2Ă—F3: 25Ă—3Ă—16 = 1,200; F3Ă—F4: 3Ă—16Ă—1 = 48; F4Ă—F5: 16Ă—1Ă—1000 = 16,000.
Dynamic choices (key steps): compute F3F4 first (cost 48) because it is cheapest; then multiply that by F2 (cost 25Ă—3Ă—1 = 75) to get the product F2(F3F4); then multiply by F1 (cost 2Ă—25Ă—1 = 50) to obtain F1(F2(F3F4)); finally multiply that by F5 (cost 2Ă—1Ă—1000 = 2,000).
Total minimal cost: 48 + 75 + 50 + 2,000 = 2,173 scalar multiplications.
Thus the optimal parenthesization is F1*(F2*(F3F4))*F5 (i.e., compute F3F4 first, then fold in F2, then F1, then F5). The only adjacent original pair explicitly multiplied in this optimal plan is F3F4.
A video solution is available for this question — log in and enroll to watch it.