 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.
1.4.2 The Accuracy of a Method
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 Problem
(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.