We present and analyze a new randomized algorithm called rand_cholQR for computing tall-and-skinny QR factorizations. Using one or two random sketch matrices, it is  proved that with high probability, its orthogonality error is bounded by a constant of the order of unit roundoff for any numerically full-rank matrix. An evaluation of the performance of rand_cholQR on a NVIDIA A100 GPU demonstrates that for tall-and-skinny matrices, rand_cholQR with multiple sketch matrices is nearly as fast as, or in some cases faster than, the state-of-the-art CholeskyQR2. Hence, compared to CholeskyQR2, rand_cholQR is more stable with almost no extra computational or memory cost, and therefore a superior algorithm both in theory and in practice.

 

This is joint work with Andrew J. Higgins, Erik G. Boman, and Ichitaro Yamazaki.