QR factorization of ill-conditioned tall-and-skinny matrices on distributed-memory systems
<|reference_start|>QR factorization of ill-conditioned tall-and-skinny matrices on distributed-memory systems: In this paper we present a novel algorithm developed for computing the QR factorisation of extremely ill-conditioned tall-and-skinny matrices on distributed memory systems. The algorithm is based on the communication-avoiding CholeskyQR2 algorithm and its block Gram-Schmidt variant. The latter improves the numerical stability of the CholeskyQR2 algorithm and significantly reduces the loss of orthogonality even for matrices with condition numbers up to $10^{15}$. Currently, there is no distributed GPU version of this algorithm available in the literature which prevents the application of this method to very large matrices. In our work we provide a distributed implementation of this algorithm and also introduce a modified version that improves the performance, especially in the case of extremely ill-conditioned matrices. The main innovation of our approach lies in the interleaving of the CholeskyQR steps with the Gram-Schmidt orthogonalisation, which ensures that update steps are performed with fully orthogonalised panels. The obtained orthogonality and numerical stability of our modified algorithm is equivalent to CholeskyQR2 with Gram-Schmidt and other state-of-the-art methods. Weak scaling tests performed with our test matrices show significant performance improvements. In particular, our algorithm outperforms state-of-the-art Householder-based QR factorisation algorithms available in ScaLAPACK by a factor of $6$ on CPU-only systems and up to $80\times$ on GPU-based systems with distributed memory.<|reference_end|>
@article{mijić2024qr,
    title={QR factorization of ill-conditioned tall-and-skinny matrices on
  distributed-memory systems},
    author={Nenad Miji'c, Abhiram Kaushik, Davor Davidovi'c},
    journal={arXiv preprint arXiv:2405.04237},
    year={2024},
    archivePrefix={arXiv},
    eprint={2405.04237},
    primaryClass={cs.DC cs.DS cs.PF}
}