Fast assembly of the Coulomb matrix: A quantum chemical tree code

Fast methods based on a representation of the electron charge density in a Hermite Gaussian basis are introduced for constructing the Coulomb matrix encountered in Hartree-Fock and density functional theories. Simplifications that arise from working in a Hermite Gaussian basis are discussed, translations of such functions are shown to yield rapidly convergent expansions valid in both the near- and far-field, and the corresponding truncation errors are derived in compact form. The relationship of such translations to hierarchical multipole methods is pointed out and a quantum chemical tree code related to the Barnes-Hut method is developed. Novel methods are introduced for the independent thresholding of ‘‘bra’’ and ‘‘ket’’ distributions as well as for screening out insignificant multipole interactions. Recurrence relations for computing the Cartesian multipole tensor are used to efficiently calculate far-field electrostatic interactions using high-order expansions. Application of the quantum chemical tree code to assembly of the Coulomb matrix for HF/3-21G calculations on sequences of polyglycine α-helices and water clusters demonstrate scalings as favorable as N1.6, where N is the number of basis functions. Comparisons with a commercial electronic structure program indicate that our method is highly competitive. Speed is obtained without sacrificing precision, truncation errors are controlled with a single parameter, and the method performs equally well with a contracted or uncontracted LCAO basis.