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$ .