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

Title: en_US An O(N) Algorithm for Three-Dimensional N-Body Simulations
Creator: en_US Zhao, Feng
Date: 2004-10-20T20:10:52Z
Date Available: 2004-10-20T20:10:52Z
Date Issued: en_US 1987-10-01
Identifier: en_US AITR-995
uri: http://hdl.handle.net/1721.1/6962
Abstract: en_US We develop 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 ?? computes the potentials and forces to within any prespecified tolerance up to machine precision. We present an implementation of the algorithm for a sequential machine. We numerically verify the algorithm, and compare its speed with that of an O(N2) direct force computation. We also describe a parallel version of the algorithm that runs on the Connection Machine in order 0(logN) time. We compare experimental results with those of the sequential implementation and discuss how to minimize communication overhead on the parallel machine.
Extent: 4592892 bytes; 3220469 bytes
Format: application/postscript; application/pdf
Language: en_US
Relation: en_US AITR-995