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