The Calendar Queue and N-Body Simulation

by Mike Palmer

The N-Body problem is intrinsically O(n²) (there are n² gravitational interactions that must be computed). While polynomial time is normally acceptable in the world of computer science, when n becomes very large (greater than 1,000,000), polynomial time performance is clearly undesireable. Therefore, N-Body simulations often cluster astral bodies together and approximate the gravitational interactions that occur between the clusters. However, when the 'cluster' approximation method is used in simulations, error is introduced into the results produced. Therefore, some method must be used to limit the error.

The most common method used to limit the error is the Barnes-Hut method (or some comparable variant). If the error value associated with a cluster is too large, the Barnes-Hut method will open the cluster in order to reduce the error. The Barnes-Hut method determines whether or not to open a cluster based on local criterion. Therefore, the Barnes-Hut method has no concept of global error.

An alternate method which is used to bound the error uses a priority queue to keep track of the clusters with the largest error. The priority queue method opens the cluster's with the largest errors first, until the global error of all of the clusters is below some permissable value.

The Barnes-Hut method is the most common method used today because it takes constant time per operation when determining whether or not to open a cluster. Conversely, most priority queue's require O(log n) time per operation. Therefore, the time performance of the Barnes-Hut method often greatly exceeds that of most priority queue driven algorithms. However, the priority queue approach offers one distinct advantage to the Barnes-Hut method: the priorty queue method produces a very even error distribution which in turn makes the resulting data more consistent and reliable. My research objective was to determine if a special constant time per operation priority queue, called the calendar queue, could be used to improve the running time of the priority queue approach to N-Body simulations.

My results were as follows:

• Using a hybrid algorithm which combines elements of the Barnes-Hut and priority queue methods has favorable running time and a very even error distribution.
• The calendar queue needed to be greatly adapted in order to be used in the priority queue approach.

Advised by Richard Ladner

EE1 003
May 19, 1999
3:30 pm