The Barnes-Hut Method for the

N-body Problem

**Coordinators:
Jan Prins &
Manuel
Chakravarty**

Given a self-gravitating system consisting of *n* distinct
particles characterized by their mass, initial position, and velocity,
the problem is to compute the force on each particle that is induced by
the other particles.

A direct force calculation would require the computation of
O(*n*^{2}) interactions, a large amount of work for
particle systems encountered in practice. There exist a variety of
methods that compute approximations to the exact solution with
reasonable accuracy and with an improved asymptotic complexity
[4].

We provide the following resources concerning the problem:

- We provide a brief problem description illustrating the Barnes-Hut hierarchical force-calculation algorithm, which we proposed as a case study; furthermore, the slides of Jan Prins' presentation (in PDF format) a give more detailed, illustrated introduction to the problem. The irregular, input-dependent computation and communication structure as well as the practical relevance of the algorithm make it an interesting object of research.
- This reference code is a sequential implementation of the algorithm in Haskell, which hopefully assists you in understanding the details and should be useful for debugging your implementation and generating particle tests. (If you did not use Haskell so far, you may be interested in implementations of the language for executing the code.)

Last modified: Tue Oct 19 16:19:31 JST 1999