Communication-optimal parallel and sequential QR and LU factorizations
From MaRDI portal
``non-Strassen-like QRcomparison of methodsHouseholder QRLU factorizationnumerical examplesparallel algorithmparallel computationQR factorizationrectangular matricesScaLAPACK algorithms
Factorization of matrices (15A23) Direct numerical methods for linear systems and matrix inversion (65F05) Numerical solutions to overdetermined systems, pseudoinverses (65F20) Orthogonalization in numerical linear algebra (65F25) Parallel numerical computation (65Y05) Complexity and performance of numerical algorithms (65Y20)
Abstract: 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 extending known lower bounds on communication bandwidth for sequential and parallel matrix multiplication to provide latency lower bounds, and show these bounds apply to the LU and QR decompositions. 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 also point out recent LU algorithms in the literature that attain at least some of these lower bounds.
Recommendations
Cited in
(96)- Random projections for Bayesian regression
- Randomized algorithms for distributed computation of principal component analysis and singular value decomposition
- Parallel \(\mathcal {H}\)-matrix arithmetic on distributed-memory systems
- High-performance implementation of Chebyshev filter diagonalization for interior eigenvalue computations
- Varying the \(s\) in your \(s\)-step GMRES
- Fast multipole preconditioners for sparse matrices arising from elliptic equations
- Block Gram-Schmidt algorithms and their stability properties
- The red-blue pebble game on trees and DAGs with large input
- A parallel and streaming dynamic mode decomposition algorithm with finite precision error analysis for large data
- GMRES with embedded ensemble propagation for the efficient solution of parametric linear systems in uncertainty quantification of computational models
- Linear-time CUR approximation of BEM matrices
- Benefits from using mixed precision computations in the ELPA-AEO and ESSEX-II eigensolver projects
- GMRES algorithms over 35 years
- Enlarged Krylov subspace conjugate gradient methods for reducing communication
- A randomized blocked algorithm for efficiently computing rank-revealing factorizations of matrices
- Considerations on the Implementation and Use of Anderson Acceleration on Distributed Memory and GPU-based Parallel Computers
- A distributed and incremental SVD algorithm for agglomerative data analysis on large networks
- A parallel algorithm for calculation of determinants and minors using arbitrary precision arithmetic
- LU factorization with panel rank revealing pivoting and its communication avoiding version
- Gram-Schmidt orthogonalization: 100 years and more
- Data Driven Modal Decompositions: Analysis and Enhancements
- Scaling LAPACK panel operations using parallel cache assignment
- CALU: A communication optimal LU factorization algorithm
- Cholesky and Gram-Schmidt orthogonalization for tall-and-skinny QR factorizations on graphics processors
- Communication avoiding rank revealing QR factorization with column pivoting
- Increasing the performance of the Jacobi-Davidson method by blocking
- Nonnegative diagonals and high performance on low-profile matrices from Householder QR
- Simultaneous multidiagonalization for the CS decomposition
- FaIMS: a fast algorithm for the inverse medium problem with multiple frequencies and multiple sources for the scalar Helmholtz equation
- The singular value decomposition: anatomy of optimizing an algorithm for extreme scale
- Low Rank Approximation of a Sparse Matrix Based on LU Factorization with Column and Row Tournament Pivoting
- Avoiding Communication in Primal and Dual Block Coordinate Descent Methods
- Introduction to communication avoiding algorithms for direct methods of factorization in linear algebra
- Adapting regularized low-rank models for parallel architectures
- Communication lower bounds and optimal algorithms for numerical linear algebra
- Numerical algorithms for high-performance computational science
- Rounding error analysis of mixed precision block Householder QR algorithms
- Parallel Algorithms for Tensor Train Arithmetic
- Scaling up parallel computation of tiled QR factorizations by a distributed scheduling runtime system and analytical modeling
- Performance of the low-rank TT-SVD for large dense tensors on modern multicore CPUs
- GPU parameter tuning for tall and skinny dense linear least squares problems
- Randomized Projection for Rank-Revealing Matrix Factorizations and Low-Rank Approximations
- Parallel \textit{QR} factorization of block-tridiagonal matrices
- Iteratively reweighted FGMRES and FLSQR for sparse reconstruction
- Communication-optimal parallel and sequential Cholesky decomposition
- Shifted Cholesky QR for computing the QR factorization of ill-conditioned matrices
- Communication-efficient distributed statistical inference
- Scalable linear solvers based on enlarged Krylov subspaces with dynamic reduction of search directions
- Robust and accurate stopping criteria for adaptive randomized sampling in matrix-free hierarchically semiseparable construction
- Block Modified Gram--Schmidt Algorithms and Their Analysis
- Communication-avoiding symmetric-indefinite factorization
- Communication Avoiding ILU0 Preconditioner
- Mixed-Precision Cholesky QR Factorization and Its Case Studies on Multicore CPU with Multiple GPUs
- Implementing Multifrontal Sparse Solvers for Multicore Architectures with Sequential Task Flow Runtime Systems
- Randomized QR with column pivoting
- Linear algebra software for large-scale accelerated multicore computing
- Randomized numerical linear algebra: Foundations and algorithms
- Accelerating the reduction to upper Hessenberg, tridiagonal, and bidiagonal forms through hybrid GPU-based computing
- TTDFT: a GPU accelerated Tucker tensor DFT code for large-scale Kohn-Sham DFT calculations
- Mixed Precision Iterative Refinement with Sparse Approximate Inverse Preconditioning
- Householder Orthogonalization with a Nonstandard Inner Product
- A distributed block Chebyshev-Davidson algorithm for parallel spectral clustering
- A block Cholesky‐LU‐based QR factorization for rectangular matrices
- On sampling determinantal and Pfaffian point processes on a quantum computer
- Adaptively restarted block Krylov subspace methods with low-synchronization skeletons
- A fast randomized algorithm for computing an approximate null space
- A novel parallel algorithm based on the Gram-Schmidt method for tridiagonal linear systems of equations
- Performance Analysis of the Householder-Type Parallel Tall-Skinny QR Factorizations Toward Automatic Algorithm Selection
- Probabilistic rounding error analysis of modified Gram-Schmidt
- 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
- A LAPACK implementation of the dynamic mode decomposition
- Active control of the flow past a circular cylinder using online dynamic mode decomposition
- A numerically stable communication-avoiding s-step GMRES algorithm
- Incremental model order reduction of smoothed-particle hydrodynamic simulations
- A new modified variable s-step BiCGSTAB method with regularization for solving shifted linear systems
- On the loss of orthogonality in low-synchronization variants of reorthogonalized block classical Gram-Schmidt
- Randomised subspace system identification: complexities and error bounds
- Distributed generalized linear models: a privacy-preserving approach
- Analysis of randomized Householder-Cholesky QR factorization with multisketching
- A novel adaptive low-rank matrix approximation method for image compression and reconstruction
- Backward error analysis of the AllReduce algorithm for Householder QR decomposition
- Variable s-step technique for planar algorithms in solving indefinite linear systems
- An improved shifted CholeskyQR based on columns
- Analyzing the dissemination of news by model averaging and subsampling
- CholeskyQR with randomization and pivoting for tall matrices (CQRRPT)
- Distributed-parallel proper orthogonal/dynamic mode decompositions of large flow data
- Sparse linear least-squares problems
- Efficient image reconstruction via regularized variable s-step conjugate gradient method for Sylvester matrix equations
- Augmented flexible Krylov subspace methods with applications to Bayesian inverse problems
- Detecting interactions in high-dimensional data using cross leverage scores
- Randomized block Gram-Schmidt process for the solution of linear systems and eigenvalue problems
- Hermitian dynamic mode decomposition -- numerical analysis and software solution
- Randomized Householder QR
- Towards dense linear algebra for hybrid GPU accelerated manycore systems
This page was built for publication: Communication-optimal parallel and sequential QR and LU factorizations
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2882786)
