Fast Methods for Long Range Interactions in Complex Systems
Forschungszentrum Juelich, 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].
Paul Gibbon ( Forschungszentrum Jülich ) - Organiser
Thomas Lippert ( Forschungszentrum Jülich ) - Organiser
Godehard Sutmann ( Forschungszentrum Juelich ) - Organiser