CECAM school: Fast Methods for Long Range Interactions in Complex Particle Systems
Summer School, 9-13 September 2013, Jülich Supercomputing Centre, Forschungszentrum Jülich, Germany
Computer simulations of complex particle systems have a strongly increasing impact in a broad field of physics, e.g. in astrophysics, statistical physics, plasma physics, material sciences or physical chemistry and biophysics. Along with the development of computer hardware, which nowadays shows a performance in the range of PFlop/s, it is essential to develop efficient and scalable algorithms which solve the physical problem. Since with more powerful computer systems usually also the problem size is increased, it is important to implement optimally scaling algorithms, which increase the computational effort proportionally to the number of particles. Especially in fields, where long-range interactions between particles have to be considered the numerical effort is usually very demanding.
This CECAM School is organized by Godehard Sutmann, Ivo Kabadshow and Paul Gibbon (JSC) and will take place at Forschungszentrum Jülich, Jülich Supercomputing Centre.
Scope
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 (www.scafacos.de) 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.
Proceedings
Lecture Notes in this area of earlier schools
Fast Methods for Long-Range Interactions in Complex Systems - Proceedings
edited by P. Gibbon, Th. Lippert, G. Sutmann
WE-Heraeus Summer School, 6 - 10 September 2010, Forschungszentrum Jülich
ISBN 978-3-89336-714-6,
Schriften des Forschungszentrums Jülich, IAS Series 6, 2011, ii, 167 pages
Fast Methods for Long-Range Interactions in Complex Systems (pdf, 6 MB)
Participants
Lectures
- Overview Lecture "High Performance Computing on the way to Exascale"
- Introduction "Particle Simulation Methods"
- Introduction to parallel computing "Introduction to MPI"
- General Overview "Long Range Interactions"
- Introduction to "Parallel Methods for Particle Simulations"
The Fast Multipole Method (FMM)
- Introduction into the Method for open boundary conditions
- FMM for Periodic Boundary Conditions in 1d-, 2d- and 3d.
- Parallelization of the Method
Tree Methods
- Overview of Tree-Methods
- The Barnes-Hut Method
- Parallelization of Tree-Methods
Multigrid Methods
- Introduction to Multigrid
- Multigrid for Long-Range Interactions in Particle Simulations
- Parallelization of Multigrid
Fourier-Transform Methods
- Overview over FFT methods
- Minimizing the discretization errors
- Non-Equidistant FFT (NFFT)
- NFFT and Fast Summation
- Parallelization of P3M and NFFT
Hands-on
- MPI - Parallel Programming
- ScaFaCoS - a parallel library for Fast Coulomb Solvers
- Integrating Fast Solvers into User Codes
- Applications of FMM, NFFT, Tree-Codes, Multigrid