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

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.

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

  • Kharchenko S.A. – Limited Liability Company "TESIS"; ulitsa Yunnatov 18, Moscow, 127083, Russia; Leading Programmer, e-mail: skh@tesis.com.ru