Randomized QR with column pivoting
From MaRDI portal
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
(32)- Adaptive, Matrix-Free Low-Rank Approximation
- librla: Randomized Linear Algebra Library
- Householder QR factorization with randomization for column pivoting (HQRRP)
- CholeskyQR with randomization and pivoting for tall matrices (CQRRPT)
- Randomized algorithm for constrained quaternion singular value decomposition and its applications
- Randomized low-rank approximation methods for projection-based model order reduction of large nonlinear dynamical problems
- Single-pass randomized QLP decomposition for low-rank approximation
- Randomized QLP decomposition
- Structure-aware analyses and algorithms for interpolative decompositions
- Randomized numerical linear algebra: Foundations and algorithms
- Low-rank approximation algorithm using sparse projection and its applications
- ALORA: affine low-rank approximations
- Randomized complete pivoting for solving symmetric indefinite linear systems
- Truncated QR factorization with pivoting in mixed precision
- Communication avoiding rank revealing QR factorization with column pivoting
- Bayesian D-optimal experimental designs via column subset selection
- A randomized blocked algorithm for efficiently computing rank-revealing factorizations of matrices
- Efficient randomized algorithms for the fixed-precision low-rank matrix approximation
- Subspaces analysis for random projection UTV framework
- A stochastic perturbation analysis of the QR decomposition and its applications
- Randomized quaternion QLP decomposition for low-rank approximation
- A training set subsampling strategy for the reduced basis method
- Randomized Householder QR
- Randomized Projection for Rank-Revealing Matrix Factorizations and Low-Rank Approximations
- Computing localized representations of the Kohn-Sham subspace via randomization and refinement
- Low-rank approximation: randomized QR with column pivoting and related methods using sparse projection and pass-efficient techniques
- Randomized local model order reduction
- Deviation maximization for rank-revealing QR factorizations
- Accelerating the Canonical Polyadic Alternating Least Squares Optimization via a Randomized Interpolative Decomposition
- Flip-flop spectrum-revealing QR factorization and its applications to singular value decomposition
- Robust blockwise random pivoting: fast and accurate adaptive interpolative decomposition
- 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)
