Project ForgeAssume that multiplying a matrix G1 of dimension p×q with another matrix G2 of dimension q×r requires pqr scalar multiplications. Computing the product of n matrices G1G2G3...Gn can be done by parenthesizing in different ways. Gi Gi+1 is an 'explicitly computed pair' for a given parenthesization if they are directly multiplied. Consider a matrix multiplication chain F1F2F3F4F5, where matrices F1, F2, F3, F4 and F5 are of dimensions 2×25, 25×3, 3×16, 16×1 and 1×1000, respectively. In the parenthesization of F1F2F3F4F5 that minimizes the total number of scalar multiplications, the explicitly computed pairs is/are
- AF1F2 and F3F4 only
- BF2F3 only
- F3F4 only
- DF1F2 and F4F5 only
Explanation
Standard matrix-chain DP over dims [2,25,3,16,1,1000] finds the minimum-cost parenthesization is F1(F2(F3F4))F5, with total cost 2173. Tracing the optimal splits: the top level splits as (F1F2F3F4)·F5, which itself splits as F1·(F2F3F4), which splits as F2·(F3F4). Only F3·F4 multiplies two matrices that are BOTH still 'atomic' (unmultiplied) at the moment of their multiplication — every other multiplication in this parenthesization involves at least one already-computed intermediate result, so F3F4 is the only explicitly computed pair.
Source: GATE CS 2018 (2018)
This question is part of a 15-day revision cycle — sign in and Project Forge will bring it back the day before you'd forget it.