Communication-optimal Parallel and Sequential QR and LU Factorizations

By J. Demmel, Laura Grigori, Mark Hoemmen, J. Langou. SIAM Journal on Scientific Computing, 2008

483 citations recorded by the source corpus.

We present parallel and sequential dense QR factorization algorithms that are both optimal (up to polylogarithmic factors) in the amount of communication they perform and just as stable as Householder QR. We prove optimality by deriving new lower bounds for the number of multiplications done by “non-Strassen-like” QR, and using these in known communication lower bounds that are proportional to the number of multiplications. We not only show that our QR algorithms attain these lower bounds (up to polylogarithmic factors), but that existing LAPACK and ScaLAPACK algorithms perform asymptotically more communication. We derive analogous communication lower bounds for LU factorization and point out recent LU algorithms in the literature that attain at least some of these lower bounds. The sequential and parallel QR algorithms for tall and skinny matrices lead to significant speedups in practice over some of the existing algorithms, including LAPACK and ScaLAPACK, for example, up to 6.7 times over ScaLAPACK. A performance model for the parallel algorithm for general rectangular matrices predicts significant speedups over ScaLAPACK.

Subfields: Computational Theory and Mathematics, Computer Networks and Communications

View Paper: https://www.semanticscholar.org/paper/13d75d2792f5f47120312c5a113876c30caae7ae

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

Citations in the corpus

Speeding Up Distributed Machine Learning Using Codes (2015, background): “The sole objective of the master is to transmit A3 to the first worker and A4 to the second.”
Randomized numerical linear algebra: Foundations and algorithms (2020, background): “Parker (1995) inspired many subsequent papers, including (Baboulin, Li and Rouet 2014, Trogdon 2017, Demmel et al. 2012, Baboulin, Dongarra, Rémy, Tomov and Yamazaki 2017, Pan and Zhao 2017).”
PLASMA (2019, methodology): “The approach was described in [Demmel et al. 2008], and extended e.”
Parallel data-driven decomposition algorithm for large-scale datasets: with application to transitional boundary layers (2016, methodology): “The TSQR algorithm of [3] represents the cornerstone of our parallel DMD algorithm; it was initially applied in the context of DMD using the MapReduce programming framework by [1], a schematic of which is shown in Fig.”
Ernest: Efficient Performance Prediction for Large-Scale Advanced Analytics (2016, methodology): “For example, we use two machine learning kernels: (a) A least squares solver used in convex optimization [37] and (b) a matrix multiply operation [75], and measure their performance for similar capacity configurations across a number of instance types.”
Communication-Efficient Distributed Statistical Inference (2016, background): “It is thus noteworthy that over the past decade there has been a revolution in numerical linear algebra in which new “communication-avoiding” algorithms have been developed to replace classical matrix routines (Demmel et al. 2012).”
Minimizing Communication in Numerical Linear Algebra (2009, methodology): “Thus, for a lower bound of Ω( mn 2 ) total multiplies for a dense m -by- n matrix given by [DGHL08a], there are Ω( mn 2 ) multiplies of the form given by (7).”
KeystoneML: Optimizing Pipelines for Large-Scale Advanced Analytics (2016, background): “• Exact solvers [25] that compute closed form solutions to the least squares loss and return an X to high precision.”
Stable and Efficient Spectral Divide and Conquer Algorithms for the Symmetric Eigenvalue Decomposition and the SVD (2013, background): “Considerable progress has been made in devising linear algebra algorithms that minimize communication, and for the above basic matrix operations implementations are known that asymptotically attain the lower bounds [10], [11], [12], [19].”