تقرير
QR factorization of ill-conditioned tall-and-skinny matrices on distributed-memory systems
العنوان: | QR factorization of ill-conditioned tall-and-skinny matrices on distributed-memory systems |
---|---|
المؤلفون: | Mijić, Nenad, Kaushik, Abhiram, Davidović, Davor |
سنة النشر: | 2024 |
المجموعة: | Computer Science |
مصطلحات موضوعية: | Computer Science - Distributed, Parallel, and Cluster Computing, Computer Science - Data Structures and Algorithms, Computer Science - Performance |
الوصف: | 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. Comment: 12 pages, 10 figures, 2 tables |
نوع الوثيقة: | Working Paper |
URL الوصول: | http://arxiv.org/abs/2405.04237 |
رقم الأكسشن: | edsarx.2405.04237 |
قاعدة البيانات: | arXiv |
الوصف غير متاح. |