TL;DR
This paper extends graph expansion analysis to prove communication cost lower bounds for fast rectangular matrix multiplication algorithms. By treating computational steps as nodes in a graph, the authors demonstrate that data movement—not just arithmetic—is a fundamental bottleneck, and they provide the mathematical tools to determine if a specific algorithm is as efficient as theoretically possible.
What Problem Does This Paper Address?
In modern computing, moving data (communication) between memory levels or across a network is significantly more expensive in terms of time and energy than performing arithmetic (computation). While we have well-established lower bounds for "classical" $O(n^3)$ matrix multiplication and Strassen’s fast square matrix multiplication, rectangular matrix multiplication—where the matrices have different dimensions—remained less understood.
Previous methods for finding these bounds relied on "geometric embedding," which essentially maps the computation onto a 3D grid. However, fast algorithms (like Strassen-like methods) don't fit neatly into a grid. This paper addresses the need for a rigorous way to calculate the minimum amount of data movement required for recursive, fast rectangular matrix multiplication.
Methods
The authors utilize Graph Expansion Analysis. They represent an algorithm as a Computational Directed Acyclic Graph (CDAG), where nodes are operations and edges are data dependencies.
Key technical components include:
- Edge Expansion ($h(G)$): A measure of how well-connected a graph is. If a graph has high expansion, you cannot partition it into small pieces without cutting many edges. In computing terms, this means you cannot perform a chunk of work without moving a lot of data in and out of fast memory.
- The Partition Argument: A standard technique that divides the CDAG into "segments" of operations that fit into fast memory. By using expansion properties, the authors prove that each segment necessitates a certain amount of data transfer ($W$).
- Top-Down Construction: The authors provide a method to analyze the expansion of recursive CDAGs by looking at the "base case" (e.g., a small $3 \times 2 \times 2$ multiplication) and seeing how that expansion scales as the recursion deepens.
Datasets
As a theoretical paper in computer science, this work does not use empirical datasets. Instead, it evaluates and provides bounds for several landmark algorithms in the field:
- Bini et al. (1979): An approximate algorithm for $\langle 3, 2, 2 \rangle$ multiplication using 10 multiplications.
- Hopcroft and Kerr (1971): An algorithm for $\langle 3, 2, 3 \rangle$ multiplication using 15 multiplications.
- Strassen’s Algorithm: Used as a baseline for square matrix cases.
Key Insights and Ideas
- The "Largest Matrix" Rule: The communication bound is typically dominated by the expansion of the largest of the three matrices involved (the two inputs or the one output). If the output matrix is the largest, the "decoding" graph determines the bound; if an input is largest, the "encoding" graph does.
- Expansion vs. Geometry: Graph expansion succeeds where geometric methods fail because it captures the combinatorial structure of the algorithm rather than its physical layout.
- Handling Disconnected Graphs: Some fast algorithms (like Bini’s) have "disconnected" encoding or decoding graphs. The authors developed new corollaries to handle these cases, proving that even if the graph is split into pieces, a lower bound still exists as long as those pieces are large enough to exceed fast memory capacity.
- Optimality of Naive Recursion: A major takeaway is that for many of these fast algorithms, the standard recursive implementation is already communication-optimal (it hits the lower bound).
Key Results
The paper establishes two main theorems for the communication cost ($W$) given a fast algorithm $\langle m, n, p \rangle = q$ with fast memory size $M$:
- For connected decoding graphs: $W = \Omega\left( \frac{q^t}{M^{\log_{mp} q - 1}} \right)$. This bound is shown to be tight when the output matrix is the largest.
- For connected encoding graphs: A similar bound is provided, $W = \Omega\left( \frac{q^t}{t^{\log_N q} M^{\log_N q - 1}} \right)$, where $N$ is the size of the input matrix.
The authors provide a comprehensive table (Table 1) applying these theorems to various versions of Bini’s and Hopcroft-Kerr’s algorithms, identifying exactly which ones are "tight" (optimal) and which ones have potential for further optimization.
Limitations and Future Work
- Hybrid Algorithms: The current analysis assumes the same base case is used at every level of recursion. It does not yet cover "hybrid" algorithms that might switch between different base cases (e.g., using Bini for one level and Strassen for the next).
- Non-Recursive Algorithms: The expansion analysis relies heavily on the recursive structure of the CDAG. Algorithms that are not defined recursively or are not bilinear are not covered.
- Small Output Matrices: The authors note that when the output matrix is significantly smaller than the input matrices, or when the largest graph is disconnected, their current bounds are not always tight, leaving room for more refined future analysis.
- Parallel Scaling: While the paper focuses on sequential machines, the authors suggest these bounds can be generalized to distributed-memory parallel models.
Summary updated