NIC Series Volume 41:   Multigrid methods for structured grids and their application in particle simulation Matthias Bolten   ISBN 978-3-9810843-7-5 December 2008, 153 pages   PDF

This work is focussed on the application of multigrid methods to particle simulation methods. Particle simulation is important for a broad range of scientific fields, like biophysics, astrophysics or plasma physics, to name a few. In these fields computer experiments play an important role, either supporting real experiments or replacing them. The first can significantly reduce costs, e.g. in the pharmaceutic industry, where possible agents can be checked for an effect in advance of real and expensive experiments. The latter has an important role in astrophysics, where most experiments just cannot be carried out in a laboratory. In the cases we are interested in, the interaction of particles can be evaluated by pairwise potentials, where short-ranged potentials, e.g. potentials describing chemical bonds, are easy to be implemented efficiently. But the very important Coulomb potential and the gravitational potential are not short-ranged, thus an intuitive implementation has to evaluate all pairwise interactions, yielding an O(N²) algorithm, where N is the number of particles to be simulated. The key to reduce this complexity is the use of approximate algorithms for the evaluation of the long-ranged potentials.