Computational Mathematics

Parallel implementation of the sparse QR decomposition for rectangular upper quasi triangular matrix with ND-type sparsity

S. A. Kharchenko, A. A. Yushchenko

LLC «TESIS», Moscow, Russian Federation

Abstract: The paper considers parallel MPI+threads+SIMD implementation of the algorithm for computing sparse QR decomposition of a specially ordered rectangular matrix. Decomposition is based on block sparse Householder transformations. The algorithm starts with independent parallel QR decompositions for sets of matrix rows; and then, according to the computations tree, the QR decomposition is performed for matrices, combined with elements of R factors of rows decompositions. The results of numerical experiments for test problems show efficiency of the parallel implementation. The algorithm can also be efficiently implemented on heterogeneous cluster architectures with GPGPU accelerators.

Keywords: sparse rectangular matrix, upper quasi triangular matrix, nested dissection, QR decomposition, Householder transformations, MPI, multithreading, SIMD.

UDC: 519.61

Received: 16.12.2015

DOI: 10.14529/cmse160203

Bibliographic databases:

•