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)

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

instead of

*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

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