Fast multipole expansion

Schulten238 outlined the development of a multiple-time-scale approximation (distance class algorithm) for the evaluation of nonbonded interactions, as well as the fast multipole expansion (FME). efficiency of the FME was demonstrated when the method outperformed the direct evaluation of Coulomb forces for 5000 atoms by a large margin and showed, for systems of up to 24,000 atoms, a linear dependence on atom number. 

If one succeeds in transforming not only the occupied but also the virtual MOs to a set of well-localized MOs, such that one can associate q (occupied and virtual) MOs with each atom, then one can argue that for the description of intraatomic correlation only excitations in this g-dimensional (and hence n-independent) subspace need to be considered. For interatomic correlations between a pair of neighboring atoms excitations with the 2q dimensional space of the MOs of the two atoms are necessary, and so forth. Correlations beyond next-nearest neighbors may be regarded as unimportant. The number of pairs of atoms to be considered scales with n, so the overall computational demands should scale with n as well, provided that also takes advantage of fast multipole expansion [190, 191] for the Coulomb interaction. 

For the non-periodic systems it is more common to use a list of non-bonded neighbors and spherical truncation of the non-bonded interactions at some cut off distance in the range 10-15 A, often together with a smoothing of the interaction to zero at the cut off. In one case a fast multipole expansion of the long-range Coulomb interactions was used. For periodic systems there is also the possibility to use Ewald summation, and the simulations of the restriction endonucleases were made with the fast particle mesh Ewald (PME) summation algorithm. 

One recent development in DFT is the advent of linear scaling algorithms. These algorithms replace the Coulomb terms for distant regions of the molecule with multipole expansions. This results in a method with a time complexity of N for sufficiently large molecules. The most common linear scaling techniques are the fast multipole method (FMM) and the continuous fast multipole method (CFMM). 

The original FMM has been refined by adjusting the accuracy of the multipole expansion as a function of the distance between boxes, producing the very Fast Multipole Moment (vFMM) method. Both of these have been generalized tc continuous charge distributions, as is required for calculating the Coulomb interactioi between electrons in a quantum description. The use of FMM methods in electronic structure calculations enables the Coulomb part of the electron-electron interaction h be calculated with a computational effort which depends linearly on the number of basi functions, once the system becomes sufficiently large. 

The description of the mDC method in the present work is supplemented with mathematical details that we Have used to introduce multipolar densities efficiently into the model. In particular, we describe the mathematics needed to construct atomic multipole expansions from atomic orbitals (AOs) and interact the expansions with point-multipole and Gaussian-multipole functions. With that goal, we present the key elements required to use the spherical tensor gradient operator (STGO) and the real-valued solid harmonics perform multipole translations for use in the Fast Multipole Method (FMM) electrostatically interact point-multipole expansions interact Gaussian-multipoles in a manner suitable for real-space Particle Mesh Ewald (PME) corrections and we list the relevant real-valued spherical harmonic Gaunt coefficients for the expansion of AO product densities into atom-centered multipoles. 

The multipole expansion of Coulomb s law up to the octupole, which can be found in [48], is more complicated than Eq. 9.3. The advantage is that the complexity in the expression leads to computational efficiency in computer simulations once it is programmed, since only one distance between two interacting water molecules is needed. The downside is that while it becomes more accurate as higher order multipoles are added, it also becomes computationally slower as higher-order multipoles are included since each n-pole involves a (n - 1) rank tensor. A soft-sphere model with a dipole, quadrupole, and octupole (SSDQO], which is exact up to the 1/r term and in addition approximates the 1/r term, has been developed for computational efficiency [48]. However, the recent implementation of a fast multipole method in the molecular dynamics program CHARMM [80] should make this approximation unnecessary specifically, the full multipole expansion up to the... 

The original FMM has been refined by also adjusting the accuracy of the multipole expansion as a function of the distance between boxes, producing the very Fast Multipole Moment (vFMM) method. ... 

Experimental chemistry is focused, in most cases, on molecules of a larger size than those for which fair calculations with correlation are possible. However, after thorough analysis of the situation, it turns out that the cost of the calculations does not necessarily increase very fast with the size of a molecule. Employing localized molecular orbitals and using the multipole expansion (see Appendix X available at booksite.elsevier.com/978-0-444-59436-5) of the integrals involving the orbitals separated in space causes, fa- elongated molecules, the cost of the post-Hartree-Fock calculations to scale linearly with the size of a molecule. It can he expected that if the methods described in... 

However, the operator V from Eq. (13.14) and the operator in the multipole form [Eq. (13.17)] are equivalent only when the mnltipole form converges. It does when the interacting objects are non-overlapping, which is not the case. The electronic charge distributions penetrate and this causes a small difference (penetration energy Epenetr) between the eist values calculated with and without the multipole expansion. The penetration energy vanishes very fast with... 

Our goal is application of the multipole expansion in the case of the intermolecular interactions. Are we able to enclose both molecules in two non-overlapping spheres Sometimes we certainly are not e.g., if a small molecule A is to be docked in a cavity of a large molecule B. This is a very interesting case (Fig. X.4d), but what we have most often in quantum chemistry are two distant molecules. So, is everything all right Apparently the molecules can be enclosed in the spheres, but if we recall that the electronic density extends to infinity (although it decays very fast), then we feel a little scared. Almost the whole density distribution could be enclosed inside such spheres, but some of it also exists outside the spheres. It turns out that this very fact causes... 

Very fast multipole methods have been developed in order to calculate these electron repulsion integralsl . The near field is determined by analytical Gaussian calculations. The far field is calculated usiug multipole expansions to treat the distant charges and their interactions. The scahng for this approach has been reduced to Fast quadrature... 

---