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. The RHQR factorization of the input matrix $W$ is equivalent to the standard Householder QR factorization of matrix $\Psi W$, where $\Psi$ is a sketching matrix that can be obtained from any subspace embedding technique. For this reason, the RHQR algorithm can also be reconstructed from the Householder QR factorization of the sketched problem. In most contexts, left-looking RHQR requires a single synchronization per iteration, with half the computational cost of Householder QR, and a similar cost to Randomized Gram-Schmidt (RGS) overall. We discuss the usage of RHQR factorization in the Arnoldi process and then in GMRES, showing thus how it can be used in Krylov subspace methods to solve systems of linear equations. Based on Charles Sheffield's connection between Householder QR and Modified Gram-Schmidt (MGS), a randomized Modified Gram Schmidt (RMGS) process is also derived. Numerical experiments show that RHQR produces a well conditioned basis whose sketch is numerically orthogonal, and an accurate factorization. For some very difficult cases, it can be more stable than RGS in both unique precision (half, single, or double) and mixed 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. 2024. ⟨hal-04156310v4⟩