Skip to Main content Skip to Navigation
Journal articles

Parallel QR factorization of block-tridiagonal matrices

Abstract : 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.
Complete list of metadata

Cited literature [36 references]  Display  Hide  Download

https://hal.archives-ouvertes.fr/hal-02370953
Contributor : Alfredo Buttari <>
Submitted on : Thursday, November 5, 2020 - 5:28:51 PM
Last modification on : Thursday, March 18, 2021 - 2:29:27 PM

File

block_tridiag_qr.pdf
Files produced by the author(s)

Identifiers

Citation

Alfredo Buttari, Søren Hauberg, Costy Kodsi. Parallel QR factorization of block-tridiagonal matrices. SIAM Journal on Scientific Computing, Society for Industrial and Applied Mathematics, 2020, 42 (6), pp.C313-C334. ⟨10.1137/19M1306166⟩. ⟨hal-02370953v2⟩

Share

Metrics

Record views

96

Files downloads

206