 Theory of the N-Body Problem
June 9, 1996
27
1.6 Speed-up Techniques
Section 1.4.1 on page 20 discusses some of the factors in evaluating the force
function
f()
, but there are a couple of simple changes that can be done to even the straight
forward
O(n
2
)
evaluation method. These changes can make a significant improvement in
the speed of the program. First, because the forces between two stars are always equal and
opposite, when the force is calculated for one star, the result can be applied to both. This
cuts the cost in half, although it doesn't change it from being
. Secondly, a time step
value of 1 can be used which, in most methods, causes all the
h
n
's to drop out of the calcu-
lations. Thirdly, the gravitational constant
G
can be set to 1, saving a multiplication for
every evaluation
f()
.
On the surface, these changes might seem to make XStar work in some unreal uni-
verse where gravity has a different strength but, under closer inspection, it can be shown
that this is not true. The value of
G
is different in imperial units (
32 ft/s
2
) and in metric
(
9.8 m/s
2
). Simply choosing the right units of measure and time can force
G
to be equal to
one. XStar can still model the same physical systems this way, after converting everything
from normal units to these "special" units.
As outlined in Section 1.3 on page 17, the accuracy of the ODE integration
methods can increased or decreased by changing the step size
h
. With
h
now being defined
as 1, how can the accuracy of the system be changed? The answer is that if you work
through the units of
G
and its use in Newton's formulas, it can be shown that to make the
star movements twice as accurate, you must cut the speed of all the stars in half and
decrease the masses by a factor of 4. The smaller masses mean less acceleration, but the
lower speeds keep the stars from flying off.
1.7 The Error Term
The final aspect of solving the N-body ODE that needs to be considered is the error
term that was mention in Section 1.3 on page 17. Recall that there are three basic parts of
the error term:
*
some constant
*
some power of h
*
the evaluation of a derivative of
f()
at some point in the time interval from
t
to
t+h
.
That is, the error term has the form:
where
.
In Section 1.6 on page 27 it was said that the step size,
h
, should be equal to one.
Since the constant
c
is often unknown, the derivative of the function is very hard to calcu-
late and the time is impossible to know, it appears that the only part of the error term that
is
known is
h
, which is now the constant 1. On the surface, this might seem to make the
error term meaningless or impossible to use. Fortunately, this is only partially true.
O n
2
( )
E
c h
n
f
n
( )
( )
=
t
...
t h
+
(
)