A cost optimal parallel algorithm for computing force field in \(N-\)body simulations on a CREW PRAM (Q5941086)

We consider the following force field computation problem: given a cluster of \(n\) particles in three-dimensional space, compute the force exerted on each particle by the other particles. Depending on different applications, the pairwise interaction could be either gravitational or Lennard-Jones. In both cases, the force between two particles vanishes as the distance between them approaches to infinity. Since there are \(n(n-1)/2\) pairs, direct method requires \(\Theta(n^{2})\) time for force evaluation, which is very expensive for astronomical simulations. In 1985 and 1986, two famous \(\Theta(n\log n)\) time hierarchical tree algorithms were published by \textit{A. W. Appel} [SIAM J. Sci. Statist. Comput. 6, 85-103 (1985)] and by \textit{J. Barnes} and \textit{P. Hut} [Nature 324, 446-449 (1980)], respectively. In a recent paper, we presented a linear time algorithm which builds the oct tree bottom-up and showed that Appel's algorithm can be implemented in \(\Theta(n)\) sequential time. In this paper, we present an algorithm which computes the force field in \(\Theta(\log n)\) time on a \(\Theta(n\log n)\) processor CREW PRAM. A key to this optimal parallel algorithm is replacing a recursive top-down force calculation procedure of Appel by an equivalent non-recursive bottom-up procedure. Our parallel algorithm also yields a new \(\Theta(n)\) time-sequential algorithm for force field computation.