Communications in Mathematical Sciences

Volume 7 (2009)

Number 3

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

Pages: 755 – 777



Roberto Car

Weinan E

Lin Lin

Jianfeng Lu

Lexing Ying


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(N^3/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.


Diagonal extraction; hierarchical Schur complement; electronic structure calculation

2010 Mathematics Subject Classification

Primary 65F30. Secondary 65Z05.

Full Text (PDF format)