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

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 $A^{T}A$, 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.