# 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 and then of order .
2.
For each of the abve DAGs, give and together with the speed-up per processor (for a given number of nodes ).
optional
Generalize the above results to the case of the multiplication of two square matrices of order .

Marc Moreno Maza
2008-02-07