Geodesic
Parallel implementation of the sparse QR decomposition for rectangular upper quasi triangular matrix with ND-type sparsity
Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ Vyčislitelʹnaâ matematika i informatika, Tome 5 (2016) no. 2, pp. 30-42 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

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.
Mots-clés : sparse rectangular matrix, QR decomposition
Keywords: upper quasi triangular matrix, nested dissection, Householder transformations, MPI, multithreading, SIMD. 
@article{VYURV_2016_5_2_a2,
     author = {S. A. Kharchenko and A. A. Yushchenko},
     title = {Parallel implementation of the sparse {QR} decomposition for rectangular upper quasi triangular matrix with {ND-type} sparsity},
     journal = {Vestnik \^U\v{z}no-Uralʹskogo gosudarstvennogo universiteta. Seri\^a Vy\v{c}islitelʹna\^a matematika i informatika},
     pages = {30--42},
     year = {2016},
     volume = {5},
     number = {2},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/VYURV_2016_5_2_a2/}
}
TY  - JOUR
AU  - S. A. Kharchenko
AU  - A. A. Yushchenko
TI  - Parallel implementation of the sparse QR decomposition for rectangular upper quasi triangular matrix with ND-type sparsity
JO  - Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ Vyčislitelʹnaâ matematika i informatika
PY  - 2016
SP  - 30
EP  - 42
VL  - 5
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/VYURV_2016_5_2_a2/
LA  - ru
ID  - VYURV_2016_5_2_a2
ER  - 
%0 Journal Article
%A S. A. Kharchenko
%A A. A. Yushchenko
%T Parallel implementation of the sparse QR decomposition for rectangular upper quasi triangular matrix with ND-type sparsity
%J Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ Vyčislitelʹnaâ matematika i informatika
%D 2016
%P 30-42
%V 5
%N 2
%U http://geodesic.mathdoc.fr/item/VYURV_2016_5_2_a2/
%G ru
%F VYURV_2016_5_2_a2
S. A. Kharchenko; A. A. Yushchenko. Parallel implementation of the sparse QR decomposition for rectangular upper quasi triangular matrix with ND-type sparsity. Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ Vyčislitelʹnaâ matematika i informatika, Tome 5 (2016) no. 2, pp. 30-42. http://geodesic.mathdoc.fr/item/VYURV_2016_5_2_a2/

[1] E.E. Tyrtyshnikov, Methods of Numerical Analysis, Akademiya, Moscow, 2007, 320 pp.

[2] S.A. Kharchenko, “A Parallel Algorithm for the Sparse QR Decomposition of a Rectangular Upper QuasiTriangular Matrix with ND-Type Sparsity”, Numerical Methods and Programming, 16 (2015), 566–577

[3] T.A. Davis, “Algorithm 915: SuitesparseQR, a Multifrontal Multithreaded Sparse QR Factorization Package”, ACM Trans. Math. Softw. Dec., 38:1 (2011), 8:1–8:22

[4] S.N. Yeralan, T.A. Davis, S. Ranka, “Algorithm 9xx: Sparse QR Factorization on the GPU”, ACM Transactions on Mathematical Software. Jan., 1:1 (2015), 1–28

[5] F. Rotella, I. Zambettakis, “Block Householder Transformation for Parallel QR Factorization”, Appl. Math. Letters, 12:4 (1999), 29–34

[6] N. Li, Y. Saad, “MIQR: A Multilevel Incomplete Qr Preconditioner for Large Sparse Leastsquares Problems”, SIAM. J. Matrix Anal. Appl., 12:28(2) (2006), 524–550

[7] A. George, J.W. Liu, Computer Solution of Large Sparse Positive Definite Systems, Prentice Hall, 1981, 324 pp.

[8] A.E. Andreev, V.A. Egunov, A.A. Nasonov, A.A. Novokshenov, “Application of Vector Instructions in Algorithms of Block Operations of Linear Algebra”, VSTU News: “Actual Problems of Control, Computers and Informatics in Technical Systems”, 2014, no. 39(12), 5–11