8
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Welcome to SciComp.SE. Your visualization looks great, BTW. What you are describing does not seem as an optimization technique but more like a no-so-brute-force solver for the n body problem. Maybe related to the Fast multipole method. $\endgroup$ – nicoguaro Jan 28 '16 at 22:55
6
$\begingroup$

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}}$.

$\endgroup$
  • $\begingroup$ Very cool! Sounds about correct.. although I think the gain in computational speed can be significantly higher if you accept a high level of inaccuracy, which can be ok if the simulation, like in my case, is mostly for visual effect and not for scientific purposes. $\endgroup$ – Magnus Wolffelt Jan 29 '16 at 23:14
  • $\begingroup$ Yes, you can always trade accuracy for speed. However the method will never scale asymptotically better, i.e. you will never get to $O(N)$ complexity with this scheme. You can combine the method with Bernes-Hut though, if you need/want more particles, or if you want to challenge yourself, implement the fast multipole method that nicoguaro mentioned. $\endgroup$ – LKlevin Feb 1 '16 at 7:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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