 Efficient Force Function Evaluation Methods
June 9, 1996
48
For the case of the gravitational N-body problem, it is possible to not have to apply
the star to each mesh point at every step. Instead, only the nearest mesh points need to be
updated every time, the ones that are further away can be updated less often. This is some-
what analogous to the discussion in Section 4.3 on page 46.
Sources: (8:3-4,6:1-10)
4.5 Creating Tree Structures For Evaluating the Force Function
The techniques described in Sections 4.2 and 4.3 can be applied in a hierarchial
"tree" fashion. There are two basic approaches, namely bottom up and top down trees.
Using either method, it is possible to create an force function evaluation method that is
O(n
2
)
, a significant improvement. The nodes in the trees are also
prime locations to store information needed to implement variable step size ODE integra-
tion methods that have different step sizes for different stars. There are actually several
variations of each of these types of trees, depending on how exactly the splitting and
joining is carried out. The following are just typical examples.
Bottom up trees can be built by taking individual stars that are close together and
replacing them with their centers of mass, and then taking the centers of mass and group-
ing them together. This process is repeated until only the center of mass of the entire
system is left. The force function can be evaluated for individual stars by traversing the
tree and if a particular branch of the tree is "distant", we can just use that particular nodes
center of mass.
O n
n
log
(
)
FIGURE 27. Bottom up tree for evaluating the force function
= Star
= Center of mass
= Tree branches
Root node