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

Lin Lin, Chao Yang, Jianfeng Lu, Lexing Ying, E. Weinan

Research output: Contribution to journalArticlepeer-review

31 Scopus citations

Abstract

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 LDLT factorization. The selected elements of A -1 we compute lie in the nonzero positions of L+LT . We use the elimination tree associated with the block LDLT 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.

Original languageEnglish (US)
Pages (from-to)1329-1351
Number of pages23
JournalSIAM Journal on Scientific Computing
Volume33
Issue number3
DOIs
StatePublished - 2011

All Science Journal Classification (ASJC) codes

  • Computational Mathematics
  • Applied Mathematics

Keywords

  • Electronic structure calculation
  • Parallel algorithm
  • Selected inversion

Fingerprint Dive into the research topics of 'A fast parallel algorithm for selected inversion of structured sparse matrices with application to 2D electronic structure calculations'. Together they form a unique fingerprint.

Cite this