Householder QR Factorization With Randomization for Column Pivoting (HQRRP)

DOI10.1137/16M1081270zbMath1365.65070arXiv1512.02671MaRDI QIDQ5738147

Nathan Heavner, Gregorio Quintana-Ortí, Robert A. van de Geijn, Per-Gunnar Martinsson

Publication date: 31 May 2017

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

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

zbMATH Keywords

numerical examplerandomized algorithmpivoting strategyblocked algorithmmatrix-matrix multiplicationsHouseholder QR factorization

Mathematics Subject Classification ID

Direct numerical methods for linear systems and matrix inversion (65F05)

Related Items

Randomized numerical linear algebra: Foundations and algorithms, Randomized Complete Pivoting for Solving Symmetric Indefinite Linear Systems, Randomized QLP decomposition, Efficient Randomized Algorithms for the Fixed-Precision Low-Rank Matrix Approximation, Computing Localized Representations of the Kohn--Sham Subspace Via Randomization and Refinement, Randomized Projection for Rank-Revealing Matrix Factorizations and Low-Rank Approximations, A stable parareal-like method for the second order wave equation, Analytical Low-Rank Compression via Proxy Point Selection, ALORA: affine low-rank approximations, Single-pass randomized QLP decomposition for low-rank approximation

Uses Software

• FLAME
• LAPACK
• BLAS
• RRQR
• toms/782
• libflame
• Elemental
• BLIS

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions
• A randomized algorithm for the decomposition of matrices
• A Note On Parallel Matrix Inversion
• BLIS: A Framework for Rapidly Instantiating BLAS Functionality
• A Randomized Blocked Algorithm for Efficiently Computing Rank-revealing Factorizations of Matrices
• Computational Advertising: Techniques for Targeting Relevant Ads
• Programming matrix algorithms-by-blocks for thread-level parallelism
• Randomized algorithms for the low-rank approximation of matrices
• Randomized Algorithms for Matrices and Data
• Elemental
• Accumulating Householder transformations, revisited
• Anatomy of high-performance matrix multiplication
• The WY Representation for Products of Householder Matrices
• A Storage-Efficient $WY$ Representation for Products of Householder Transformations
• LAPACK Users' Guide
• Hybrid Gauss-Trapezoidal Quadrature Rules
• Computing rank-revealing QR factorizations of dense matrices
• Algorithm 782
• A set of level 3 basic linear algebra subprograms
• A BLAS-3 Version of the QR Factorization with Column Pivoting
• Efficient Algorithms for Computing a Strong Rank-Revealing QR Factorization
• Fast monte-carlo algorithms for finding low-rank approximations
• FLAME
• Fast Monte Carlo Algorithms for Matrices II: Computing a Low-Rank Approximation to a Matrix
• Numerical Linear Algebra