Saturday, 15 May 2010

Attempt at "fast" solution to the N-Body Problem

The N-Body  problem is a very interesting problem both mathematically and in real world applications such as in observational cosmology. The basic idea of the N-Body Problem is, given N gravitationally interacting bodies, what is the most efficient way to solve the subsequent motions of all of the bodies given some initial conditions? I will be looking at the problem in 2 dimensions.

Lets first take a look at the example in its simplest form, with just two bodies. The two bodies pull on each other by the gravitational force, which causes both to accelerate along a vector pointed along the line joining them. This is a very simple problem to solve and any university level physicist should find solving it trivial. In the case of more bodies however, an analytical solution becomes extremely complicated and far beyond the reach of my mathematical understanding; but what I do understand is computers and iterative techniques. The simplest way therefore to solve a problem with more than two bodies would be simply to summate the forces of all the bodies acting on one body at a given moment in time and update its velocity, then repeat this for each of the other bodies in your system.

Obviously for a number of bodies N, the number of force checks that would have to be done would increase very quickly, in fact at a rate N*N, which means for 1000 bodies, 1 million checks would have to be carried out, remember this is per instant in time.

I propose a solution that uses the bitmap functionality in flash, along with the blur filter. I am sure that it won't stand up to rigorous mathematical scrutiny, but from an aesthetic standpoint, it does the job near enough ok.

The idea is that each body is represented by a pixel, with a colour related to its mass. By applying a blur filter on the bitmap, the gravitational field of the pixel is extended into the surrounding region. A brighter region means more gravitational force, and a darker region less. To solve the problem particles simply need to be accelerated along the line of highest gradient towards brighter regions. This way only N checks have to be carried out massively decreasing computing time.

For example carrying out the test with 10,000 particles, which would otherwise kill my computer (at 24 frames per second that would be 2,400,000,000 force checks per second!) it actual runs reasonably well!

Anyway take a look and feel free to make suggestions to improve the model. Just click the first image to launch the simulation!

Note: Limitations of the simulation include -

  • Blur is not complete, i.e gravity has a limited range - this may be analogous to simulations of the large scale universe where distances are two large for information to pass between.
  • Blur takes multiple steps to update (slow information rate)
  • Singularities such as collisions cause erratic behaviour (sudden velocity boosts)
Further Note: "Universe" has periodic boundary conditions, i.e X = X + Width & Y = Y + Height

Update: Running the simulation with more particles (100,000) without periodic boundary conditions yields interesting results. As expected the "universe" collapses in on its centre of mass. In this simulation I increased the blur distance, i.e the range of gravity, producing less local effects. The second image shows the simulation after it reaches a stable state with a large central mass.

No comments:

Post a Comment