Minimizing communication in numerical linear algebra

DOI10.1137/090769156MaRDI QIDQ3112398zbMATH OpenOpenAlexFDO

Authors Grey Ballard, Oded Schwartz, James Demmel, Olga Holtz

Publication date 16 January 2012

Published in SIAM Journal on Matrix Analysis and Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0905.2485

zbMATH Keywords

communication costlinear algebra algorithmsload and store operationslower boundLU factorizationmatrix multiplicationQR factorizationsparse Cholesky factorization

Mathematics Subject Classification ID

Parallel numerical computation (65Y05) Numerical algorithms for specific classes of architectures (65Y10) Complexity and performance of numerical algorithms (65Y20) Analysis of algorithms and problem complexity (68Q25) Parallel algorithms in computer science (68W10) Distributed algorithms (68W15) Analysis of algorithms (68W40)

Abstract: 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 $Omega$(#arithmetic operations / $sqrtM$), 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, $LD{L}^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.

Recommendations

• Communication lower bounds and optimal algorithms for numerical linear algebra
• Communication-optimal parallel and sequential Cholesky decomposition
• Avoiding communication in numerical linear algebra
• Graph expansion and communication costs of fast matrix multiplication
• scientific article; zbMATH DE number 3999131

Cited in

(52)

• Communication lower bounds for distributed-memory matrix multiplication
• High-performance statistical computing in the computing environments of the 2020s
• L-sweeps: a scalable, parallel preconditioner for the high-frequency Helmholtz equation
• Simultaneous band reduction of two symmetric matrices
• Distributed-memory hierarchical interpolative factorization
• A cache-optimal alternative to the unidirectional hierarchization algorithm
• Algorithm 953: Parallel library software for the multishift QR algorithm with aggressive early deflation
• A parallel algorithm for calculation of determinants and minors using arbitrary precision arithmetic
• Communication-optimal parallel and sequential QR and LU factorizations
• An accelerated divide-and-conquer algorithm for the bidiagonal SVD problem
• Minimizing synchronizations in sparse iterative solvers for distributed supercomputers
• Computing Fundamental Matrix Decompositions Accurately via the Matrix Sign Function in Two Iterations: The Power of Zolotarev's Functions
• CALU: A communication optimal LU factorization algorithm
• A factored sparse approximate inverse preconditioned conjugate gradient solver on graphics processing units
• scientific article; zbMATH DE number 1375602 (Why is no real title available?)
• A direct solver for variable coefficient elliptic PDEs discretized via a composite spectral collocation method
• A generalization of s-step variants of gradient methods
• scientific article; zbMATH DE number 1760022 (Why is no real title available?)
• Low Rank Approximation of a Sparse Matrix Based on LU Factorization with Column and Row Tournament Pivoting
• Introduction to communication avoiding algorithms for direct methods of factorization in linear algebra
• Communication lower bounds and optimal algorithms for numerical linear algebra
• Graph expansion analysis for communication costs of fast rectangular matrix multiplication
• On the cost of iterative computations
• Numerical algorithms for high-performance computational science
• Communication lower bounds of bilinear algorithms for symmetric tensor contractions
• Communication-optimal parallel and sequential Cholesky decomposition
• An input/output efficient algorithm for Hessenberg reduction
• Avoiding communication in numerical linear algebra
• Communication-avoiding symmetric-indefinite factorization
• Communication Avoiding ILU0 Preconditioner
• Randomized QR with column pivoting
• Graph expansion and communication costs of fast matrix multiplication
• Pebbling Game and Alternative Basis for High Performance Matrix Multiplication
• Accelerating the reduction to upper Hessenberg, tridiagonal, and bidiagonal forms through hybrid GPU-based computing
• A Structure-Preserving Divide-and-Conquer Method for Pseudosymmetric Matrices
• Minimizing Communication in the Multidimensional FFT
• Performance Analysis of the Householder-Type Parallel Tall-Skinny QR Factorizations Toward Automatic Algorithm Selection
• Aligning the representation and reality of computation with asynchronous logic automata
• Fast and accurate randomized algorithms for linear systems and eigenvalue problems
• Developing variable s-step CGNE and CGNR algorithms for non-symmetric linear systems
• Task-based parallel programming for scalable matrix product algorithms
• Finding solution of linear systems via new forms of BiCG, BiCGstab and CGS algorithms
• Fast and inverse-free algorithms for deflating subspaces
• A new modified variable s-step BiCGSTAB method with regularization for solving shifted linear systems
• Variable s-step technique for planar algorithms in solving indefinite linear systems
• An improved shifted CholeskyQR based on columns
• Efficient image reconstruction via regularized variable s-step conjugate gradient method for Sylvester matrix equations
• Communication lower bounds for nested bilinear algorithms via rank expansion of Kronecker products
• Generalized pseudospectral shattering and inverse-free matrix pencil diagonalization
• The swept rule for breaking the latency barrier in time advancing PDEs
• The method of polarized traces for the 2D Helmholtz equation
• Towards dense linear algebra for hybrid GPU accelerated manycore systems

Describes a project that uses

Uses Software

• LAPACK
• BLAS
• ScaLAPACK
• OSKI
• POOCLAPACK
• SBR Toolbox

This page was built for publication: Minimizing communication in numerical linear algebra

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3112398)