The n-body problem is this: for a system of n particles with known interactions, find the evolution of the system from a given initial state. The Newtonian n-body problem, for example, is the problem where the interactions are described by Newton's Universal Law of Gravitation. The problem can be reduced to finding the solutions of a system of coupled nonlinear differential equations coming from Newton's laws. The n-body problem is of importance for the understanding of various real applications and astronomical phenomena, and much effort has been made to characterize it. Unfortunately, a general solution does not appear to exist for systems of more than two bodies.
Because it is not possible to find a general solution for most interesting systems, numerical techniques are often used to model n body systems. My program, JavaPlanets, models the behavior of n-bodies in 2-dimensional space when they are acted upon by a known force. The program allows the user to give particles an initial mass, position, and velocity, and then watch the system evolve over time.
The JavaPlanets program approaches the n-body problem with a "Particle-Particle" method. That is, the exact force between every pair of particles is calculated. This approach is fine for the type of simulations we are interested in. The particle-particle method basically reduces to the numerical solution of differential equations. More details of how this is done are provided in the next section. First, it is useful to consider some of the limitations of this approach and alternative techniques. The main disadvantage of particle-particle methods are that they become exceptionally expensive computationally as the number of particles grows. In a system of n particles, there are n(n-1)/2 different pairs of particles. Thus, the number of force calculations increases as the number of particles squared. That is, the method is O(n^2). For systems with large number of particles, many other approaches are possible. Each has its strengths and weakness. Some of the major methods are: Particle-Particle, Particle-Mesh, Particle-Particle/Particle-Mesh, Particle Multiple-Mesh, Nested Grid Particle-Mesh, Tree-Code (such as Barnes-Hut), Fast-Multipole-Method, Tree-Code Particle Mesh, Self-Consistent Field, and the Symplectic Method. A good general introduction to these methods can be found at http://www.amara.com/papers/nbody.html.
Many of these approaches are quite complex, but all try to make some kind of approximation to reduce the number of calculations required, while maintaining accuracy. All of these methods are directed almost entirely at modeling 1/r^2 forces. These forces are "nice" because the force between two particles is negligible when sufficient distance separates the particles.
This routine is repeated approximately 20-30 times per second when the simulation is running in its graphical mode. However, most of this time is taken up by drawing the screen, not numerical calculations.
8bodyspring.txt
file) using Euler's method, and after about 14,000 timesteps using the RK4 method. Even more interestingly, using half the default timestep, the breakup occurred after 24,000 iterations using the RK4 method. That is, in less simulation time than with the larger timestep. This counterintuitive result suggests that the disruption has to do with the number of calculations and hence the buildup of roundoff errors, not so much with the accuracy of the numerical methods.collinear.txt
sets up such a simulation. The RK4 method preserves the collinear property approximately 4800 iterations (using the default timestep), and the Euler method preserves it approximately 4100 iterations. Thus, this simulation does seem to demonstrate the superior accuracy of the RK4 method. The other thing to note about this error analysis is that it does not take into account computer time. My RK4 method is much slower than my Euler implementation -- much more so than necessary, probably. Hence, even though the RK4 method is more accurate for a given timestep, it is possible that a more accurate simulation could be produced in the same amount of time by simply using Euler's method with a smaller timestep. I did not investigate this idea because I had no good way to measure the time spent on computation as opposed to painting the screen or the thread sleeping.
My original plan was to incorporate the concept of a DES into my implementation, but I abandoned the idea because I did not see a good way to maintain the real-time display property that is important to the program. Dr. Conery suggested an extension of the basic DES idea that would have made this implementation feasible. The idea is to treat drawing events as events on the event queue, just like updates for the planets. At these fixed intervals, a "snapshot" of the system would be taken. This does not solve the real time issue. But, for systems with small number of bodies (the only type this simulation is real designed to handle) very little information is needed to render the screen. Thus, rather than drawing at each draw event, the current state can simply be pushed on a queue. The drawing thread can then take from this queue at regular intervals. The framerate and simulation parameters could then be adjusted to insure a steady framerate and realistic simulation, while still taking advantage of dynamically chosen time steps.