15-853: Algorithms in the Real World (Guy Blelloch, Fall 99)

next up previous
Topic 6: N-body Simulations

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

Topic Outline

  • Introduction
  • Algorithms
  • Particle-Particle
  • Mesh based
  • Particle Mesh (PM)
  • Particle-particle particle-mesh (P3M)
  • Nested Grid Particle Mesh (NGPM)
  • Tree based
  • Top-down particle-cell (Appel, and Barnes Hut)
  • Bottom-up particle-cell (Press)
  • Tree-code particle-mesh (Xi)
  • Cell-Cell (Greengard's FMM, Callahan)
  • Applications
  • Astronomy (e.g. formation of galaxies)
  • Molecular Dynamics (e.g. protein folding)
  • Other: Fluid Dynamics, Plasma Physics, ..

    • Scribe Notes

  • N-body 1 (draft) (Tajh Taylor)
  • N-body 2 (draft) (Steven Gribble)

    • Readings

  • 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.

    • Recommended Readings

    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.

    • Further Readings and Links

  • 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.cmu.edu.