A parallel algorithm for the sparse $QR$ decomposition of a rectangular upper quasi-triangular matrix with ND-type sparsity
Keywords:sparse rectangular matrix, upper quasi-triangular matrix, volume partitioning, nested dissection, QR decomposition, Householder transformations, parallel algorithm
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.
- E. E. Tyrtyshnikov, Methods of Numerical Analysis (Akademiya, Moscow, 2007) [in Russian].
- A. George and J. W.-H. Liu, Computer Solution of Large Sparse Positive Definite Systems (Prentice-Hall, Englewood Cliffs, 1981; Mir, Moscow, 1984).
- 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).
- T. A. Davis, “Algorithm 915: SuiteSparseQR, a Multifrontal Multithreaded Sparse QR Factorization Package,” ACM Trans. Math. Softw. 38 (1), 8: 1-8: 22 (2011).
- S. N. Yeralan, T. A. Davis, and S. Ranka, “Algorithm 9xx: Sparse QR Factorization on the GPU,” ACM Trans. Math. Softw. 1 (1) (2015).
- 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).
- 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).
- F. Rotella and I. Zambettakis, “Block Householder Transformation for Parallel QR Factorization,” Appl. Math. Lett. 12 (4), 29-34 (1999).
- 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.
How to Cite
Харченко С. A Parallel Algorithm for the Sparse $QR$ Decomposition of a Rectangular Upper Quasi-Triangular Matrix With ND-Type Sparsity // Numerical Methods and Programming (Vychislitel’nye Metody i Programmirovanie). 2015. 16. 566-577. doi 10.26089/NumMet.v16r453
Section 1. Numerical methods and applications