28
$\begingroup$

How can the gravitational n-body problem be solved numerically in parallel?

Is precision-complexity tradeoff possible?

How does precision influence the quality of the model?

Improve this question
$\endgroup$
1
  • $\begingroup$ This paper describes possible implementations with OpenMP. $\endgroup$
    – Geremia
    Commented Aug 27, 2019 at 23:59

6 Answers 6

Reset to default
29
$\begingroup$

There is a wide variety of algorithms; Barnes Hut is a popular $\mathcal{O}(N \log N)$ method, and the Fast Multipole Method is a much more sophisticated $\mathcal{O}(N)$ alternative.

Both methods make use of a tree data structure where nodes essentially only interact with their nearest neighbors at each level of the tree; you can think of splitting the tree between the set of processes at a sufficient depth, and then having them cooperate only at the highest levels.

You can find a recent paper discussing FMM on petascale machines here.

Improve this answer
$\endgroup$
1
  • 2
    $\begingroup$ BH, also called a tree-code, seems to be preferable at low accuracy. Here is a paper where the methods are combined adaptively, but I have not seen this work in practice yet. $\endgroup$
    – Matt Knepley
    Commented Dec 1, 2011 at 13:20
14
$\begingroup$

Look at the fast multipole method. It is highly scalable and $O(n)$. It allows trading off between precision and cost. Here's an example where it is run at 42 Tflops on a GPU cluster.

Improve this answer
$\endgroup$
8
$\begingroup$

As an alternative source, you could also look at mesh-based Ewald-like methods. The genesis of the "particle mesh" methods (such as PPPM and smoothed particle mesh Ewald) lies in simulations of galaxies for astrophysics; the connection to charges was an unintentional side effect (that just happened to eventually overtake the original usage).

More recently, there has also been some literature on multilevel summation methods which are akin in spirit to fast multipole methods and the Barnes-Hut, but may offer advantages in different circumstances (more general and flexible geometries, some efficiency gains, etc.).

Improve this answer
$\endgroup$
8
$\begingroup$

For the classical gravitational n-body problem, I think the following two papers do a good job at discussing the guts of the parallel implementation for the force evaluation step. Although the papers discuss a GPU implementation, they do a good job at discussing the parallelism and provide details of the algorithms:

This paper by Nyland, Harris, and Prins presents the direct n-body algorithm in CUDA for GPUs.

This other paper by Yokota and Barba has a good discussion on of the treecode and fast multipole algorithm also in the context of GPU-computing

Your questions about the accuracy of n-body numerical simulations are a bit more involved and there are so many important details that an answer can spawn several books. I think the best think to do is to give you a couple of book references. I suggest:

Gravitational N-body Simulations by Sverre J. Aarseth

Computer simulations using particles by Hockney and Eastwood. (Sorry no pdf version)

Improve this answer
$\endgroup$
4
$\begingroup$

If you need a simple implementation approach which is not optimal in the asymptotic sense, you may want to consider using all-gather communication operations. Since each of the N-bodies needs to know the gravitational effect of the other bodies, it is important for every processor to know the entire dataset. This is what all-gather operations do. There is a good book: Parallel Programming in C with MPI and OPENMP by Michael J. Quinn (2004) which discusses exactly this topic on page 82. It might be worth looking at to give you a start.

Improve this answer
$\endgroup$
3
  • 3
    $\begingroup$ You are describing "direct summation" which is an $O(n^2)$ algorithm with huge communication volume, so it can only be recommended for extremely small problems. Since the interaction has structure, it is definitely not necessary for "every processor to know the entire dataset". Your suggestion is like recommending solving a sparse linear system with dense linear algebra or sorting using bubble sort. $\endgroup$
    – Jed Brown
    Commented Jan 14, 2012 at 15:30
  • $\begingroup$ That's true. Although, as I stated earlier, this is an easy implementation, not necessarily an efficient one. $\endgroup$
    – Paul
    Commented Jan 14, 2012 at 15:48
  • $\begingroup$ +1 somehow all other answer are assuming that the OP is looking for tera or petascale performance. FMM and akin make sense only opposed to more naive approaches. $\endgroup$
    – Stefano M
    Commented Jan 30, 2013 at 23:15
1
$\begingroup$

See Google Scholar and look for references to HACC and GADGET, among other codes.

Improve this answer
$\endgroup$
2
  • 2
    $\begingroup$ Could you add a little more detail as to why you recommend HACC and GADGET? $\endgroup$
    – Paul
    Commented Aug 28, 2014 at 17:03
  • 1
    $\begingroup$ They are both high-profile cosmology codes that include gravity solvers. $\endgroup$
    – Jeff Hammond
    Commented Aug 28, 2014 at 17:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.