Fast N-body Solvers

Fast N-body solvers are techniques that perform the force update in a lower complexity than the direct O(N2) method. In this project we focus on hierarchical tree methods which can perform the force update in O(NlogN) complexity. Tree codes are a collection of algorithms that approximate the solution to exact formulation by grouping particles and data that represent average quantities of these particles. In the algorithms, grouping the particles results in a spatial hierarchy that forms a tree data structure (the leaves are the particles and the nodes the appropriate average values). The force on a particular particle is then computed by searching the tree and using the interaction with the averaged values rather than the collective interaction with all the particles being averaged.Hierarchical methods exist in many formulations, the most well known are the Barnes and Hut method [4, 6] and the Fast Multipole Methods [5]. Within the astrophysical community the Barnes and Hut method is most widely used. Therefore we focus our attention first to this method. The original Barnes Hut method uses mono-pole approximations [4]. State-of-the-art codes apply quadrupole approximations [6].In 1991 Makino demonstrated how to run the original Barnes-Hut method on GRAPE-1A [9]. For this he used a vectorised version of the algorithm, due to Barnes [16]. The algorithm was also demonstrated on GRAPE-3 [10]. Here, a turnover between the Barnes-Hut and the direct algorithm (i.e. the point where Barnes-Hut becomes faster) was achieved for $N \sim 10^5$. From the literature and own experiments it is well known that if both algorithms run completely on the host, the turnover is already at $N \simeq 10^3$. This dramatically shows the host bottleneck which we propose to solve on our novel architecture.For collision-less N-body systems tree-codes with limited accuracy, such as the original Barnes-Hut method, are very well suited. However, for collisional systems much higher accuracy in needed. For this reason the GRAPE team e.g. run the direct method on the most powerful GRAPE system available to date. However, we also need to understand to what extent more accurate fast N-body solvers can benefit from smaller GRAPE systems, like the UvA N-body lab. Therefore we plan to study the possibilities of quadrupole Barnes-Hut, higher order Fast Multipole Methods, or accurate P3M methods on relative small and cheap systems like the UvA N-body lab. Because we plan this research in the second half of the project (see chapter 5) it is not yet clear which method we will consider. This depends on the one hand on needs from our target applications and on the other hand on the developments in the GRAPE project.

The direct N-body software is based on the Starlab software environment [17, 18]. Starlab is a software package for simulating the evolution of dense stellar systems and analyzing the resultant data. The main components of Starlab are the N-body integrator kira and the stellar and binary evolution program SeBa. The program is designed to take advantage of the ``GRAPE-4'' and ``GRAPE-6'' special-purpose processors [19]. The stellar evolution program currently uses parameterized tracks, which strongly limits its uses. Part of this project will be to attach a more realistic stellar evolution code to the N-body integrator and to extend this code to evolve binaries and higher order hierarchical systems.

The vast data output of these simulations, measured in hundreds of Tera bytes for a single run, demands novel forms of exploring the data. One way of analyzing the data is by using the CAVE [23], the 3D virtual reality environment available at the SARA supercomputer center of the UvA. The most striking novel feature of this type of analysis is the ability to simultaneously visualize local and global characteristics of the complex interacting system of stars.