Efficient Force Function Evaluation Methods
June 9, 1996
49
Top down trees are created by taking space and splitting it into regions (4 for the 2-
D case, 8 for 3-D). If a region has more than one star, it is further sub-divided until each
region contains only one star. Then, working back up the tree, the centers of mass for each
region is calculated. The different regions of space are typically numbered with a special
method called "oct codes" so that it is easier to find which regions are close to each other.
Sources: (18:13-15,8:5-7,5:4-8,6:11-16)
4.6 Hybrid Force Evaluation Methods
Due to the principle of superposition, it is possible to break the force into several
parts, such as:
It is then possible to use a different method to calculate each component of the force. For
example, a mesh method could be used to create the far force and if you make sure the
mesh is large enough so that there are substantially fewer mesh points than bodies, then
you will have an
O(n)
routine to calculate the bulk of the stars. For medium range bodies,
one of the tree methods could be used, giving an
method for the bulk of the
remaining bodies. When there are small clusters of only 3-6 bodies, the simple Particle-
Particle method could be used. Finally, for close passes and binary systems, Kepler orbits
can be used.
By using several of these methods, it is possible to create a system that is substan-
tially faster and more accurate than any one method could possibly be. While I know of no
implementation that uses all of these methods, most of the current research methods seem
FIGURE 28. Top down tree for evaluating the force function
f x t
( )
(
)
near_force far_force external_force
+
+
=
O n
n
log
(
)