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.
All Science Journal Classification (ASJC) codes
- Applied Mathematics
- Diagonal extraction
- Electronic structure calculation
- Hierarchical Schur complement