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