N-body simulation optimisation, looking for name or existing work

Question

during the development of my N-body simulation with visualisation in WebGL, I devised an optimisation, and I'm wondering if it has a name. I find it unlikely that it has never been done before.

It works like this: During the first timestep, make an all-pairs iteration. During that iteration, for each particle:

1. Store all the close interactions in a list - representing all the particles that are close to this one. These interactions will from then on be evaluated each time step. This list would typically contain a handful of entries.
2. Iterate on all the other particles and calculate a net far force that you store with the particle. This net force is thus remembered between timesteps and continuously applied to the particle.

Then as the simulation continues past its first timestep, in a round-robin fashion, each timestep update a small number of particles' lists of close interactions and net far forces. So that over a certain number of time steps - say, 1000, all the particles' close interactions and net far forces will have been updated. The ones that you don't update will just check their close interactions and apply the net far force. In this example, the computational complexity of each time step is something like $N^2 / 1000$ instead of $N^2$.

A trick to also making this reasonably accurate is to better identify "close interactions". Sometimes proximity is not the best indicator - you could also consider mass and relative velocity and so on. "Most significant interactions" might be a better word. Or "most-likely-to change-soon-interactions".

This optimisation allows for a lot more interacting particles than the all-pairs method, but I'm not sure how to describe it in O() terms, as it does not make a complete solution each timestep, but reuses (slightly incorrect) old information and spreads out the computational effort over time.

(Disclaimer: My webgl simulation also has "vfx" particles that only get affected by gravity and don't reciprocate the effect, so it's not as awesomely fast as it might appear)

So does this optimisation technique have a name?

Answer 1

The method you describe is somewhat similar to the Barnes-Hut algorithm. The main difference is that you have a single level of close interactions, whereas the Barnes-Hut has $\log N$.

In the Barnes-Hut, all particles are put into an octree, and the gravitational force computed between the elements every node. Computational complexity then drops to $O(N \log N)$.

EDIT:

Turns out what you're proposing does have a name: the Ahmad-Cohen scheme. The gain in computational speed is $(N/3.8)^{\frac{1}{4}}$.