# Schools

## Fast Methods for Long Range Interactions in Complex Systems

### Organisers

- Paul Gibbon
*(Forschungszentrum Jülich, Germany)* - Thomas Lippert
*(Forschungszentrum Jülich, Germany)* - Godehard Sutmann
*(Research Center Jülich, Germany)*

### Supports

### Description

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 [8], which may be shown to scale like O(N^3/2) if parameters are optimised [9]. Faster methods, which are based on Fast Fourier Transform (FFT) techniques, include the Particle-Mesh Ewald [22], the Smooth Particle Mesh Ewald [23] 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 [10] and MMM2d [11] 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 [14], 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 [15], fast summation algorithms based on Non-equidistant Fast Fourier Transforms (NFFT) [16], Multigrid solvers [17,18] and local methods to solve Maxwell equations [19,20].

### References

[1] 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).

[2] L. Greengard and V. Rokhlin, A fast algorithm for particle

simulations, J. Comp. Phys. 73, 325 (1987).

[3] C.A. White and M. Head-Gordon, Fractional tiers in fast multipole

method calculations, Chem. Phys. Lett. 257, 647 (1996).

[4] 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).

[5] J.E. Barnes and p. Hut, A hierarchical O(NlogN) force calculation

algorithm, Nature 324, 446 (1986).

[6] M. S. Warren and J. K. Salmon. A portable parallel particle

program. Comp. Phys. Commun., 87, 266 (1995).

[7] S. Pfalzner and P. Gibbon, Many Body Tree Methods in Physics,

(Cambridge University Press, New York, 1996).

[8] P. P. Ewald, Die Berechnung optischer und elektrostatischer

Gitterpotentiale, Ann. Phys. 64, 253 (1921).

[9] 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).

[10] A. Arnold and C. Holm, MMM1D: A method for calculating electrostatic

interactions in one-dimensional periodic geometries, J. Chem. Phys.,

123, 144103 (2005)

[11] 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)

[12] 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)

[13] 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).

[14] A. Arnold, J. de Joannis and C. Holm, Electrostatics in Periodic Slab

Geometries I, J. Chem. Phys. 117, 2496 (2002).

[15] I. Kabadshow, The Fast Multipole Method: Error analysis,

performance optimization and extension to 1d-, 2d- and 3d-periodic

systems. PhD thesis University Wuppertal (submitted).

[16] 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).

[17] G. Sutmann, B. Steffen, A particle-particle particle-multigrid

algorithm for long-range interactions in molecular systems,

Comp. Phys. Comm. 169, 343 (2005).

[18] 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.

[19] G. Sutmann and B. Steffen. High-order compact solvers for the three

dimensional Poisson equation. J. Comp. Appl. Math., 187:142170,

2006.

[20] I. Pasichnyk and B. Duenweg, Coulomb interactions via local dynamics:

A molecular dynamics algorithm, J. Phys. Cond. Matt. 16, 3999 (2004).

[21] A.C. Maggs and V. Rossetto, Local simulation algorithms for

Coulomb interactions, Phys. Rev. Lett. 88, 196402 (2002)

[22] 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).

[23] 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).