CS294-3: Algorithms in the Real World (Guy Blelloch, Fall 97)

#

Topic 6: N-body Simulations

[ Topics |
Scribe Notes |
Readings |
Text Books |
Links ]

N-body 1 (draft) (Tajh Taylor)
N-body 2 (draft) (Steven Gribble)
The Numerical Solution of the N-Body Problem, L. Greengard
(abstract).
N-body/Particle simulation Methods.
An excellent online overview of various n-body methods.

**Note:** we will be spending most of our time
on the tree and FMM methods, so if you don't understand the other
methods described very well, don't worry.
Cosmological N-body Simulation.
Not required, but a good short reading on the state-of-the-art
in nbody simulations in cosmology from
the N-body Shop.
**The only textbook I know of on the subject**
Susanne Pfalzner and Paul Gibbon.
Many Body Tree Methods in Physics.
Cambridge University Press, 1997.
**Articles on the subject**
Fast algorithms for classical physics, L. Greengard
(abstract).
A hierarchical O(N Log N) force calculation algorithm.
J. E. Barnes and P. Hut. Nature, 324(4):446-449, December 1986.
Fast parallel tree codes for gravitational and fluid dynamical
N-body problems. Salmon, Warren and Winckelmans.
(abstract).
Scalable variants of multipole-based algorithms for molecular
dynamics applications.
Board, Hakura, Elliot, and Rankin.
(abstract).
Optimal parallel all-nearest-neighbours using the well-separated
pairs decomposition.
P.B. Callahan. In 34th Annual Symposium on Foundations of Computer Science, pages 332-340, Palo Alto, 1993. IEEE.
Astrophysical n-body simulations using hierarchical tree data
structures.
M. Warren and J. Salmon. In Proceedings of Supercomputing, 1992.
**General links**
A Survey
from the Edinburgh Parallel Computing Centre.
Parallel N-Body Simulations.
Nbody
methods, from a Astronomy course by Joshua Barnes.
Here are two online lectures on the Barnes Hut
and Greengard methods from
a course by
Jim Demmel at Berkeley.
**Implementations and comparisons**
Available software for n-body simulations.
A Data-Parallel Implementation of the Adaptive Fast Multipole Algorithm
by Lars Nyland, Jan Prins, and John Reif
Scientific Computing Group at the Dept. of Electrical Eng, Duke University.
**Astrophysics**
The N-body Shop at
the University of Washington.
Some images (JPEG) and movies (MPEG) of structure
formation in the universe.
A theoretical astrophysics page
from Los Alomos national labs.
Stellar Dynamical Systems, from a course by Joshua Barnes.
**Vortex Methods and Fluid Dynamics**
The Parallel hierarchical N-body solvers for vortex flows
Grid-Free Simulation of 3-D Viscous Flows
Multibody Fluid Dynamics by a Vortex
Particle/Boundary Element Method
SPH -- Smoothed Particle Hydrodynamics.
Has lots of pointers to general work and codes for the n-body problem.
Application of Fast Parallel and Sequential Tree Codes to
Computing Three-Dimensional Flows with the Vortex
Element and Boundary Element Methods

Back to the Algorithms in the Real World home page.

Guy Blelloch,
guyb@cs.berkeley.edu.