Parallel QR factorization of block-tridiagonal matrices

Alfredo Buttari (1) , Søren Hauberg (2) , Costy Kodsi (2)

1 IRIT-APO - Algorithmes Parallèles et Optimisation
2 DTU Compute - Department of Applied Mathematics and Computer Science [Lyngby]

In this work, we deal with the QR factorization of block-tridiagonal matrices, where the blocks are dense and rectangular. This work is motivated by a novel method for computing geodesics over Riemannian man-ifolds. If blocks are reduced sequentially along the diagonal, only limited parallelism is available. We propose a matrix permutation approach based on the Nested Dissection method which improves parallelism at the cost of additional computations and storage. We provide a detailed analysis of the approach showing that this extra cost is bounded. Finally, we present an implementation for shared memory systems relying on task parallelism and the use of a runtime system. Experimental results support the conclusions of our analysis and show that the proposed approach leads to good performance and scalability.

Domaines: Calcul parallèle, distribué et partagé [cs.DC]; Logiciel mathématique [cs.MS]

Alfredo Buttari, Søren Hauberg, Costy Kodsi. Parallel QR factorization of block-tridiagonal matrices. [Research Report] IRIT - Institut de recherche en informatique de Toulouse. 2019. ⟨hal-02370953v1⟩