  A tight $\Omega((n/\sqrt{M})^{\log_2 7}M)$ lower bound is derived on the \io
complexity of Strassen's algorithm to multiply two $n \times n$ matrices, in a
two-level storage hierarchy with $M$ words of fast memory. A proof technique is
introduced, which exploits the Grigoriev's flow of the matrix multiplication
function as well as some combinatorial properties of the Strassen computational
directed acyclic graph (CDAG). Applications to parallel computation are also
developed. The result generalizes a similar bound previously obtained under the
constraint of no-recomputation, that is, that intermediate results cannot be
computed more than once. For this restricted case, another lower bound
technique is presented, which leads to a simpler analysis of the \io complexity
of Strassen's algorithm and can be readily extended to other "Strassen-like"
algorithms.
