Sparsity of the density matrix in Kohn-Sham density functional theory and an assessment of linear system-size scaling methods

The range and sparsity of the one-electron density matrix (DM) in density functional theory is studied for large systems using the analytical properties of its Chebyshev expansion. General estimates of the range of the DM are derived, showing that the range is inversely proportional to the square root of an insulator band gap and inversely proportional to the square root of the temperature. These findings support ''principle of nearsightedness'' introduced recently by W. Kohn [Phys. Rev. Lett. 76, 3168 (1996)]. These estimates are used to study the complexity of several linear system-size scaling electronic structure algorithms which differ in their dependence on the geometric dimensionality of the system.