Efficient algorithms for computing rank‐revealing factorizations on a GPU

DOI10.1002/NLA.2515MaRDI QIDQ6137131zbMATH OpenOpenAlexFDO

Authors Nathan Heavner, Chao Chen, Abinand Gopal, P. G. Martinsson

Publication date 18 January 2024

Published in Numerical Linear Algebra with Applications (Search for Journal in Brave)

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

zbMATH Keywords

randomized numerical linear algebrarank-revealing matrix factorizationparallel algorithm for GPU

Mathematics Subject Classification ID

Parallel numerical computation (65Y05) Numerical methods for low-rank matrix approximation; matrix compression (65F55)

Abstract: Standard rank-revealing factorizations such as the singular value decomposition and column pivoted QR factorization are challenging to implement efficiently on a GPU. A major difficulty in this regard is the inability of standard algorithms to cast most operations in terms of the Level-3 BLAS. This paper presents two alternative algorithms for computing a rank-revealing factorization of the form $A=UT{V}^{\ast }$, where $U$ and $V$ are orthogonal and $T$ is triangular. Both algorithms use randomized projection techniques to cast most of the flops in terms of matrix-matrix multiplication, which is exceptionally efficient on the GPU. Numerical experiments illustrate that these algorithms achieve an order of magnitude acceleration over finely tuned GPU implementations of the SVD while providing low-rank approximation errors close to that of the SVD.

Recommendations

• A randomized blocked algorithm for efficiently computing rank-revealing factorizations of matrices
• Efficient Algorithms for Computing a Strong Rank-Revealing QR Factorization
• A block algorithm for computing rank-revealing QR factorizations
• Computing rank-revealing QR factorizations of dense matrices
• On Rank-Revealing Factorisations

Cited in

(1)

• Adaptive, Matrix-Free Low-Rank Approximation

This page was built for publication: Efficient algorithms for computing rank‐revealing factorizations on a GPU

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6137131)