DOI: https://doi.org/10.26089/NumMet.v16r453

A parallel algorithm for the sparse $QR$ decomposition of a rectangular upper quasi-triangular matrix with ND-type sparsity

Authors

  • S.A. Kharchenko

Keywords:

sparse rectangular matrix
upper quasi-triangular matrix
volume partitioning
nested dissection
QR decomposition
Householder transformations
parallel algorithm

Abstract

An algorithm for computing the sparse QR decomposition of a specially ordered rectangular matrix is proposed. This decomposition is based on the block sparse Householder transformations. For ordering computations, the nested dissection ordering is used for the matrix ATA, where A is the original rectangular matrix. For mesh based problems, the ordering can be constructed starting from an appropriate volume partitioning of the computational mesh. Parallel computations are based on sparse QR decomposition for sets of rows with an additional initial zero block.

New computational technologies

Downloads

Published

2015-10-02

Issue

Vol. 16 (2015): Issue 4.

Section

Section 1. Numerical methods and applications

Author Biography

S.A. Kharchenko

TESIS, LLC
• Leading Programmer

References

  1. E. E. Tyrtyshnikov, Methods of Numerical Analysis (Akademiya, Moscow, 2007) [in Russian].
  2. A. George and J. W.-H. Liu, Computer Solution of Large Sparse Positive Definite Systems (Prentice-Hall, Englewood Cliffs, 1981; Mir, Moscow, 1984).
  3. I. E. Kaporin, “High Quality Preconditioning of a General Symmetric Positive Definite Matrix Based on its U^T U+U^T R+R^T U-Decomposition,” Numer. Linear Algebra Appl. 5 (6), 483-509 (1998).
  4. T. A. Davis, “Algorithm 915: SuiteSparseQR, a Multifrontal Multithreaded Sparse QR Factorization Package,” ACM Trans. Math. Softw. 38 (1), 8: 1-8: 22 (2011).
  5. S. N. Yeralan, T. A. Davis, and S. Ranka, “Algorithm 9xx: Sparse QR Factorization on the GPU,” ACM Trans. Math. Softw. 1 (1) (2015).
    doi 10.1145/0000000.0000000
  6. N. Li and Y. Saad, “MIQR: A Multilevel Incomplete QR Preconditioner for Large Sparse Least-Squares Problems,” SIAM J. Matrix Anal. Appl. 28 (2), 524-550 (2006).
  7. S. A. Kharchenko and A. A. Yushchenko, “Parallel Implementation of Sparse QR Decomposition of a Rectangular Upper Quasitriangular Matrix with ND-Type Sparsity,” Vestn. South Ural State Univ. Ser. Vychisl. Mat. Inf., 2015 (in press).
  8. F. Rotella and I. Zambettakis, “Block Householder Transformation for Parallel QR Factorization,” Appl. Math. Lett. 12 (4), 29-34 (1999).
  9. A. Haidar, T. T. Dong, S. Tomov, et al., “A Framework for Batched and GPU-Resident Factorization Algorithms Applied to Block Householder Transformations,” in Lecture Notes in Computer Science (Springer, Heidelberg, 2015), Vol. 9137, pp. 31-47.