In an nbody gravity simulation, instead of doing exact(all-pair brute force) solution, I added masses of each body into cells of a 3D grid(each cell is just a float value having a mass value). Then smoothed the grid using a stencil. Now I'm trying to get an approximation of point masses for point masses, from grid. I have already tried directly doing body-cell interaction(similar to body-body but using smoothed mass of cell and center position of cell) but this selects originally non-mass containing cells as if they are attracting and leads to high errors.

What could be the most precise(or logical) way to do one of below options:

  • a unit mass at an approximated position
  • an approximated mass at a unit distance and angle
  • approximation of both mass and distance

so that long-range component of total force properly acts same as all-pair brute-force version(long-range part of it)?

Or, what could be a proper way other than upper options? Can I use derivate of mass density(by neighboring cells) for these?

For now I'm calculating only an RMS error between all pair(but only long range part) version and this center-of-cell with smoothed mass (only with closest neighbor cells after long range distance(which equals 2*cell size)) to check how close the simulation is to all-pair version.

I'm doing this grid smoothing because I want to learn multigrid acceleration for nbody. To learn it step by step (and to do a performance comparison against later), only using a single grid with simple smoothing(16x16x16 cubes(as grid size) and 16 smoothing steps with 26 closest neighbor cells(using successive over relaxation ).

Initially both versions start in a cube volume.(Total particles are just 3072)

enter image description here

then at each timestep, rms of error of all body positions between two versions is calculated.

enter image description here

Addition of point masses to cells are done very simply as


1 Answer 1


It seems like you are inventing Barnes-Hut-type algorithm, which is a fundamental accelerated algorithm for n-body simulations. It follows a similar logic: you combine masses on a grid. But, it is done in a more elaborate fashion:

  • when particles are close, you still use direct calculations (no combination), otherwise, you would lose accuracy.
  • multipole expansions (center of mass) are used on an octree (in 3D) to accelerate distant interactions.

Since there are many more distant interactions when you handle your particles in a tree-fashion, this leads to the complexity reduction: $\mathcal O(N\log N)$ vs $\mathcal O(N^2)$ for direct computation.


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.