GATE 2018 CS – Question 41
Assume that multiplying a matrix $G_1$ of dimension $p\times q$ with another matrix $G_2$ of dimension $q\times r$ requires $pqr$ scalar multiplications. Computing the product of $n$ matrices $G_1G_2G_3\dots G_n$ can be done by parenthesizing in different ways. Define $G_iG_{i+1}$ as an explicitly computed pair for a given parenthesization 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\times25$, $25\times3$, $3\times16$, $16\times1$ and $1\times1000$, 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
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: (C) $F_3F_4$ only
Explanation
Dimensions: $F_1:2\times25$, $F_2:25\times3$, $F_3:3\times16$, $F_4:16\times1$, $F_5:1\times1000$.
Multiplying chains whose inner dimension is 1 is very cheap, so the trick is to collapse the small-dimension matrices first and multiply by the big $1\times1000$ matrix last.
**Parenthesization $(F_1(F_2(F_3F_4)))F_5$**
1. $F_3F_4$: $3\cdot16\cdot1=48$, result $3\times1$.
2. $F_2(F_3F_4)$: $25\cdot3\cdot1=75$, result $25\times1$.
3. $F_1(\dots)$: $2\cdot25\cdot1=50$, result $2\times1$.
4. $\dots\times F_5$: $2\cdot1\cdot1000=2000$.
Total $=48+75+50+2000=2173$.
**Compare with $((F_1F_2)(F_3F_4))F_5$:** $150+48+6+2000=2204$. Larger.
Any grouping that multiplies $F_4F_5$ costs $16\cdot1\cdot1000=16000$, much larger.
So the optimum is $(F_1(F_2(F_3F_4)))F_5$, and the only explicitly computed pair is $F_3F_4$: option (C).