Fast algorithm for extracting the diagonal of the inverse matrix with application to the electronic structure analysis of metallic systems. (English) Zbl 1182.65072

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

Commun. Math. Sci. 7, No. 3, 755-777 (2009).

Summary: 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.

MSC:

65F30	Other matrix algorithms (MSC2010)
65Z05	Applications to the sciences
81V45	Atomic physics

Keywords:

diagonal extraction; hierarchical Schur complement; electronic structure calculation; algorithm; extracting the diagonal of the inverse matrices; numerical results