Theory of the N-Body Problem

June 9, 1996

21

There are three components of the speed that must be considered:

Firstly, how efficiently a method uses the results of the force function

*f()*

must be

considered. As an example, Euler's is normally much less efficient than a fourth order

Taylor series because in order to get the same accuracy with Euler's method, the step size

would have to be much smaller and therefore,

*f()*

would have to be evaluated many more

times. This turns out to be the predominate consideration for XStar.

Secondly, how efficiently a method selects the points in time to evaluate

*f()*

must

be considered. The time step needs to be shortest when

*f()*

is changing rapidly in order to

keep the discretization error to a minimum. But using the same step size when

*f()*

is chang-

ing slowly is inefficient. Dynamically changing the step size makes a method more com-

plicated, and it also makes the results come out at an irregular rate. For some applications

it is ok for a method to take considerably longer to return a result in certain situations than

in other situations. XStar, however, needs to display the results in real time. The speed in

which the star trails are displayed on the screen needs to reflect how fast the stars are

moving.

Thirdly, how efficiently a routine calculates the function

*f()*

must be considered. A

straight forward implementation of

*f()*

as outlined in Section
1.3 on page
17 produces a

routine that takes O(

*n*

*2*

) operations. So, when the number of stars is doubled, the routine

will take four times as long to complete. There are methods of calculating

*f()*

that are

O(

*n*
*log*
*n*

) or even O(

*n*

), but they are much more complicated to implement. While this is

very important when you are calculating the movements of the millions of stars in a

galaxy, for XStar, this is not as important of a consideration.

Another aspect of the definition of "a better method" is how do we determine

which method "has the greatest accuracy?" We know that all methods that use numerical

analysis to find a solution must have a degree of error in them, and that these errors accu-

mulate. So, let's try this for an initial definition of accuracy:

Definition:

One method is more

**accurate**

than another if the results more

closely match what would happen in the real world.

This really is what the definition of accuracy should be, but there is a problem:

how can the computers' results be compared to the real world? This would require experi-

ments that would be very hard to perform. In Marciniak's book,

*Numerical Solutions of*

*the N-body Pr**oblem*

(12:54-6)

, he uses a two body system that he can derive exact values for

and compares the computers' results to these exact answers. However, it is very question-

able that this method is suitable for judging the accuracy of 15 stars that are interacting, let

alone millions of stars.

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