Demmel, James; Grigori, Laura; Hoemmen, Mark; Langou, Julien Communication-optimal parallel and sequential QR and LU factorizations. (English) Zbl 1241.65028 SIAM J. Sci. Comput. 34, No. 1, A206-A239 (2012). Summary: 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. Cited in 61 Documents MSC: 65F05 Direct numerical methods for linear systems and matrix inversion 65Y05 Parallel numerical computation 65Y20 Complexity and performance of numerical algorithms 15A23 Factorization of matrices 65F25 Orthogonalization in numerical linear algebra 65F20 Numerical solutions to overdetermined systems, pseudoinverses Keywords:QR factorization; LU factorization; parallel computation; comparison of methods; numerical examples; Householder QR; “non-Strassen-like” QR; ScaLAPACK algorithms; parallel algorithm; rectangular matrices Software:CALU; MPI; LAPACK; BLOPEX; POOCLAPACK; ScaLAPACK PDFBibTeX XMLCite \textit{J. Demmel} et al., SIAM J. Sci. Comput. 34, No. 1, A206--A239 (2012; Zbl 1241.65028) Full Text: DOI arXiv