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

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

How does precision influence the quality of the model?

-

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.

-
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. – Matt Knepley Dec 1 '11 at 13:20

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.

-

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.).

-

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)

-

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.

-
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. – Jed Brown Jan 14 '12 at 15:30
That's true. Although, as I stated earlier, this is an easy implementation, not necessarily an efficient one. – Paul Jan 14 '12 at 15:48
+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. – Stefano M Jan 30 '13 at 23:15

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

-
Could you add a little more detail as to why you recommend HACC and GADGET? – Paul Aug 28 '14 at 17:03
They are both high-profile cosmology codes that include gravity solvers. – Jeff Aug 28 '14 at 17:49