   n-body simulations
  I'm working on a galaxy/gravitational simulator.  I was thinking about using the fast multipole method, but I hear that it doesn't work well in a 3d space.  Has anyone else done something similar?  Also at the moment I'm using a brute force O(n^2) gravitational force calculation and I can only get around 500-1000 stars simulated with a smooth frame-rate.  Does that seem a bit low?   
  Lets make a rough estimation:Say you have a 3 Ghz machine (3 * 2^30 = 3221225472 instructions/sec) and want to have 30 frames per second.You have 1000 planets, so 1000 * 999 = 999000 pairs to calculate per frame.In total 29970000 pairs per second.Thus, 3221225472 / 29970000 = 107 instructions per pair.Well, this is a !!very!! rough estimation, but adding the general overhead per frame, it seems that a maximum of 1000 objects in real time is not that unlikely.Obviously, the FMM method and the Barnes-Hut method both perform worse in 3D than 2D, but I assume that they are both much better scalable in general than the brute force algorithm.   ;  It doesn't seem low, you probably can't get much higher than that. In the DirectX SDK there is a D3D10-sample called NBodyGravity that does this on the GPU with many more particles. If you can use the GPU for this it would probably let you have quite a few more stars.   ;  Just some wild idea... Find the center of gravity for all stars CoG_g, and store the total mass M_g. Next divide the domain into a grid, and assign each star to the grid cell it's in. When computing gravity, accumulate the gravitational force from the stars in the grid cells around the current star (say 3x3 cells). Also find the center of gravity CoG_l and total mass M_l for these neighboring stars.Next apply the force from the rest of the stars by first adjusting the global CoG by removing the contribution from the local CoG, ie CoG_mod = (M_g * CoG_g - M_l * CoG_l) / (M_g - M_l), then using the modified global CoG along with the adjusted glocal mass to find the force (ie approximating it as a point source).After each iteration update the grid cell info for each star.No idea if it'll work but might be worth a shot? Obviously if you loop over all stars by grid cell you can amortize the local CoG computations. An adaptive grid subdivision might also be a good idea.   ;Quote:Original post by dietepietYou have 1000 planets, so 1000 * 999 = 999000 pairs to calculate per frame.In total 29970000 pairs per second.If you have n planets, then you actually only have [n (n-1)]/2 force-pairs to compute, after you take symmetry into account.  Granted, that's still O(2).And... actually you need accelerations, not forces, so really that's not the number of force magnitudes to compute, but the number of inverse-square distances to compute.  So you could compute [n (n-1)]/2 inverse-square distances and, later, do n multiplies to compute accelerations.  This assumes that deferring the calculation and doing a lookup is faster than repeating the 3 MULS, 2 ADDS, and 1 divide, which isn't necessarily the case.-----Personally, though, I think that the Fast multipole method that dietepiet mentioned sounds more interesting:http://math.nyu.edu/faculty/greengar/shortcourse_fmm.pdf   ;  FMM is your best choice if you want to go much higher. The 'problems' with FMM in 3d space are mainly related to breaking up the tree, but they're primarily just hard to think about, and not limitations on the algorithm itself.   ;  If I recall correctly, the n-body problem is chaotic for n>2 and for 1/r^2 forces, so if you're actually trying to get real numbers (i.e., predict when we're going to get hit by a comet) you should be extremely careful.   