Deprecated: The each() function is deprecated. This message will be suppressed on further calls in /home/zhenxiangba/zhenxiangba.com/public_html/phproxy-improved-master/index.php on line 456 Dagstuhl Seminar 99171: The N-body Problem
Dagstuhl Seminar 99171, Case Study #2
The Barnes-Hut Method for the N-body Problem
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(n2) 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.)