an N-body simulation

Drop a thousand stars into empty space, let gravity pull each one on every other, and watch what happens over a billion years. There is no closed formula for this — even three gravitating bodies have no general solution — so the only way to find out is to simulate it step by step. An N-body simulation does exactly that: it follows the motion of N particles that all interact, integrating their trajectories forward in time.

At its heart it is Newton again. Each particle feels a force that is the sum of the pulls from all the others, you compute that total force, update velocities and positions by a small time step (typically with a symplectic integrator like leapfrog, to conserve energy over long runs), and repeat. The naive cost is the catch: with N particles, summing every pairwise force is N times N work per step, which is hopeless for the billions of particles in a galaxy simulation. The field's great algorithmic ideas attack exactly this. Tree codes (the Barnes-Hut method) group distant clumps of particles and treat each clump as a single body, cutting the cost to about N log N. The fast multipole method pushes further to roughly linear, O(N), by expanding the far-field influence of whole groups into a few well-chosen terms. Particle-mesh methods spread the particles onto a grid and use an FFT-based fast Poisson solver to get the field.

N-body simulations built our modern picture of how galaxies, dark matter, and the cosmic web formed, and the same machinery models plasmas, star clusters, and even crowds and traffic. The honest caveat is that the fast methods are approximations with controllable error — you trade exact pairwise forces for a tunable accuracy parameter — and that close encounters between particles can demand tiny time steps or special treatment. The art is choosing approximations whose error you understand and can bound.