N-Body problems inevitably come up when doing any most any kind of physical simulation work, particularly when particles are involved. N-Body problems appear whenever the particles in a system construct a field that in turn determines their dynamics. The classic examples are typically gravitational, but the n-body problem equally applies to electrostatic, electromagnetic, fluid dynamics, and even acoustic scattering problems. All can be formulated in essentially the same way just with different constants.
At first sight, n-body problems have a runtime complexity of O(N^2) since every particle interacts with every other particle. While this is not a big deal for small numbers of particles on the order of a few hundred, the amount of calculations required quickly exceeds what even the speediest of computers can handle. The challenge is to somehow reduce the complexity to something like O(N log N), which is actually tractable for millions or even billions of particles, making something like the Millenium Simulation Project possible.
Fortunately, there has been a lot of work done in this area since the late 80′s and 90′s for cosmological and electrostatic simulations, particularly by Greengard and Rokhlin. Together, they developed the Fast Multipole Method (FMM), which makes use of the math of complex analysis of harmonic functions to reformulate the n-body problem as O(N log N).
While this might sound complicated, the essential insight is straightforward and rather enlightening. The simplification the FMM is based on recognizes that the field a clusters of particles generates, when viewed from a certain distance, can be simplified to a single point that approximates the actual field. It’s akin to performing a simulation of the earth and sun where the mass of each body is taken to be at a point located the center of mass instead of spread out in space in a sphere.
The above images were generated using the FMM technique. The red points in the middle are the particles, each with an equal charge. The surface represents the potential generated by the points withe the coloring representing the phase. With one particle, there’s one cycle of a wave around the place. With 7 particles, there are more cycles as the waves generated by each particle interfere. The FMM approximation is akin to a spatial wavelet transform. This is the 2D case. In 3D, the FMM method uses spherical harmonics to approximate the potential.
While the above surfaces represent electrical potential, what we actually want is the electric field. The electric field gives the forces acting on the particles and is used to update the simulation. Fortunately, the electric field can be derived directly from the potential by taking its derivative. This works because we’re working with complex numbers. With purely real numbers, the phase information is missing, and the electric field cannot be determined without phase.
One useful way to think about simulations is in terms of Lagrangian and Eulerian paradigms. The Lagrangian perspective is essentially that of the particle. Information moves through space according to the dynamics involved. The Eulerian perspective is of a lattice or field, where fixed discrete points in space sample the dynamics.
In the case of the FMM, the n-body problem is simplified by converting the usual Lagrangian formulation into a hybrid Lagrangian-Eulerian algorithm where clusters of particles become instead waves in space. This conversion only holds a certain distance away from the cluster, so nearby particles must be treated in an purely Lagrangian manner.
This technique is of course not new. Spectral methods are used in all kinds of ways to quickly process point-wise spatial information, but such techniques have yet to be placed in the context of spatial composition where there is a continuum between field and particle. FMM lies at the boundary between the two, and it will be interesting to see how working with the diametrically opposed conceptualization of spatial information can be brought together in a rigorous yet intuitive manner.
References: