Randomized QR with column pivoting

DOI10.1137/15M1044680zbMATH Open1371.65026arXiv1509.06820MaRDI QIDQ5348261FDOQ5348261

Authors:

Publication date: 15 August 2017

Published in: SIAM Journal on Scientific Computing (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1509.06820

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

zbMATH Keywords

singular value decompositionlow-rank approximationparallel computationrandom samplingQR factorizationtruncated SVDcolumn pivotingblocked algorithmsample update

Mathematics Subject Classification ID

Direct numerical methods for linear systems and matrix inversion (65F05) Parallel numerical computation (65Y05) Numerical solutions to overdetermined systems, pseudoinverses (65F20)

Cites Work

• Rang revealing QR factorizations
• Extensions of Lipschitz mappings into a Hilbert space
• Title not available (Why is that?)
• Finding structure with randomness: probabilistic algorithms for constructing approximate matrix decompositions
• Communication-optimal parallel and sequential QR and LU factorizations
• Minimizing communication in numerical linear algebra
• Randomized algorithms for the low-rank approximation of matrices
• Some Applications of the Rank Revealing QR Factorization
• Efficient Algorithms for Computing a Strong Rank-Revealing QR Factorization
• A randomized algorithm for the decomposition of matrices
• The WY Representation for Products of Householder Matrices
• A Storage-Efficient $WY$ Representation for Products of Householder Transformations
• A Parallel QR Factorization Algorithm with Controlled Local Pivoting
• The QLP Approximation to the Singular Value Decomposition
• A BLAS-3 Version of the QR Factorization with Column Pivoting
• On the convergence of Stewart's QLP algorithm for approximating the SVD
• Communication Avoiding Rank Revealing QR Factorization with Column Pivoting

Cited In (17)

• 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
• Single-pass randomized QLP decomposition for low-rank approximation
• Randomized QLP decomposition
• Randomized Local Model Order Reduction
• Subspaces Analysis for Random Projection UTV Framework
• Randomized numerical linear algebra: Foundations and algorithms
• Computing Localized Representations of the Kohn--Sham Subspace Via Randomization and Refinement
• ALORA: affine low-rank approximations
• 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 Projection for Rank-Revealing Matrix Factorizations and Low-Rank Approximations
• Randomized Complete Pivoting for Solving Symmetric Indefinite Linear Systems
• Deviation maximization for rank-revealing QR factorizations
• Flip-flop spectrum-revealing QR factorization and its applications to singular value 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)