A fast parallel algorithm for selected inversion of structured sparse matrices with application to 2D electronic structure calculations

An efficient parallel algorithm is presented for computing selected components of A^-1 where A is a structured symmetric sparse matrix. Calculations of this type are useful for several applications, including electronic structure analysis of materials in which the diagonal elements of the Green's functions are needed. The algorithm proposed here is a direct method based on a block LDL^T factorization. The selected elements of A ^-1 we compute lie in the nonzero positions of L+L^T . We use the elimination tree associated with the block LDL^T factorization to organize the parallel algorithm, and reduce the synchronization overhead by passing the data level by level along this tree using the technique of local buffers and relative indices. We demonstrate the efficiency of our parallel implementation by applying it to a discretized two dimensional Hamiltonian matrix. We analyze the performance of the parallel algorithm by examining its load balance and communication overhead, and show that our parallel implementation exhibits an excellent weak scaling on a large-scale high performance distributed-memory parallel machine.