Communications in Mathematical Sciences
Volume 7 (2009)
Fast algorithm for extracting the diagonal of the inverse matrix with application to the electronic structure analysis of metallic systems
Pages: 755 – 777
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.