Graph Expansion Analysis for Communication Costs of Fast Rectangular Matrix Multiplication

Grey Ballard, James Demmel, Olga Holtz, Benjamin Lipshitz, Oded Schwartz

Abstract

Graph expansion analysis of computational DAGs is useful for obtaining communication cost lower bounds where previous methods, such as geometric embedding, are not applicable. This has recently been demonstrated for Strassen's and Strassen-like fast square matrix multiplication algorithms. Here we extend the expansion analysis approach to fast algorithms for rectangular matrix multiplication, obtaining a new class of communication cost lower bounds. These apply, for example to the algorithms of Bini et al. (1979) and the algorithms of Hopcroft and Kerr (1971). Some of our bounds are proved to be optimal.

Introduction

In modern high-performance computing, the primary bottleneck is often not the arithmetic operations themselves, but the movement of data between memory levels or across networks. This "communication cost" dominates both time and energy consumption. While communication lower bounds for classical $O(n^3)$ matrix multiplication and Strassen’s square matrix multiplication are well-understood, fast rectangular matrix multiplication—where matrices have varying dimensions—has lacked a rigorous analytical framework.

Previous bounding techniques relied on geometric embedding, which maps computations onto a 3D grid. However, fast recursive algorithms do not conform to these rigid structures. This paper addresses this gap by extending graph expansion analysis to provide a mathematical foundation for determining the minimum data movement required for recursive, fast rectangular matrix multiplication.

Methodology: Graph Expansion on CDAGs

The authors represent algorithms as Computational Directed Acyclic Graphs (CDAGs), where nodes represent operations and edges represent data dependencies. The core of the analysis lies in Edge Expansion ($h(G)$), a metric of graph connectivity. High expansion implies that a graph cannot be partitioned into small segments without cutting many edges, which translates to a requirement for significant data transfer ($W$) when performing a chunk of work in fast memory.

To derive these bounds, the authors utilize a Partition Argument, dividing the CDAG into segments that fit within a fast memory of size $M$. By analyzing the expansion of the "base case" (e.g., a small $3 \times 2 \times 2$ multiplication) and observing how it scales through a Top-Down Construction as recursion deepens, they can calculate the total communication cost.

The "Largest Matrix" Rule and CDAG Structure

A central insight of this work is that the communication bound is typically dictated by the expansion of the largest of the three matrices involved: the two inputs ($A$ and $B$) or the output ($C$).

Recursive structure of encoding and decoding for rectangular matrix multiplication.

As illustrated in the figure above, the algorithm is composed of encoding steps for the inputs ($Enc_t A, Enc_t B$) and a decoding step for the output ($Dec_t C$). If the output matrix is the largest, the expansion of the decoding graph determines the bound; conversely, if an input matrix is larger, the encoding graph dominates. This combinatorial approach succeeds where geometric methods fail because it captures the inherent structure of the algorithm rather than its physical layout.

Key Results and Algorithm Analysis

The paper establishes two primary theorems for communication cost $W$ given a fast algorithm $\langle m, n, p \rangle = q$ with fast memory size $M$:

  1. For connected decoding graphs: $W = \Omega\left( \frac{q^t}{M^{\log_{mp} q - 1}} \right)$. This bound is tight when the output matrix is the largest.
  2. For connected encoding graphs: $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 applied these theorems to several landmark algorithms:

  • 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.

A significant finding is that for many of these algorithms, the standard recursive implementation is already communication-optimal, meaning it naturally achieves the theoretical lower bound.

Limitations and Future Directions

While this work provides a robust framework, several areas remain for future exploration. The current analysis assumes a consistent base case throughout recursion and does not yet account for "hybrid" algorithms that switch between different base cases (e.g., combining Bini and Strassen steps). Additionally, the bounds are less tight when the output matrix is significantly smaller than the inputs or when the largest graph is disconnected. Finally, while the focus here is on sequential machines, the authors suggest these expansion-based bounds can be generalized to distributed-memory parallel models to optimize large-scale scientific computing.

Summary updated

Abstract

Graph expansion analysis of computational DAGs is useful for obtaining communication cost lower bounds where previous methods, such as geometric embedding, are not applicable. This has recently been demonstrated for Strassen's and Strassen-like fast square matrix multiplication algorithms. Here we extend the expansion analysis approach to fast algorithms for rectangular matrix multiplication, obtaining a new class of communication cost lower bounds. These apply, for example to the algorithms of Bini et al. (1979) and the algorithms of Hopcroft and Kerr (1971). Some of our bounds are proved to be optimal.
BibTeX
@inproceedings{ballard2012graph,
  author = {Grey Ballard and James Demmel and Olga Holtz and Benjamin Lipshitz and Oded Schwartz},
  title = {{Graph Expansion Analysis for Communication Costs of Fast Rectangular Matrix Multiplication}},
  booktitle = {MedAlg},
  year = {2012},
  url = {https://openreview.net/forum?id=9QdwANyPy3Y},
}
Figure