N Body Algorithm Comparison

Paul Fishwick (fishwick@cis.ufl.edu)
26 Aug 1994 09:53:23 -0500

Does anyone know of an article which compares N body algorithms?
Tutorial articles and code for N body algorithms are also desired if
available. Many books on galactic and molecular dynamics (both having
long range forces) contain sections on algorithms but I have yet to
find something more cohesive which explains when a particular
algorithm is useful. There are the tree-based algorithms which
are O(NlogN) and some other multipole expansion algorithms are
O(N) but I'm not sure how to compare them yet. For instance,
Greengard-Rokhlin (GR) is O(N) but so is an algorithm, purportedly,
in the book by Binney et al. (Galactic Dynamics, 1987) which does
not reference GR. Has anyone compared these two? Also, I have
had replies (to an earlier post to another group) to the effect
that tree algorithms are sometimes better to use than potential
field algorithms. Thoughts? I'll compile a list of replies from
this query and correlate these replies with those I received
earlier from the other news group.