Navigation and service

Fast Methods for Long Range Interactions in Complex Particle Systems

Contents and objectives

The natural complexity of long range interactions is O(N2), which strongly limits the size of particle systems in computer simulations of complex systems. Depending on the boundary conditions (open or periodic boundaries), the tolerated approximation error and the parallel performance, different methods were developed. For open boundary conditions, hierarchical methods are often used, like the Fast Multipole Method (FMM) or the Barnes-Hut-Tree Method (BHTM). Applying techniques, like space-filling curves, the BHTM is capable of treating strongly inhomogeneous systems, as it is often found in astrophysical applications. The majority of simulations in condensed matter problems 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(N3/2) if parameters are optimized. Faster methods, which are based on Fast Fourier Transform (FFT) techniques, include e.g. the Particle-Mesh Ewald, or the Particle-Particle Particle-Mesh Ewald (P3M). 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. New developments of algorithms, which are also introduced during 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 and local methods to solve Maxwell equations.

During the summer school, various modern methods and algorithms (like FMM, BHTM, P3M, NFFT, multigrid) are introduced and presented, which strongly reduce the computational complexity. Introductions are provided for each method, complemented by details on how to parallelize the methods efficiently for modern high-performance computers. During the hands-on the newly developed parallel library ScaFaCoS ( for long range interactions will be introduced and applied to physical examples. Participants are encouraged to bring their own codes into which the library can be included and get first-hand experience with modern numerical techniques. Participants will be assisted and supported by developers of the library. To get people who are not familiar with parallel computing prepared, the first day will provide an introduction to basic concepts of parallel computing as well as various parallelization approaches.

The school aims to attract PhD students, postdocs or senior scientists who want to learn about modern approaches to long range interactions or who want to apply these efficient algorithms in their own simulation programs.