An O(N) Algorithm for Three-Dimensional N-Body Simulations

Abstract

The author presents an algorithm that computes the gravitational potentials and forces on N point-masses interacting in three-dimensional space. The algorithm, based on analytical techniques developed by Rokhlin and Greengard, runs in order N time. In contrast to other fast N-body methods such as tree codes, which only approximate the interaction potentials and forces, this method is exact-it computes the potentials and forces to within any prespecified tolerance up to machine precision. Presented is an implementation of the algorithm for a sequential machine. The author numerically verifies the algorithm, and compare its speed with that of an O(sq N) direct force computation. He also describes a parallel version of the algorithm that runs on the Connection Machine in order O(log N) time. This document compares experimental results with those of the sequential implementation and discusses how to minimize communication overhead on the parallel machine.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Oct 01, 1987
Accession Number
ADA196903

Entities

People

  • Feng Zhao

Organizations

  • Massachusetts Institute of Technology

Tags

Communities of Interest

  • Energy and Power Technologies

DTIC Thesaurus Topics

  • Accuracy
  • Algorithms
  • Artificial Intelligence
  • Cartesian Coordinates
  • Computational Complexity
  • Computational Science
  • Computer Science
  • Electrical Engineering
  • Engineering
  • Far Field
  • Fluid Dynamics
  • Molecular Dynamics
  • Near Field
  • Parallel Computing
  • Three Dimensional
  • Trees (Data Structures)
  • Two Dimensional

Fields of Study

  • Computer science

Readers

  • Finite Element Method (FEM) for solving Partial Differential Equations (PDEs)
  • Graph Algorithms and Convex Optimization.
  • Software Engineering

Technology Areas

  • Space
  • Space - Spacecraft Maneuvers