Question 3

We consider Strassen's algorithm for multiplying matrices described on Pages 11 to 13 of the introductory chapter. We assume that every operation on coefficients (addition and multiplication) has a unit cost.
1.
Describe the computation directed acyclic graph associated with the multiplication of two square matrices of order $ 2$ and then of order $ 4$ .
2.
For each of the abve DAGs, give $ T_1$ and $ T_{\infty}$ together with the speed-up per processor $ E(n,p)$ (for a given number of nodes $ p$ ).
optional
Generalize the above results to the case of the multiplication of two square matrices of order $ 2^k$ .

Marc Moreno Maza
2008-02-07