CholeskyQR with Randomization and Pivoting for Tall Matrices (CQRRPT)

This paper develops and analyzes an algorithm for QR decomposition with column pivoting (QRCP) of tall matrices. The algorithm uses methods from randomized numerical linear algebra in a particularly careful way, to accelerate both pivot decisions for the input matrix and the process of decomposing the pivoted matrix via QR. The source of the latter acceleration is the use of randomized preconditioning and CholeskyQR. Comprehensive analysis is provided in both exact and finite-precision arithmetic to characterize the algorithm's rank-revealing properties and its numerical stability. An implementation of the described algorithm is made available under the open-source RandLAPACK library, which itself relies on RandBLAS. Experiments with this implementation on an Intel Xeon Gold 6248R CPU demonstrate order-of-magnitude speedups relative to LAPACK's standard function for QRCP, and comparable performance to a specialized algorithm for unpivoted QR of tall matrices.