Computational Structure of the N-Body Problem
JACOB KATZENELSON · SIAM Journal on Scientific and Statistical Computing · 1989
This work considers tree algorithms for the N-body problem where the number of particles is on the order of a million. The main concern of this work is the organization and performance of these computations on parallel computers. This work introduces a formulation of the N-body problem as a set of recursive equations based on a few elementary functions. It is shown that both the algorithm of Barnes–Hut and that of Greengard–Rokhlin satisfy these equations using different elementary functions. The recursive formulation leads directly to a computational structure in the form of a pyramid-like graph, where each vertex is a process, and each arc a communication link. The pyramid is mapped to three different processor configurations: (1) a pyramid of processors corresponding to the processes pyramid graph; (2) a hypercube of processors, e.g., a connection-machine-like architecture; and (3) a rather small array, e.g., $2 \times 2 \times 2$, of processors faster than the ones considered in (1) and (2) above. The main conclusion is that simulations of this size can be performed on any of the three architectures in reasonable time. Approximately 24 seconds per timestep is the estimate for a million equally distributed particles using the Greengard-Rokhlin algorithm on the CM-2 connection machine. The smaller array of processors is quite competitive in performance.