Deterministic and randomized LU-Householder CholeskyQR

In this work, we focus on improving LU-CholeskyQR2 \cite{LUChol}. Compared to other deterministic and randomized CholeskyQR-type algorithms, it does not require a sufficient condition on $\kappa_{2}(X)$ for the input tall-skinny matrix $X$, which ensures the algorithm's safety in most real-world applications. However, the Cholesky factorization step may break down when the $L$-factor after the LU factorization of $X$ is ill-conditioned. To address this, we construct a new algorithm, LU-Householder CholeskyQR2 (LHC2), which uses HouseholderQR to generate the upper-triangular factor, thereby avoiding numerical breakdown. Moreover, we utilize the latest sketching techniques to develop randomized versions of LHC: SLHC and SSLHC. We provide a rounding error analysis for these new algorithms. Numerical experiments demonstrate that our three new algorithms have better applicability and can handle a wider range of matrices compared to LU-CholeskyQR2. With the sketching technique, our randomized algorithms, SLHC2 and SSLHC3, show significant acceleration over LHC2. Additionally, SSLHC3, which employs multi-sketching, is more efficient than SLHC2 and exhibits better numerical stability. It is also robust as a randomized algorithm.