Consider product of three matrices M1, M2 and M3 having w rows and x columns,…
2020
Consider product of three matrices M1, M2 and M3 having w rows and x columns, x rows and y columns, and y rows and z columns. Under what condition will it take less time to compute the product as (M1M2)M3 than to compute M1(M2M3) ?
- A.
Always take the same time
- B.
(1/x + 1/z) < (1/w + 1/y)
- C.
x > y
- D.
(w + x) > (y + z)
Attempted by 109 students.
Show answer & explanation
Correct answer: B
Let M1 be w×x, M2 be x×y, and M3 be y×z.
Computing (M1M2)M3 requires wxy multiplications for M1×M2, resulting in a w×y matrix. Multiplying this by M3 takes wyz multiplications. Total cost: wxy + wyz.
Computing M1(M2M3) requires xyz multiplications for M2×M3, resulting in an x×z matrix. Multiplying M1 by this takes wxz multiplications. Total cost: xyz + wxz.
For (M1M2)M3 to be faster, we need wxy + wyz < xyz + wxz. Dividing by wxyz gives 1/x + 1/z < 1/w + 1/y.