Randomized QR with column pivoting
From MaRDI portal
Publication:5348261
Abstract: The dominant contribution to communication complexity in factorizing a matrix using QR with column pivoting is due to column-norm updates that are required to process pivot decisions. We use randomized sampling to approximate this process which dramatically reduces communication in column selection. We also introduce a sample update formula to reduce the cost of sampling trailing matrices. Using our column selection mechanism we observe results that are comparable in quality to those obtained from the QRCP algorithm, but with performance near unpivoted QR. We also demonstrate strong parallel scalability on shared memory multiple core systems using an implementation in Fortran with OpenMP. This work immediately extends to produce low-rank truncated approximations of large matrices. We propose a truncated QR factorization with column pivoting that avoids trailing matrix updates which are used in current implementations of level-3 BLAS QR and QRCP. Provided the truncation rank is small, avoiding trailing matrix updates reduces approximation time by nearly half. By using these techniques and employing a variation on Stewart's QLP algorithm, we develop an approximate truncated SVD that runs nearly as fast as truncated QR.
Recommendations
- Householder QR factorization with randomization for column pivoting (HQRRP)
- A randomized blocked algorithm for efficiently computing rank-revealing factorizations of matrices
- Communication avoiding rank revealing QR factorization with column pivoting
- Four algorithms for the the efficient computation of truncated pivoted QR approximations to a sparse matrix
- A fast randomized algorithm for the approximation of matrices
Cites work
- scientific article; zbMATH DE number 6159604 (Why is no real title available?)
- A BLAS-3 Version of the QR Factorization with Column Pivoting
- A Parallel QR Factorization Algorithm with Controlled Local Pivoting
- A Storage-Efficient $WY$ Representation for Products of Householder Transformations
- A randomized algorithm for the decomposition of matrices
- Communication avoiding rank revealing QR factorization with column pivoting
- Communication-optimal parallel and sequential QR and LU factorizations
- Efficient Algorithms for Computing a Strong Rank-Revealing QR Factorization
- Extensions of Lipschitz mappings into a Hilbert space
- Finding structure with randomness: probabilistic algorithms for constructing approximate matrix decompositions
- Minimizing communication in numerical linear algebra
- On the convergence of Stewart's QLP algorithm for approximating the SVD
- Randomized algorithms for the low-rank approximation of matrices
- Rang revealing QR factorizations
- Some Applications of the Rank Revealing QR Factorization
- The QLP Approximation to the Singular Value Decomposition
- The WY Representation for Products of Householder Matrices
Cited in
(20)- A training set subsampling strategy for the reduced basis method
- A stochastic perturbation analysis of the QR decomposition and its applications
- Randomized Projection for Rank-Revealing Matrix Factorizations and Low-Rank Approximations
- Randomized quaternion QLP decomposition for low-rank approximation
- Randomized low-rank approximation methods for projection-based model order reduction of large nonlinear dynamical problems
- Efficient randomized algorithms for the fixed-precision low-rank matrix approximation
- Deviation maximization for rank-revealing QR factorizations
- Randomized QLP decomposition
- Communication avoiding rank revealing QR factorization with column pivoting
- Randomized complete pivoting for solving symmetric indefinite linear systems
- Randomized numerical linear algebra: Foundations and algorithms
- Computing localized representations of the Kohn-Sham subspace via randomization and refinement
- Single-pass randomized QLP decomposition for low-rank approximation
- Randomized local model order reduction
- ALORA: affine low-rank approximations
- Subspaces analysis for random projection UTV framework
- A randomized blocked algorithm for efficiently computing rank-revealing factorizations of matrices
- Flip-flop spectrum-revealing QR factorization and its applications to singular value decomposition
- Householder QR factorization with randomization for column pivoting (HQRRP)
- Pass-efficient truncated UTV for low-rank approximations
This page was built for publication: Randomized QR with column pivoting
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5348261)
