Fast algorithm for extracting the diagonal of the inverse matrix with application to the electronic structure analysis of metallic systems

Lin Lin, Jianfeng Lu, Lexing Ying, Roberto Car, Weinan E

Research output: Contribution to journalArticle

70 Scopus citations

Abstract

We propose an algorithm for extracting the diagonal of the inverse matrices arising from electronic structure calculation. The proposed algorithm uses a hierarchical decomposition of the computational domain. It first constructs hierarchical Schur complements of the interior points for the blocks of the domain in a bottom-up pass and then extracts the diagonal entries efficiently in a top-down pass by exploiting the hierarchical local dependence of the inverse matrices. The overall cost of our algorithm is O(N3/2) for a two dimensional problem with N degrees of freedom. Numerical results in electronic structure calculation illustrate the efficiency and accuracy of the proposed algorithm.

Original languageEnglish (US)
Pages (from-to)755-777
Number of pages23
JournalCommunications in Mathematical Sciences
Volume7
Issue number3
DOIs
StatePublished - Jan 1 2009

All Science Journal Classification (ASJC) codes

  • Mathematics(all)
  • Applied Mathematics

Keywords

  • Diagonal extraction
  • Electronic structure calculation
  • Hierarchical Schur complement

Fingerprint Dive into the research topics of 'Fast algorithm for extracting the diagonal of the inverse matrix with application to the electronic structure analysis of metallic systems'. Together they form a unique fingerprint.

  • Cite this