Title: Randomized Householder-Cholesky QR Factorization with Multisketching

Affiliation: Temple University

Abstract: 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 practice.

Joint work with Andrew J. Higgins, Erik G. Boman, and Ichitaro Yamazaki.