r/Python • • Jan 14 '20

I made a gravity simulation https://github.com/phgilde/gravity_simulation

1.8k Upvotes

82 comments sorted by

View all comments

260

u/psharpep Jan 15 '20

Nice start here! I noticed you mentioned this sim took 3 hours to run - if you're interested in further improving this code, you can probably get 1000x faster performance on the same hardware. Consider looking into the following topics (you should be able to find more info on all of them with a Google search):

  • Vectorization. A specific example is getting rid of your for loop in simulate.py line 66 - this can be easily done with NumPy vectorization instead, which will make this much faster. Alternatively, you can at the very least give this a Numba @jit decorator by adding just a single line of code, which will move this for loop down to low-level code.

  • Better integration schemes. Your RK4 implementation is a great start! Adaptive RK4 schemes will be a lot faster, though, and symplectic schemes will be astronomically more accurate for an orbital dynamics simulation.

  • Fast Multipole Method interactions - this one's absolutely HUGE. Right now, your function to calculate acceleration due to gravity, a(x), is of computational complexity O(n2 ) - the time it takes to run is proportional to the number of particles squared. The fast multipole method ("FMM", often referred to as one of the top 10 most important algorithms of the 20th century), gives you an arbitrarily-precise solution to this problem that has complexity O(n log(n) ). This will literally get you a thousand-fold faster calculation right here alone.

  • Object-oriented methods. You have a ton of redundant calculations: for example, you recalculate the radius of each object at each timestep (simulate.py line 69), when you really only need to recalculate it after each collision - if there's no collision, the radius of the particle doesn't change.

Source: grad student whose research involves a lot of scientific computing

5

u/Astrokiwi Jan 15 '20

For gravity n-body simulations, it's more common to use the Barnes-Hut algorithm - I haven't looked into FMM but it seems closely related. Here you clump distant particles together using an oct-tree or quad-tree, but gravity for the clumped cell is just calculated as a monopole.

The other thing is a particle-particle particle-mesh method, where you bin masses onto a grid and do some Fourier transforms to work out the large-scale forces, and then add a small n2 sum to calculate short-range forces.

1

u/[deleted] Jan 16 '20

One more question: why is it inaccurate to use the center of mass and sum of mass of a group of bodies to calculate the force, compared to calculating the sum of the forces of each individual body?

2

u/Astrokiwi Jan 16 '20

Because gravity doesn't scale linearly with distance.

Gravitational acceleration is Gm/r2. A mass-weighted average of Gm/r2 isn't equal to the GM/<r>2, where <r> is the mass-weighted average of r.

For example, imagine three objects with the same mass, at a distance of r=1,r=2,r=3. What is the gravitational force that have on a test particle at r=0? (For simplicity, let G=m=1)

The full sum is 1/12+1/22+1/32 = 49/36 ≈ 1.36

The average distance would be (1+2+3)/3=2. So if you took the total mass (M=3) and the average distance, that's 3/22=3/4=0.75, which is very different!

On the other hand, imagine three objects at a distance of r=99,r=100,r=101. Then the full sum gives ≈0.00030006, but the radius-weighted centre-of-mass calculation gives 0.0003 exactly. So the approximation is very accurate in that limit.

Basically, force increases very rapidly as you get to small distances, so you're disproportionately dominated by nearby particles. So, while you can chunk things together into their centre-of-mass, this is only accurate for things that are close to each other and far away from you. For nearby objects, you're so sensitive to distance that you really need to do the full sum.