The I/O Complexity of Strassen’s Matrix Multiplication with Recomputation

A tight \(\varOmega ((n/\sqrt{M})^{\log _2 7}M)\) lower bound is derived on the I/O 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.