Source-linked AI summary
Minimizing Communication in Linear Algebra
Grey Ballard, James Demmel, Olga Holtz, Oded Schwartz
TL;DR
The paper asks how communication lower bounds for matrix multiplication can extend across direct linear algebra and related computations. It develops a segment-based geometric proof and applies it to bandwidth and latency across dense or sparse, sequential or parallel settings. The resulting bounds cover broad algorithmic classes, with dense-case attainability but remaining scope limitations and open problems.
Problem
The paper addresses the need for communication lower bounds beyond conventional matrix multiplication, including broader linear-algebra algorithms and both bandwidth and latency costs.
Method
The paper partitions computations into segments of M memory operations, bounds evaluations per segment using a geometric argument, and extends the framework to compositions and related algorithms.
Results
The framework covers most dense and sparse direct linear-algebra algorithms, sequential and parallel settings, bandwidth and latency, compositions, and certain graph algorithms; dense-case bounds are attainable.
Takeaways & Limitations
Communication minimization can be analyzed through general lower bounds rather than separately for each operation, while optimized algorithms attain the dense bounds described.
Takeaways & Limitations
For sufficiently rectangular or sparse problems, the communication bound may fall below the trivial input-plus-output bound, whose joint attainability remains an open question.
Abstract
from arXiv · showhide
In 1981 Hong and Kung proved a lower bound on the amount of communication needed to perform dense, matrix-multiplication using the conventional $O(n^3)$ algorithm, where the input matrices were too large to fit in the small, fast memory. In 2004 Irony, Toledo and Tiskin gave a new proof of this result and extended it to the parallel case. In both cases the lower bound may be expressed as $Ω$(#arithmetic operations / $\sqrt{M}$), where M is the size of the fast memory (or local memory in the parallel case). Here we generalize these results to a much wider variety of algorithms, including LU factorization, Cholesky factorization, $LDL^T$ factorization, QR factorization, algorithms for eigenvalues and singular values, i.e., essentially all direct methods of linear algebra. The proof works for dense or sparse matrices, and for sequential or parallel algorithms. In addition to lower bounds on the amount of data moved (bandwidth) we get lower bounds on the number of messages required to move it (latency). We illustrate how to extend our lower bound technique to compositions of linear algebra operations (like computing powers of a matrix), to decide whether it is enough to call a sequence of simpler optimal algorithms (like matrix multiplication) to minimize communication, or if we can do better. We give examples of both. We also show how to extend our lower bounds to certain graph theoretic problems. We point out recently designed algorithms for dense LU, Cholesky, QR, eigenvalue and the SVD problems that attain these lower bounds; implementations of LU and QR show large speedups over conventional linear algebra algorithms in standard libraries like LAPACK and ScaLAPACK. Many open problems remain.
1 Introduction
The paper generalizes communication lower bounds from conventional matrix multiplication to broad classes of dense and sparse linear-algebra and graph algorithms, covering bandwidth and latency in sequential and parallel settings.
- 1 Introduction: The paper derives both bandwidth bounds for total words moved and latency bounds for the number of messages sent.Latency follows by dividing the bandwidth lower bound by the largest possible message size, the memory size M.
- 1 Introduction: The lower bound applies to data movement between fast and slow memory sequentially or between processor-local memories in parallel computation.In the parallel case, estimating an overall bound requires assumptions such as memory balance.
- 1 Introduction: The work generalizes Hong–Kung and Irony–Toledo–Tiskin lower bounds to most direct linear-algebra methods, including dense or sparse factorizations and transformations.Covered problems include BLAS operations, LU, Cholesky, LDLT, QR, eigenvalue, and singular-value computations.
- 1 Introduction: The framework extends beyond individual operations to compositions of linear-algebra computations and certain graph algorithms, including All-Pairs-Shortest-Path.It distinguishes cases where chaining optimized component algorithms is optimal from cases where a better combined algorithm exists.
- 1 Introduction: In dense settings, all stated lower bounds are attainable, although parallel attainability is subject to polylogP factors and minimal O(n^2/P) storage per processor.Recent optimal algorithms for dense LU, Cholesky, QR, eigenvalue problems, and SVD are not part of LAPACK or ScaLAPACK.
2 First Lower Bound
The first lower bound partitions computation into communication-sized segments, bounds evaluations per segment geometrically, and converts that bound into bandwidth and latency lower bounds.
- 2 First Lower Bound: The proof divides instructions into segments containing exactly M load and store operations, bounds evaluations per segment by F, and scales by the total evaluation count G.The resulting lower bound is based on at least floor(G/F) complete segments, each contributing M loads or stores.
- 2 First Lower Bound: Loomis–Whitney bounds the number of lattice-point evaluations in a segment from projections representing the distinct operands and destinations in fast memory.The model permits overlapping input, output, and accumulator addresses but assumes each result destination is computed only once.
- 2 First Lower Bound: Theorem 2 gives a bandwidth lower bound for evaluating the general computation when no operand is created and discarded without causing memory traffic.The no-S2/D2 condition is what keeps the relevant operand count bounded during each segment.
- 2 First Lower Bound: The bound may need refinement when input and output sizes dominate, when matrices are small enough to fit in fast memory, or when overlap-specific accounting strengthens it.A problem-dependent overlap analysis can increase the lower bound by as much as a factor of 8.
- 2 First Lower Bound: Corollary 3 converts the bandwidth bound into a latency bound by dividing by the maximum message size M.The result lower-bounds the number of messages required to communicate the computation's data.
- 2 First Lower Bound: The same lower-bound framework applies across nested memory hierarchies, providing bounds between every pair of adjacent levels.This extends the communication analysis beyond a two-level memory model.
3 Consequences for BLAS, LU, Cholesky, and LDLT
Theorem 2 yields communication lower bounds for conventional dense or sparse BLAS operations and direct factorizations, in sequential and parallel settings. Dense algorithms attain these bounds in several important cases, while sparse attainability and some latency goals remain unresolved.
- Matrix multiplication: Ω(#arithmetic operations / √M) words is the bandwidth lower bound for sequential multiplication of explicitly stored matrices, with M fast-memory capacity.For dense n-by-r times r-by-m multiplication, the bound specializes to a term proportional to n·r·m/√M, subject to input-output terms.
- Matrix multiplication: Well-known dense algorithms nearly attain the combined bandwidth lower bound, while latency attainment can require recursive block storage or space-filling-curve layouts.The corresponding sparse case lacks the same attainability result.
- Matrix multiplication: Memory-balanced parallel matrix multiplication requires at least one processor to communicate a lower-bounded number of words, with the bound expressed using its multiplication count and local memory.The result assumes the input and output data are distributed in a memory-balanced way across P processors.
- BLAS: Theorem 2 applies to conventional BLAS3 operations, including transposed, triangular, symmetric, Hermitian, and triangular-solve computations.The extension covers operations such as TRSM without changing the lower-bound argument.
- LU factorization: The lower-bound framework applies to LU and incomplete LU despite overwritten inputs, pivoting, omitted entries, and sparsity-dependent operation counts.For sparse LU, counting only multiplications that contribute to retained L or U results avoids overstating the required work when cancellations or zero structure eliminate partial sums.
- LU factorization: Dense LU algorithms can attain bandwidth bounds, but simultaneous bandwidth-and-latency optimality may require nonconventional stable pivoting and remains unavailable across multiple sequential memory levels.The ScaLAPACK parallel implementation attains bandwidth modulo O(log P) but not latency; another parallel algorithm attains both modulo O(log P).
- Cholesky and LDL^T: For sparse Cholesky on a two-dimensional 5-point stencil, the bandwidth lower bound is attainable by nested dissection, and the framework also applies to LDL^T.For LDL^T, the multiplication count is about half the Cholesky count, n^3/6 + O(n^2), with storage n(n + 1)/2.
4 Applying Orthogonal Transformations
The paper develops a distinct lower-bound argument for algorithms applying orthogonal transformations, covering QR, eigenvalue, and SVD computations. It derives bandwidth bounds for QR and matrix reductions, while identifying limitations for Hessenberg eigenvalue iteration and generalized eigenproblems.
- Scope and method: Orthogonal-transformation algorithms require a separate lower-bound argument because Loomis–Whitney counting alone cannot bound segment arithmetic operations.The class includes QR factorization, standard eigenvalue and eigenvector algorithms, and the SVD.
- QR model: QR analysis allows arbitrarily blocked Householder sequences that make progress without refilling zeros deliberately created earlier.This generality covers transformations that zero only parts of columns and supports applications beyond conventional QR.
- QR factorization: Θ(mn2) multiplies in dense m-by-n QR yield a bandwidth lower bound of Ω(mn2/√M) up to constants and an additive −M term.The bound applies to sequential Householder-based QR, with G denoting the update multiplications.
- QR model limitations: The QR proof cannot use Loomis–Whitney directly because a segment may contain Θ(M3/2) operations despite having too many Z(k,j) arguments.A second limitation is that QR behaves differently from Cholesky, so the identity R^T R = A^T A does not transfer Cholesky bounds.
- Matrix reductions: The same approach gives Ω(n3/√M) bandwidth lower bounds for dense reductions to Hessenberg, tridiagonal, or bidiagonal form.These results cover left and/or right Householder transformations under the progress restriction.
- Eigenvalue and SVD problems: For Hessenberg eigenvalue iteration, the conjectured bound is Ω(mn2/√M), but practical choices of m≤256 limit its applicability.A divide-and-conquer approach for dense eigenproblems and the SVD uses QR and matrix multiplication and attains the stated communication lower bounds.
5 Lower Bounds for Compositions of Linear Algebra Operations
The paper extends communication lower bounds to composed linear algebra computations, including cases with formula-generated inputs, scalar outputs, discarded intermediates, and arbitrary instruction interleavings. It shows when individually optimal routines suffice, when interleaving is necessary, and how the bounds apply to matrix powers and graph problems.
- General compositions: The framework targets composed operations whose intermediate outputs may remain in fast memory, inputs may be formula-generated, outputs may be scalar, or results may be discarded.These cases motivate lower bounds for globally optimized programs rather than separately optimized stages.
- General compositions: The lower bound is designed to cover arbitrary interleavings of instructions across operations, including computations sharing a common input matrix.This addresses whether global scheduling can reduce communication beyond straightforward composition.
- Eliminating input/output traffic: Imposing reads and writes removes difficult source/destination cases, allowing Theorem 2 to yield lower bounds even when formulas generate inputs or the final output is a scalar.For one example, at most n^2 writes and 2n^2 reads are imposed when each formula value is evaluated once; repeated evaluation changes the bound.
- Interleaved versus phased sequences: In the matrix-power cases covered by the bound, calling individually optimized routines is asymptotically optimal, while another composition can require careful interleaving to attain its lower bound.Thus composition does not have a single universal scheduling rule.
- Sequences of operations: For consecutive matrix powers, no interleaving can beat the bandwidth lower bound Ω(G/(8√M) − M − (t−2)n^2), with a smaller subtraction for sparse powers.The proof combines all operations under one index set and imposes writes for intermediate results.
- Graph-theoretic applications: Communication-avoiding matrix-power methods extend to APSP, and for t = o(log n) can outperform Floyd–Warshall on constant-degree inputs in both operation count and bandwidth.Recursive-block data structures provide optimal latency for the cited algorithms.
6 Attaining the lower bounds, and open problems
The section surveys algorithms attaining communication lower bounds across sequential and parallel dense linear algebra, while identifying substantial gaps for several problem classes and settings.
- Current state of attainment: Dense sequential algorithms attain all listed communication lower bounds, while dense parallel algorithms do so with minimal per-processor memory, modulo polylogP terms.Only a few of these algorithms appear in standard libraries such as LAPACK and ScaLAPACK.
- Current state of attainment: Dense LU and QR algorithms attain both bandwidth and latency lower bounds sequentially and in parallel, but require altered choices for pivoting or Q representation.Partial pivoting can be retained for bandwidth minimization in LU, and the usual Q representation can be retained for bandwidth minimization in QR.
- Current state of attainment: ScaLAPACK’s symmetric eigensolver and SVD minimize bandwidth modulo log P, but not latency, while its nonsymmetric eigensolver communicates substantially more.The symmetric eigensolver and SVD send O(n) messages, and the Hessenberg QR iteration has n-times higher bandwidth in the nonsymmetric case.
- Open problems: Open problems include LDL^T, replicated-memory 3D algorithms beyond matrix multiplication, Strassen-like algorithms, and sparse matrices generally.The paper also identifies unresolved attainment questions when its lower bound falls below the trivial inputs-plus-outputs bound for rectangular or sufficiently sparse matrices.