Variable Step Size N-Body ODE Integration Methods
June 9, 1996
The second area of efficiency that was discussed in Section
1.4.1 on page
that you don't have to select equally spaced points in time to evaluate the force function
. As was seen in Section
1.2.3 on page
10, the force function
has periods when it is
changing very rapidly and periods when it is very smooth. The system needs the most
accuracy when a star is making a sharp curve around another star, and it needs the least
accuracy when a star is slowly moving off in a fairly straight line.
Many of the ODE integration methods, the Runge-Kutta method and the Gragg-
Bulirsch- Stoer method in particular, can estimate the accuracy of the results that they are
returning and it is possible to have them adjust the step size accordingly.
The major problem with variable step size methods in XStar is that they tend to
have the smallest step size, and thus run slower, when the stars are actually moving the
fastest. If you implemented a variable step size method and didn't do anything to counter-
act this, you would see stars "slow down" as they approached collapsars and "speed up"
when they are far away from them. For this reason, no variable step size methods were
considered for XStar.
Another consideration when using variable step size methods is that the most well
known implementations decrease the step size for all stars in the system anytime any of
the of the stars need greater accuracy. When there is even a moderately large number of
stars, say around 20-40, there will almost always be at least one star that needs a small step
size. Implementing separate step sizes for each star can be complicated because you can't
update the locations/velocities all at once. Some stars many need to be updated many
times before some other star gets updated once, and until a star has been moved you can't
calculate the force function. One method of getting around this is to create a polynomial
approximation of the path and any time you need to find the location of a star, you evalu-
ate this polynomial.
The key to creating a variable step size ODE integration method is to find a bound
on the error term. If the error term is too large, then you need to decrease the step size. On
the other hand, if the error term is too small, then you should be able to increase the step
size without causing any serious problems. The CPU time you save can be used when a
small step size is really needed.
Care must be taken not to try and make the lower bound of the error too small. The
computer can always make the error value equal to zero by making the step size
small, that the stars won't move at all. Instead of using a global lower bound on the error,
it is often better to make it relative to the size of velocity, or some other flexible formula.
The following sections describe the four major ways of implementing a variable
step size method
This document is best viewed as n-body.pdf because the translation to html was buggy.