PSe1Inv - A distributed memory parallel algorithm for selected inversion: The non-symmetric case

摘要

This paper generalizes the parallel selected inversion algorithm called PSeIInv to sparse non-symmetric matrices. We assume a general sparse matrix A has been decomposed as PAQ = LU on a distributed memory parallel machine, where L, U are lower and upper triangular matrices, and P, Q are permutation matrices, respectively. The PSeIInv method computes selected elements of A(-1). The selection is confined by the sparsity pattern of the matrix AT. Our algorithm does not assume any symmetry properties of A, and our parallel implementation is memory efficient, in the sense that the computed elements of A-T over-writes the sparse matrix L U in situ. PSeIInv involves a large number of collective data communication activities within different processor groups of various sizes. In order to minimize idle time and improve load balancing, tree-based asynchronous communication is used to coordinate all such collective communication. Numerical results demonstrate that PSeIInv can scale efficiently to 6,400 cores for a variety of matrices. (C) 2017 Elsevier B.V. All rights reserved.