Fast algorithm for extracting the diagonal of the inverse matrix with application to the electronic structure analysis of metallic systems
Roberto Car, E Weinan, Lin Lin, Jianfeng Lu, Lexing Ying · Communications in Mathematical Sciences · 2009
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.