Variable Step Size N-Body ODE Integration Methods

June 9, 1996

40

The second area of efficiency that was discussed in Section
1.4.1 on page
20 was

that you don't have to select equally spaced points in time to evaluate the force function

*f()*

. As was seen in Section
1.2.3 on page
10, the force function

*f()*

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.

(10:6)

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

*h*

so

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.