Fast Methods for Long Range Interactions in Complex Systems
- Paul Gibbon (Forschungszentrum Jülich, Germany)
- Thomas Lippert (Forschungszentrum Jülich, Germany)
- Godehard Sutmann (Research Center Jülich, Germany)
Computer simulations of complex particle systems have a stronglyincreasing impact in a broad field of physics, e.g. in astrophysics,statistical physics, plasma physics, material sciences or phyisicalchemistry and biophysics. Along with the developmen of computerhardware, which nowerdays shows a performance in the range of PFlop/s,it is essential to develop efficient and scalable algorithms whichsolve the physical problem. Since with more powerful computer systemsusually also the problem size is increased, it is important toimplement optimally scaling algorithms, which increase thecomputational effort propertionally to the number of particles.Especially in fields, where long-range interactions between particleshave to be considered the numerical effort is usually very high.
The natural complexity o long range interactions is O(N^2), which strongly limits the range of applicability for larger systems. Depending on the boundary conditions (open or periodic boundaries), the tolerated approximation error and the parallel performance, different methods were developed and extended in various directions. For open boundary conditions, hierarchical methods are often used, like the Fast Multipole Method (FMM) [2-4] or the Barnes-Hut-Tree Method (BHTM) [5-7]. Via the use of space-filling curves, the BHTM is also able treet strongly inhomogenous systems, as it is often the case in astrophysical applications. The majority of simulations is, however, performed in periodic boundary conditions in order to avoid artifacts originating from physical boundaries. Traditionally, the Ewald sum is applied , which may be shown to scale like O(N^3/2) if parameters are optimised . Faster methods, which are based on Fast Fourier Transform (FFT) techniques, include the Particle-Mesh Ewald , the Smooth Particle Mesh Ewald  or the Particle-Particle Particle-Mesh Ewald (P3M) [12,13]. Calculating electrostatic interactions in partial periodic systems, i.e. in 1d- or 2d-periodic systems, requires re-formulations of the algorithms, which sometimes have a worse numerical complexity than their 3d-periodic counterpart. The so called MMM1d  and MMM2d  methods treat electrostatics in 1d- and 2d-periodic systems respectively, allowing to control the approximation error. These methods, however, show a scaling behavior like O(N^2) or O(5/3), which limits them to relatively small systems. For 2d-periodic systems the Electrostatic Layer Correction (ELC) was introduced , which applies a 3d-method to a 2d-system by introducing a vacuum slab in one periodic system and introducing a correction term, which partially compensates for this artificial periodic treatment. New developments of algorithms, which are also tought in the Tutorial are extensions of the FMM to 1d-, 2d- and 3d-periodic systems , fast summation algorithms based on Non-equidistant Fast Fourier Transforms (NFFT) , Multigrid solvers [17,18] and local methods to solve Maxwell equations [19,20].
 P. Gibbon and G. Sutmann, Long range interactions in many-particle
simulation, in Quantum simulations of many-body systems: from theory
to algorithms, 10, Eds. J. Grotendorst, D. Marx and A.Muramatsu (John
von Neumann Institute for Computing, Jülich), pp. 467-506 (2001).
 L. Greengard and V. Rokhlin, A fast algorithm for particle
simulations, J. Comp. Phys. 73, 325 (1987).
 C.A. White and M. Head-Gordon, Fractional tiers in fast multipole
method calculations, Chem. Phys. Lett. 257, 647 (1996).
 H. Dachsel, M. Hofmann, G. Rünger, Library Support for Parallel
Sorting in Scientific Computations, Euro-Par 2007, Parallel
Processing, 13th international Euro-Par conference (Springer), LCNS
Vol.4641, p.695 (2007).
 J.E. Barnes and p. Hut, A hierarchical O(NlogN) force calculation
algorithm, Nature 324, 446 (1986).
 M. S. Warren and J. K. Salmon. A portable parallel particle
program. Comp. Phys. Commun., 87, 266 (1995).
 S. Pfalzner and P. Gibbon, Many Body Tree Methods in Physics,
(Cambridge University Press, New York, 1996).
 P. P. Ewald, Die Berechnung optischer und elektrostatischer
Gitterpotentiale, Ann. Phys. 64, 253 (1921).
 J. W. Perram, H. G. Petersen, and S. W. D. Leeuw, An algorithm for the
simulation of condensed matter which grows as the N^3/2 power of the
number of particles, Mol. Phys. 65, pp. 875-893 (1988).
 A. Arnold and C. Holm, MMM1D: A method for calculating electrostatic
interactions in one-dimensional periodic geometries, J. Chem. Phys.,
123, 144103 (2005)
 A. Arnold and C. Holm, MMM2D: A fast and accurate summation method for
electrostatic interactions in 2d slab geometries, Comp. Phys. Comm.,
148, 327 (2002)
 M. Deserno and C. Holm, How to mesh up Ewald sums. I. A theoretical
and numerical comparison of various particle mesh routines,
J.Chem.Phys., 109, 7678 (1998)
 M. Deserno and C. Holm, How to mesh up Ewald sums. II. An accurate
error estimate for the P3M algorithm, J.Chem.Phys., 109, 7694 (1998).
 A. Arnold, J. de Joannis and C. Holm, Electrostatics in Periodic Slab
Geometries I, J. Chem. Phys. 117, 2496 (2002).
 I. Kabadshow, The Fast Multipole Method: Error analysis,
performance optimization and extension to 1d-, 2d- and 3d-periodic
systems. PhD thesis University Wuppertal (submitted).
 D. Potts, G. Steidl and A. Nieslony, Fast convolution with radial
kernelsat non-equispaced knots, Numer. Math. 98, 329 (2004).
interactions, Phys. Rev. Lett. 88, 196402 (2002).
 G. Sutmann, B. Steffen, A particle-particle particle-multigrid
algorithm for long-range interactions in molecular systems,
Comp. Phys. Comm. 169, 343 (2005).
 M. Bolten. Multigrid methods for structured grids and their
application in particle simulation. In NIC Series, volume 41, Juelich,
2008. John von Neumann Institute for Computing.
 G. Sutmann and B. Steffen. High-order compact solvers for the three
dimensional Poisson equation. J. Comp. Appl. Math., 187:142170,
 I. Pasichnyk and B. Duenweg, Coulomb interactions via local dynamics:
A molecular dynamics algorithm, J. Phys. Cond. Matt. 16, 3999 (2004).
 A.C. Maggs and V. Rossetto, Local simulation algorithms for
Coulomb interactions, Phys. Rev. Lett. 88, 196402 (2002)
 T. Darden, D. York, and L. Pedersen, Particle mesh Ewald: an N.log(N) method for
Ewald sums in large systems, J. Chem. Phys. 98, 10089<96>10092 (1993).
 U. Essmann, L. Perera, M. L. Berkowitz, T. Darden, H. Lee and L. G. Pedersen, A
smooth particle mesh Ewald method, J. Chem. Phys. 103, 8577<96>8593 (1995).