RECORD
Graph Expansion and Communication Costs of Fast Matrix Multiplication
Data Structures and Algorithms · Submitted 8 Sep 2011
abstract compiled · 2026-09-23 · no language-model review
The authors' main claim The communication cost of algorithms (also known as I/O-complexity) is shown to be closely related to the expansion properties of the corresponding computation graphs.
The compiled record
The paper's own sentences, arranged. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.
Open the compiled record
The abstract, sentence by sentence
The communication cost of algorithms (also known as I/O-complexity) is shown to be closely related to the expansion properties of the corresponding computation graphs. We demonstrate this on Strassen's and other fast matrix multiplication algorithms, and obtain first lower bounds on their communication costs. In the sequential case, where the processor has a fast memory of size $M$, too small to store three $n$-by-$n$ matrices, the lower bound on the number of words moved between fast and slow memory is, for many of the matrix multiplication algorithms, $\Omega((\frac{n}{\sqrt M})^{\omega_0}\cdot M)$, where $\omega_0$ is the exponent in the arithmetic count (e.g., $\omega_0 = \lg 7$ for Strassen, and $\omega_0 = 3$ for conventional matrix multiplication). With $p$ parallel processors, each with fast memory of size $M$, the lower bound is $p$ times smaller. These bounds are attainable both for sequential and for parallel algorithms and hence optimal. These bounds can also be attained by many fast algorithms in linear algebra (e.g., algorithms for LU, QR, and solving the Sylvester equation).
background contribution method result interpretation main claim
| # | sentence | role | the authors' own work | states the main conclusion | strength |
|---|---|---|---|---|---|
| s0 | The communication cost of algorithms (also known as I/O-complexity) is shown to be closely related to the expansion properties of the corresponding computation graphs. | result 0.50 | 0.35 | 0.38 | asserted 1.00 |
| s1 | We demonstrate this on Strassen's and other fast matrix multiplication algorithms, and obtain first lower bounds on their communication costs. | contribution 0.86 | 0.93 | 0.25 | asserted 1.00 |
| s2 | In the sequential case, where the processor has a fast memory of size $M$, too small to store three $n$-by-$n$ matrices, the lower bound on the number of words moved between fast and slow memory is, for many of the matrix multiplication algorithms, $\Omega((\frac{n}{\sqrt M})^{\omega_0}\cdot M)$, where $\omega_0$ is the exponent in the arithmetic count (e.g., $\omega_0 = \lg 7$ for Strassen, and $\omega_0 = 3$ for conventional matrix multiplication). | result 1.00 | 0.82 | 0.33 | asserted 1.00 |
| s3 | With $p$ parallel processors, each with fast memory of size $M$, the lower bound is $p$ times smaller. | result 1.00 | 0.81 | 0.10 | asserted 1.00 |
| s4 | These bounds are attainable both for sequential and for parallel algorithms and hence optimal. | result 0.72 | 0.83 | 0.41 | asserted 1.00 |
| s5 | These bounds can also be attained by many fast algorithms in linear algebra (e.g., algorithms for LU, QR, and solving the Sylvester equation). | result 0.88 | 0.64 | 0.08 | asserted 0.85 |
What was examined, and what was not
- arXiv listing abstract v1
- full text
- figures and tables
- references and citing sentences
- relations to other papers
- P abstract
- S sections
- T body sentences
- C citations
- R cross-paper relations
The paper
Original abstract
The communication cost of algorithms (also known as I/O-complexity) is shown to be closely related to the expansion properties of the corresponding computation graphs. We demonstrate this on Strassen's and other fast matrix multiplication algorithms, and obtain first lower bounds on their communication costs. In the sequential case, where the processor has a fast memory of size $M$, too small to store three $n$-by-$n$ matrices, the lower bound on the number of words moved between fast and slow memory is, for many of the matrix multiplication algorithms, $\Omega((\frac{n}{\sqrt M})^{\omega_0}\cdot M)$, where $\omega_0$ is the exponent in the arithmetic count (e.g., $\omega_0 = \lg 7$ for Strassen, and $\omega_0 = 3$ for conventional matrix multiplication). With $p$ parallel processors, each with fast memory of size $M$, the lower bound is $p$ times smaller. These bounds are attainable both for sequential and for parallel algorithms and hence optimal. These bounds can also be attained by many fast algorithms in linear algebra (e.g., algorithms for LU, QR, and solving the Sylvester equation).
Human review
How the literature uses it
What this paper does with the arXiv papers it cites
What it cites · 4 sentences without a confident label
Builds on 1 paper
-
In [ref] we generalize the results of [ref] regarding matrix multiplication, to obtain new lower bounds for a much wider variety of algorithms.
Minimizing Communication in Linear Algebra · Previous Work · 1.00
Uses the method or tool of 1 paper
-
In [ref] we use the approach of [ref] , based on the Loomis-Whitney geometric theorem [ref] , by embedding segments of the computation process into a three-dimensional cube.
Minimizing Communication in Linear Algebra · Previous Work · 0.97
Cites as background 1 paper
-
See [ref] for more details.
Minimizing Communication in Linear Algebra · Previous Work · 0.91
Discussion
Know something about this paper? Leave a comment, or highlight any passage above to comment on it.