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

42

u/[deleted] Jan 15 '20

So I tried looking into fmm but didn't understand it really. Do you know some resources to get into it?