Efficient Force Function Evaluation Methods

June 9, 1996

43

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.

This document is best viewed as n-body.pdf because the translation to html was buggy.