Randomized Householder QR

Laura Grigori (1, 2) , Edouard Timsit (3, 4, 5)

1 EPFL - Ecole Polytechnique Fédérale de Lausanne
2 PSI - Paul Scherrer Institute
3 SU - Sorbonne Université
4 LJLL (UMR_7598) - Laboratoire Jacques-Louis Lions
5 ALPINES - Algorithms and parallel tools for integrated numerical simulations

This paper introduces a randomized Householder QR factorization (RHQR). This factorization can be used to obtain a well conditioned basis of a set of vectors and thus can be employed in a variety of applications. We discuss in particular the usage of this randomized Householder factorization in the Arnoldi process. Numerical experiments show that RHQR produces a well conditioned basis and an accurate factorization. We observe that for some cases, it can be more stable than Randomized Gram-Schmidt (RGS) in single precision.

Keywords: Householder; Randomizaton; Sketching; Arnoldi; Numerical stability; QR factorization; Simple precision; Block QR factorization

Domains: Numerical Analysis [math.NA]; Modeling and Simulation; Numerical Analysis [cs.NA]

Laura Grigori, Edouard Timsit. Randomized Householder QR. 2023. ⟨hal-04156310v2⟩