N-Body Methods Resources

Local Resources

The summary of a survey on N-body methods I performed sometime ago.

Thesis: Numerical Study of Three-Dimensional Flow using Fast Parallel Particle Algorithms.

The following thesis was written by Gavin Pringle. The following parts can be downloaded:

abstract: The abstract to the thesis, in ASCII
thesis  : The thesis itself, in compressed postscript
          format (454 kb).
Figure  : Figure 2, from chapter 7, in compressed 
          postscript format (25.5 kb).

Remote Resources

Jurgen Singer's Bibliography on Fast Summation Methods and N-body methods

The XStar N-body Solver

XStar is an X11 client that ``solves'' the N-body Problem, and displays the results on the screen. It starts by putting a bunch of stars on the screen, and then it lets the inter-body gravitational forces move the stars around. The result is a lot of neat wandering paths, as the stars interact and collide.

The XStar program is not a "serious" n-body problem solver, it is actually just a X-windows screen saver. However, it does have the option of using any one of a number of ODE integration methods, for Euler's to a Gragg-Bulirsch-Stoer method. I also wrote up a paper that gives an introduction to the N-body problem. I am sure that everything it it you would already know, but for those people who are just getting into the N-body problem, it might be of some use.

A Parallel Tree Code

We describe a new implementation of a parallel N-body tree code. The code is load-balanced using the method of orthogonal recursive bisection to subdivide the N-body system into independent rectangular volumes each of which is mapped to a processor on a parallel computer. On the Cray T3D, the load balance is in the range of 70-90% depending on the problem size and number of processors. The code can handle simulations with > 10 million particles roughly a factor of 10 greater than allowed on vectorized tree codes.

BOOK: Many Body Tree Methods in Physics

We have just completed a book about N-body tree methods, including a lay-introduction to the Barnes-Hut and Greengard-Rohklin (FMM) algorithms. This will be available shortly (August 1996) from Cambridge University Press.

S. Pfalzner & P. Gibbon, 'Many Body Tree Methods in Physics', CUP 1996, ISBN 0-521-49564-4 (hardback).

We are also interested in using tree codes for collisional and collisionless plasma simulation. An implementation of the Barnes-Hut method for periodic plasma systems can be found in:

S. Pfalzner & P. Gibbon, Computer Physics Communications 79, 24-38 (1994)

Reprints available from pfalzner@astro.uni-jena.de on request.

The N-body Shop. (HPCC GROUP University of Washington).

This interdisciplinary group lead by George Lake includes faculty and students from the Departments of Astronomy, Physics, Applied Math and Computer Science & Engineering at the University of Washington in Seattle. A paper prepared for a recent SIAM conference provides an overview of cosmological simulation. Other servers give a general description of the Interagency HPCC project and the Earth and Space Sciences Component within NASA's HPCC Program.

NEMO Home Page.

NEMO is an extendible Stellar Dynamics Toolbox. It has various programs to create, integrate, analyze and visualize N-body and SPH like systems. In addition there are various tools to operate on images, tables and orbits, including FITS files to export/import to/from other astronomical data reduction packages. We also advertise other software packages , which work on similar problems.

ParallelN-Body Simulations.

This work deals with the parallel implementations of N-Body algorithms, which have applications in a number of areas such as astrophysics and fluid dynamics. We are interested in comparing two popular algorithms, the Barnes-Hut algorithm, and Greengard's Fast Multipole Method, both of which use multipole expansions and hierarchical data structures to reduce the complexity of computing long-range interactions like gravity. These algorithms have been implemented in NESL.

N-Body / Particle Simulation Methods

Amara's Recap of Particle Simulation Methods ("ARPSM" !!): My own experience with N-body simulation methods are with schemes using direct integration of forces ("Particle Particle" methods), and also with the symplectic methods. When a discussion in August 1995 on the sci.math.num-analysis newsgroup about N-body/Particle simulation methods caught my attention, I wrote this article to keep track of the different schemes (too many acronyms!), and to learn what researchers in the field are using today.

This is mirrored by Gavin Pringle at Napier in the UK.

Grand Challenge Cosmology Consortium

The Grand Challenge Cosmology Consortium is an NSF-funded HPCC grand challege project devoted to harnessing the power of parallel computers to explore the origin of large scale structure in the universe and how galaxies form. Consortium institutions include Princeton, MIT, U. Illinois, Indiana U., U.C. Santa Cruz, U. Pittsburgh and the NCSA and PSC supercomputer centers.

Theoretical Astrophysics (T-6)

This is the home page of the Theoretical Astrophysics group at Los Alamos National Laboratory.

Cardiff Star Formation Group

We use smoothed particle hydrodynamics (SPH) with tree-code gravity (TCG) for our simulations, and run on local Sun workstations, the KSR at Manchester Computing Centre, and the Cray-YMP at RAL, Oxford. Simulations are represented as column density plots.

Dynamical Simulation of the N-Body Problem

The simulation of many-body, many particle system has a wide range of applications in area such as biophysics, chemistry, astrophysics, etc. It is known that the force calculation contributes 90% of the simulation time. This is mainly due to the fact that the total number of interactions in the force is O(N^2). My current research is to parallelize the Fast Multipole Method, which is of order O(N), proposed by Greengard and Rokhlin. My advising faculty is Dr. Daniel Okunbor. I am also in the Numerical Computing Research Group.

HPF Application - O(N**2) N-Body Particle Dynamics

Include molecular dynamics and classical astrodynamics applications. The new Fast Multipole Method with its O(N) or O(NlogN) complexity outperforms the classic (N**2) approach. The crossover point is of order N=10,000. This value of N is quite large for many chemistry calculations which still therefore use the classic method. However astrophysics simulations with N from 100,000 to 10,000,000 clearly require and use the newer multipole methods.

N-body Methods on MIMD Supercomputers : Astrophysics on the Intel Touchstone Delta.

We have used hierarchical N-body methods running on a MIMD parallel supercomputer to follow the evolution of systems with large numbers of particles (). The nonlinear gravitational collapse of galaxies from cosmological seed perturbations, the tidal stripping of globular clusters by galaxies and the collision of stellar systems have been studied in detail. The measured sustained performance of these methods for gravitational astrophysical problems exceeds 5 Gflops on the 512 node Intel Touchstone.

N-Body Models of Collisionless Systems

Informally, a self-gravitating system is collisionless if the granularity of its mass distribution does not influence its evolution. Galaxies, in particular, are expected to evolve collisionlessly even over timescales much longer than a Hubble time. This chapter describes an N-body algorithm for simulating the evolution of collisionless systems.

Using Adaptive Particle-Mesh Method

The complete manuscript is available in postscript. The code is a shell archive, /pub/hpcc/adap.sh.Z in our ftp archive. It contains a full N-body code with potential solver and time evolution. There is a seperate program to generate initial conditions. The final state of a Dark Matter simulation using Couchman's code has been created using the group's visualization program: TIPSY.

Tree Codes for N-body Simulations

This is part of the book "Parallel Computing Works" by Geoffrey C. Fox, Roy D. Williams and Paul C. Messina.

A Parallel Adaptive Fast Multipole algorithm for N-body problems

in Proceedings of the International Conference on Parallel Processsing, August 1995.
Abstract:
We describe the design and implementation of a parallel adaptive fast multipole algorithm (AFMA) for N-body problems. Our AFMA algorithm can organize particles in cells of arbitrary shape. This simplifies its parallelization, so that good locality and load balance are both easily achieved. We describe a tighter well-separatedness criterion, and improved techniques for constructing the AFMA tree. We describe how to avoid redundant computation of pair-wise interactions while maintaining load balance, using a fast edge-partitioning algorithm. The AFMA algorithm is designed in an object oriented, message-driven manner, allowing latency tolerance by overlapping computation and communication easily. It also incorporates several optimizations for message prioritization and communication reduction. Preliminary performance results of our implementation using the Charm++ parallel programming system are presented.

Parallel Fast Multipole Method

In collaboration with the researchers at Boeing Corporation a parallel formulation of the fast multipole method (FMM) using MPI is being developed. FMM is a hierarchical divide-and-conquer strategy for calculating long-range (e.g. Coulomb) interaction in N-body simulations with a computational cost of order N (direct calculation is order N2). Parallel formulation of FMM involves partitioning a tree structured task graph among multiple processors with the combined (load-balancing) objectives of minimizing inter-processor communication and equalizing the computational work load. When particle distributions are uniform these objectives are not difficult to achieve, however, when the particles are non-uniformly distributed one must deal with dynamic, irregular data structures.

Applications of Parallel Computers

Lectures 26 (Fast Hierarchical Methods for the N-body Problem) and 27 ( Fast Hierarchical Methods for the N-body Problem (continued) ) appear to be the most pertinent.

Fast Multipole Method Technical Reports

This directory contains copies of papers that were found across the internet regarding the Fast Multipole Algorithm. Links to the original groups will be provided when I find them again. I have stored the papers in a compressed format. All files are stored as compressed PostScript. Our server provides compression information on the fly.

N-Body Models of Collisionless Systems

Informally, a self-gravitating system is collisionless if the granularity of its mass distribution does not influence its evolution. Galaxies, in particular, are expected to evolve collisionlessly even over timescales much longer than a Hubble time. This chapter describes an N-body algorithm for simulating the evolution of collisionless systems.