Minimizing Communication in Numerical Linear Algebra

By Grey Ballard, J. Demmel, Olga Holtz, Oded Schwartz. 2009

281 citations recorded by the source corpus.

In 1981 Hong and Kung proved a lower bound on the amount of communication (amount of data moved between a small, fast memory and large, slow memory) needed to perform dense, n-by-n matrix multiplication using the conventional O(n3) 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 (where communication means the amount of data moved between processors). In both cases the lower bound may be expressed as Ω(#arithmetic_operations/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, LDLT factorization, QR factorization, the Gram–Schmidt algorithm, and 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 para...

Subfields: Computational Theory and Mathematics, Computer Networks and Communications, Hardware and Architecture, Optimization & Training

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

In Computer Networks and Communications

In Hardware and Architecture

In Optimization & Training

Citations in the corpus

Mesh-TensorFlow: Deep Learning for Supercomputers (2018, background): “(See [4, 7, 12] for rigorous communication lower bounds analyses.)”
Communication lower bounds and optimal algorithms for programs that reference arrays - Part 1 (2013, methodology): “We begin by reviewing the geometric model of matrix multiplication introduced in [13], describe how it was extended to more general linear algebra algorithms in [4], and finally show how to generalize it to the class of programs considered in this work.”
Stable and Efficient Spectral Divide and Conquer Algorithms for the Symmetric Eigenvalue Decomposition and the SVD (2013, background): “basic matrix operations, including matrix multiplication, the Cholesky factorization and the QR factorization (without pivoting) [9], [10], [11], [17].”
Integrated Model and Data Parallelism in Training Neural Networks (2017, background): “At least one matrix is replicated multiple times, which often results in an asymptotic reduction in communication costs [1].”
Communication-Optimal Parallel Recursive Rectangular Matrix Multiplication (2013, background): “For square matrix multiplication, communication cost lower bounds have been proved [22], [5], [2], suggesting that known 2D algorithms (such as SUMMA) and 3D algorithms [7], [1] are only optimal in certain memory ranges.”
Minimax Bounds on Stochastic Batched Convex Optimization (2018, background): “As a consequence, processor manufacturers and algorithm designers have moved toward increased parallelism, with reduced communication among processors, as the way to continue to see increased computing performance (Fuller and Millett, 2011; Ballard et al., 2011).”
AI and Memory Wall (2024, unknown): “A notable example of this in numerical linear algebra is the family of communication avoiding algorithms [1].”