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/chinpokomon Jan 15 '20

Is that FMM?

I've been looking at doing a similar thing using quad-trees (2D and not 3D), for any region of space, the force vector between that and another region seems that it should only need to be calculated as a monopole. A quad-tree of the entire set could allow you find regions, but the tree wouldn't be built just to group masses, it would have a partitioning partly assisted by the distance away from a mass. Essentially each mass would have its own quad-tree representation of the space.

I think that this would improve things, but I didn't take it further yet because I don't see a good way for the tree to self-balance and every tree would need to rebalance after collisions, so I think I'm back to high complexity and O(n2).

I also considered just using a grid, so that I wouldn't have to do the rebalancing, but I've shifted gears and started looking at shaders now, thinking that I might be able to batch these calculations into something I can run on the GPU compute units in parallel.

2

u/Astrokiwi Jan 15 '20

You just rebuild the tree every time, because that's nlogn. You don't worry about balancing the tree, that's not the bottleneck.

What you do is for each particle, you propagate from the top of the tree downwards, until you find either leaf nodes, or cells that are smaller than some opening angle from the particle. It's one quad tree, you just don't open it all the way down for every particle.

People also do this with kdtrees if you want to try that too. But tree gravity is the default algorithm for big galaxy simulations etc.

1

u/chinpokomon Jan 15 '20

I assumed there was probably art for that technique, but I haven't explored it further than just thinking about how I might approach it.

1

u/[deleted] Jan 16 '20 edited Jan 16 '20

Interesting method, I'll try to implement it, but how do you make sure to not include the particle you want to calculate the force for in the tree? Wouldn't I have to re-calculate the tree for every particle, making the runtime N2 log N?

Do you choose theta so the particle can't be in an internal node and don't use the external node the particle is in

1

u/Astrokiwi Jan 16 '20

The opening angle criterion means that you go further down the tree for closer nodes. The particle's leaf node is always opened, and that means you can exclude it specifically without having to take into account that its mass is included in higher branches - you've already opened those nodes to get down to the leafs. The opening angle is basically cell-size/distance, and distance==0 for the cell you're in, so you're always bigger than the opening angle criterion.

Btw this is a very standard method, so there's lots of documentation on it, and lots of textbooks will spell it out better than I can in a reddit comment.

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.