Localized and Randomized Algorithms for Electronic Structure

The computational cost of conventional electronic structure algorithms is cubic-scaling in system size. Quadratic scaling is possible with polynomial or rational approximation of the Fermi-Dirac function applied to the electronic Hamiltonian, but such algorithms are only beneficial for large system sizes. Further reduction to linear scaling is possible by using localization [Rev. Mod. Phys. 71, 1085 (1999)] or randomization [Phys. Rev. Lett. 111, 106402 (2013)], but localized algorithms perform poorly for low-temperature metals and randomized algorithms perform poorly for small error tolerances. We combine localized and randomized algorithms to offset their individual weaknesses – we reduce variance by randomly sampling from a residual error in a localized density matrix approximation rather than the full density matrix and reduce the cost per sample by using localized Green’s functions to precondition the evaluation of rational approximations. We compare this methods with quadratic-scaling PEXSI and cubic-scaling matrix diagonalization for tight-binding calculations of large copper clusters.