Cell multipole methods

Figure 6.25 reprinted from Chemical Physics Letters, 196, Ding H-Q, N Karasawa and W A Goddard III, T he Reduced Cell Multipole Method for Coulomb Interactions in Periodic Systems with Million-Atom Unit Cells, 6-10, 1992, with permission of Elsevier Science. 

Both the Coulomb cmd Lennard-Jones potentials can be considered examples of this type. In the cell multipole method the simulation space is divided into uniform cubic... 

A. M. Mathiowetz, A. Jain, N. Karasawa, W. A. Goddard III. Protein simulations using techniques suitable for very large systems the cell multipole method for nonbond interactions and the Newton-Euler inverse mass operator method for internal coordinate dynamics. CN 8921. Proteins 20 221, 1994. 

Kutteh R, Nicholas JB (1995) Efficient dipole iteration in polarizable charged systems using the cell multipole method and application to polarizable water. Comput Phys Commun 86(3) 227—235... 

Two temperatures were simulated 273 K at which PTFE is in Phase II and 298 K at which it is in Phase IV The canonical ensemble (constant temperature, constant volume) was used. Owing to the large number of atoms (-3500 including dummy atoms), the cell multipole method was chosen for the calculation of long-range van der Waals and electrostatic interactions. For the latter, a dielectric constant of 1.0 was used. 

Iteration in Polarizable Charged Systems Using the Cell Multipole Method and Application to Polarizable Water. 

Atom Level Simulations of a Million Particles The Cell Multipole Method for Coulomb and London Nonbond Interactions. 

Considering long-range MD, a variety of approximate methods have been developed to overcome the bottleneck that characterizes the forces treatment these include particle mesh algorithms, hierarchical methods, and fast multipole methods. One of the most promising developments is the cell multipole method, which scales linearly with N, requires only modest memory, and is well suited to highly parallel and vector computers. 

H. Q. Ding, N. Karasawa, and W. A. Goddard III,/. Chem. Phys., 97,4309 (1992). Atomic Level Simulations on a Million Particles The Cell Multipole Method for Coulomb and London Interactions. 

There is a growing number of approaches to treat the essentially infinite reach of charge-charge interactions. To mention just a few of the more traditional numerical ones which are well adapted to the requirements of MD, we have charge group cut-off [63], Ewald [72] summation, smooth particle Ewald [66] summation and particle-particle-particle-mesh (P M) [73]. There are also several variations of hierarchical methods [74] a few examples are the method of Bames and Hut (BH) [75], the fast multipole method (EMM), with [76] and without [77] multipoles, and the cell multipole method [78]. 

We note, however, in the present context that as discussed in Chapter 4, there are two alternative techniques to the Ewald sum method for evaluating the long range Coulomb interactions. One is the Particle-Particle/Particle-Mesh method (PPPM) (Eastwood et al., 1980) and the other is the Cell Multipole Method (CMM) (Greengard and Rokhlin, 1987). The computational cost for both PPPM and CMM scale as N, the number of particles, while for the Ewald sum the cost scales as Ni>2 (Fincham, 1994). Of the two alternative techniques, the CMM is gaining more popularity mainly because it is applicable to non-periodic and inhomogeneous systems as well and it is more amenable to parallelization. CMM is slower than the Ewald sum for small systems but it is faster for very large systems. However, it is not certain yet at which value of N the crossover occurs. Values between 300 and 30000 have been quoted (Fincham, 1994). 

The cell multipole method (also called the fast multipole method) is an algorithm that enables all N N — 1) pairwise non-bonded interactions to be enumerated in a time that scales linearly with N, rather than N, as in the standard Ewald approach [Greengard and Roklin 1987 Ding et al. 1992a, b Greengard 1994]. The cell multipole method can be used to evaluate interactions that can be expressed in the following general form ... 

This multipole expansion is only valid if the separation between the interacting particles (be they atoms, molecules or cells) is larger than the sum of the radii of convergence of the multipoles. In the cell multipole method, the multipole expansion is used for interactions that are more than one cell distance away. For interactions that are within one cell distance the usual atomic pairwise interaction method is employed. 

Cell Multipole Method for Dipolar and Charged Dipolar Systems. 

Ding HQ, Karasawa N, Goddard WA (1992) Atomic level simulations on a million particles -the cell multipole method for Coulomb and London nonbond interactions. J Chem Phys 97(6) 4309 315... 

---