Randomized Householder QR
Abstract
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.
| Origin | Files produced by the author(s) |
|---|