# The I/O complexity of Strassen's matrix multiplication with recomputation

Preprint · Gianfranco Bilardi, Lorenzo De Stefani

- Archive id: arxiv:1605.02224
- Published: 2016-05-07
- arXiv: https://arxiv.org/abs/1605.02224
- Source URL: https://arxiv.org/abs/1605.02224
- PDF: https://arxiv.org/pdf/1605.02224
- Provenance: arxiv

## Abstract

A tight $Ω((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.

_Abstract reproduced under CC0-1.0 (arXiv descriptive metadata)._

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.