Parallel QR factorization of block-tridiagonal matrices - Algorithmes Parallèles et Optimisation Accéder directement au contenu
Article Dans Une Revue SIAM Journal on Scientific Computing Année : 2020

Parallel QR factorization of block-tridiagonal matrices

Résumé

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.
Fichier principal
Vignette du fichier
block_tridiag_qr.pdf (394.62 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-02370953 , version 1 (19-11-2019)
hal-02370953 , version 2 (05-11-2020)

Identifiants

Citer

Alfredo Buttari, Søren Hauberg, Costy Kodsi. Parallel QR factorization of block-tridiagonal matrices. SIAM Journal on Scientific Computing, 2020, 42 (6), pp.C313-C334. ⟨10.1137/19M1306166⟩. ⟨hal-02370953v2⟩
332 Consultations
463 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More