Efficient Force Function Evaluation Methods
June 9, 1996
43
4.0 Efficient Force Function Evaluation Methods
When there are large number of stars, the evaluation of
f()
can be very time con-
suming. If the formula in Section 1.3 on page 17 is implemented in the obvious fashion,
the distance to every star must be found for every star, a process that takes on the order of
n
2
operations. This particular method of evaluating the force function is known as a Parti-
cle-Particle method because each star is treated as a particle and it is checked against other
stars (particles). If you have say, 100 stars, then there will be 100 evaluations of the force
function f(), each of which will have 99 terms that involve the expensive operations of
division and taking a square root. For Xstar with a system of 100 stars, the evaluation of
the force function will account for well over 75% of the CPU time used. The integration
taking up around 10% and all the other housekeeping and display code taking up the last
15% of the CPU. Even for the default configuration of only 15 stars, the evaluation of the
force method accounts for almost half of all CPU time used. For other N-body programs
that have to evaluate thousands or even millions of bodies, this method of evaluating the
force function is almost completely useless.
Because the efficient evaluation of the force function
f()
is so critical for most N-
body programs, this has been a very active area of research in the last 15 years. There are
many different approaches, but so far there doesn't seem to be any particular method that
has become the clear favorite among the N-body research community. While there is also
a wide variety of ODE integration methods, they at least have well known trade-offs and
areas of strengths. The trade-offs among the force evaluation methods do not appear to be
as well known.
The list of methods of evaluating the force function contains many exotic names,
such as:
(8)
*
Particle-Particle
*
Particle-Mesh
*
Particle-Particle/Particle-Mesh
*
Tree-Code Top Down
*
Tree-Code Bottom up
*
Fast-Multipole-Method
*
Tree-Code Particle-Mesh
*
Self-Consistent Field
*
Symplectic Method
Since this is still an area of active research, this document will not try to give a
complete overview of this area. Instead, a few techniques will be discussed and interested
readers are encouraged to read the internet document ftp://ftp.amara.com/papers/nbody.txt
(8)
which is a very good starting point for finding more information in this area.
 Previous page Home Table of Contents Next page
 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57
This document is best viewed as n-body.pdf because the translation to html was buggy.