2024/05/07 by Nenad Mijić, Mijić, Nenad, Abhiram Kaushik +3
Biochemistry, Genetics and Molecular Biology · Computer Science · #DNA and Biological Computing #Data Structures and Algorithms (cs.DS) #Distributed #FOS: Computer and information sciences #Neural Networks and Applications #Parallel #Performance (cs.PF) #Quantum Computing Algorithms and Architecture #and Cluster Computing (cs.DC)
paper · pdf · doi:10.48550/arxiv.2405.04237
openalex publication_date 2024/05/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 1015. 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× on GPU-based systems with distributed memory.