Fast multi-body gravity algorithm?

Question

I am writing a program to simulate an n-body gravity system, whose precision is arbitrarily good depending on how small a step of "time" I take between each step. Right now, it runs very quickly for up to 500 bodies, but after that it gets very slow since it has to run through an algorithm determining the force applied between each pair of bodies for every iteration. This is of complexity n(n+1)/2 = O(n^2), so it's not surprising that it gets very bad very quickly. I guess the most costly operation is that I determine the distance between each pair by taking a square root. So, in pseudo code, this is how my algorithm currently runs:

for (i = 1 to number of bodies - 1) {
  for (j = i to number of bodies) {
   (determining the force between the two objects i and j,
    whose most costly operation is a square root)
  }
}

So, is there any way I can optimize this? Any fancy algorithms to reuse the distances used in past iterations with fast modification? Are there any lossy ways to reduce this problem? Perhaps by ignoring the relationships between objects whose x or y coordinates (it's in 2 dimensions) exceed a certain amount, as determined by the product of their masses? Sorry if it sounds like I'm rambling, but is there anything I could do to make this faster? I would prefer to keep it arbitrarily precise, but if there are solutions that can reduce the complexity of this problem at the cost of a bit of precision, I'd be interested to hear it.

Thanks.

Answer 1

Take a look at this question. You can divide your objects into a grid, and use the fact that many faraway objects can be treated as a single object for a good approximation. The mass of a cell is equal to the sum of the masses of the objects it contains. The centre of mass of a cell can be treated as the centre of the cell itself, or more accurately the barycenter of the objects it contains. In the average case, I think this gives you O(n log n) performance, rather than O(n²), because you still need to calculate the force of gravity on each of n objects, but each object only interacts individually with those nearby.

Assuming you’re calculating the distance with r² = x² + y², and then calculating the force with F = Gm₁m₂ / r², you don’t need to perform a square root at all. If you do need the actual distance, you can use a fast inverse square root. You could also used fixed-point arithmetic.

Answer 2

One good lossy approach would be to run a clustering algorithm to cluster the bodies together.

There are some clustering algorithms that are fairly fast, and the trick will be to not run the clustering algorithm every tick. Instead run it every C ticks (C>1).

Then for each cluster, calculate the forces between all bodies in the cluster, and then for each cluster calculate the forces between the clusters.

This will be lossy but I think it is a good approach.

You'll have to fiddle with:

• which clustering algorithm to use: Some are faster, some are more accurate. Some are deterministic, some are not.
• how often to run the clustering algorithm: running it less will be faster, running it more will be more accurate.
• how small/large to make the clusters: most clustering algorithms allow you some input on the size of the clusters. The larger you allow the clusters to be, the faster but less accurate the output will be.

So it's going to be a game of speed vs accuracy, but at least this way you will be able to sacrafice a bit of accuracy for some speed gains - with your current approach there's nothing you can really tweak at all.