Communication-optimal parallel and sequential Cholesky decomposition

DOI10.1137/090760969MaRDI QIDQ5200261zbMATH OpenOpenAlexFDO

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

Publication date 1 August 2011

Published in SIAM Journal on Scientific Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0902.2537, http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.221.2762

zbMATH Keywords

bandwidth lower boundCholesky decompositioncommunication avoiding algorithmcommunication costslatencyLU factorizationmatrix multiplicationparallel computationQR factorization

Mathematics Subject Classification ID

Direct numerical methods for linear systems and matrix inversion (65F05) Parallel numerical computation (65Y05) Complexity and performance of numerical algorithms (65Y20)

Abstract: Numerical algorithms have two kinds of costs: arithmetic and communication, by which we mean either moving data between levels of a memory hierarchy (in the sequential case) or over a network connecting processors (in the parallel case). Communication costs often dominate arithmetic costs, so it is of interest to design algorithms minimizing communication. In this paper we first extend known lower bounds on the communication cost (both for bandwidth and for latency) of conventional (O(n^3)) matrix multiplication to Cholesky factorization, which is used for solving dense symmetric positive definite linear systems. Second, we compare the costs of various Cholesky decomposition implementations to these lower bounds and identify the algorithms and data structures that attain them. In the sequential case, we consider both the two-level and hierarchical memory models. Combined with prior results in [13, 14, 15], this gives a set of communication-optimal algorithms for O(n^3) implementations of the three basic factorizations of dense linear algebra: LU with pivoting, QR and Cholesky. But it goes beyond this prior work on sequential LU by optimizing communication for any number of levels of memory hierarchy.

Recommendations

• Minimizing communication in numerical linear algebra
• scientific article; zbMATH DE number 641618
• Communication-optimal parallel and sequential QR and LU factorizations
• Communication lower bounds and optimal algorithms for numerical linear algebra
• Avoiding communication in numerical linear algebra

Cited in

(11)

• Efficient and optimal parallel algorithms for Cholesky decomposition
• The red-blue pebble game on trees and DAGs with large input
• Solving a large scale radiosity problem on GPU-based parallel computers
• Communication-optimal parallel and sequential QR and LU factorizations
• Minimizing communication in numerical linear algebra
• Introduction to communication avoiding algorithms for direct methods of factorization in linear algebra
• Communication lower bounds and optimal algorithms for numerical linear algebra
• Comparison of Accuracy and Scalability of Gauss--Newton and Alternating Least Squares for CANDECOMC/PARAFAC Decomposition
• Avoiding communication in numerical linear algebra
• Communication-avoiding symmetric-indefinite factorization
• Accelerating the reduction to upper Hessenberg, tridiagonal, and bidiagonal forms through hybrid GPU-based computing

Describes a project that uses

Uses Software

• LAPACK
• ScaLAPACK
• mctoolbox

This page was built for publication: Communication-optimal parallel and sequential Cholesky decomposition

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