N-body simulation

From Wikipedia, the free encyclopedia

https://en.wikipedia.org/wiki/N-body_simulation

 

An N-body simulation of the cosmological formation of a cluster of galaxies in an expanding universe.

 

In physics and astronomy, an N-body simulation is a simulation of a dynamical system of particles, usually under the influence of physical forces, such as gravity (see n-body problem). N-body simulations are widely used tools in astrophysics, from investigating the dynamics of few-body systems like the Earth-Moon-Sun system to understanding the evolution of the large-scale structure of the universe. In physical cosmology, N-body simulations are used to study processes of non-linear structure formation such as galaxy filaments and galaxy halos from the influence of dark matter. Direct N-body simulations are used to study the dynamical evolution of star clusters. 

Nature of the particles

The 'particles' treated by the simulation may or may not correspond to physical objects which are particulate in nature. For example, an N-body simulation of a star cluster might have a particle per star, so each particle has some physical significance. On the other hand, a simulation of a gas cloud cannot afford to have a particle for each atom or molecule of gas as this would require on the order of 10²³ particles for each mole of material (see Avogadro constant), so a single 'particle' would represent some much larger quantity of gas (often implemented using Smoothed Particle Hydrodynamics). This quantity need not have any physical significance, but must be chosen as a compromise between accuracy and manageable computer requirements. 

Direct gravitational N-body simulations

In direct gravitational N-body simulations, the equations of motion of a system of N particles under the influence of their mutual gravitational forces are integrated numerically without any simplifying approximations. These calculations are used in situations where interactions between individual objects, such as stars or planets, are important to the evolution of the system. 

The first direct N-body simulations were carried out by Erik Holmberg at the Lund Observatory in 1941, determining the forces between stars in encountering galaxies via the mathematical equivalence between light propagation and gravitational interaction: putting light bulbs at the positions of the stars and measuring the directional light fluxes at the positions of the stars by a photo cell, the equations of motion can be integrated with ${\displaystyle O(N)}$ effort. The first purely calculational simulations were then done by Sebastian von Hoerner at the Astronomisches Rechen-Institut in Heidelberg, Germany. Sverre Aarseth at the University of Cambridge (UK) has dedicated his entire scientific life to the development of a series of highly efficient N-body codes for astrophysical applications which use adaptive (hierarchical) time steps, an Ahmad-Cohen neighbour scheme and regularization of close encounters. Regularization is a mathematical trick to remove the singularity in the Newtonian law of gravitation for two particles which approach each other arbitrarily close. Sverre Aarseth's codes are used to study the dynamics of star clusters, planetary systems and galactic nuclei.

General relativity simulations

Many simulations are large enough that the effects of general relativity in establishing a Friedmann-Lemaitre-Robertson-Walker cosmology are significant. This is incorporated in the simulation as an evolving measure of distance (or scale factor) in a comoving coordinate system, which causes the particles to slow in comoving coordinates (as well as due to the redshifting of their physical energy). However, the contributions of general relativity and the finite speed of gravity can otherwise be ignored, as typical dynamical timescales are long compared to the light crossing time for the simulation, and the space-time curvature induced by the particles and the particle velocities are small. The boundary conditions of these cosmological simulations are usually periodic (or toroidal), so that one edge of the simulation volume matches up with the opposite edge.

Calculation optimizations

N-body simulations are simple in principle, because they involve merely integrating the 6N ordinary differential equations defining the particle motions in Newtonian gravity. In practice, the number N of particles involved is usually very large (typical simulations include many millions, the Millennium simulation included ten billion) and the number of particle-particle interactions needing to be computed increases on the order of N², and so direct integration of the differential equations can be prohibitively computationally expensive. Therefore, a number of refinements are commonly used. 

Numerical integration is usually performed over small timesteps using a method such as leapfrog integration. However all numerical integration leads to errors. Smaller steps give lower errors but run more slowly. Leapfrog integration is roughly 2nd order on the timestep, other integrators such as Runge–Kutta methods can have 4th order accuracy or much higher. 

One of the simplest refinements is that each particle carries with it its own timestep variable, so that particles with widely different dynamical times don't all have to be evolved forward at the rate of that with the shortest time. 

There are two basic approximation schemes to decrease the computational time for such simulations. These can reduce the computational complexity to O(N log N) or better, at the loss of accuracy. 

Tree methods

In tree methods, such as a Barnes–Hut simulation, an octree is usually used to divide the volume into cubic cells and only interactions between particles from nearby cells need to be treated individually; particles in distant cells can be treated collectively as a single large particle centered at the distant cell's center of mass (or as a low-order multipole expansion). This can dramatically reduce the number of particle pair interactions that must be computed. To prevent the simulation from becoming swamped by computing particle-particle interactions, the cells must be refined to smaller cells in denser parts of the simulation which contain many particles per cell. For simulations where particles are not evenly distributed, the well-separated pair decomposition methods of Callahan and Kosaraju yield optimal O(n log n) time per iteration with fixed dimension. 

Particle mesh method

Another possibility is the particle mesh method in which space is discretised on a mesh and, for the purposes of computing the gravitational potential, particles are assumed to be divided between the nearby vertices of the mesh. Finding the potential energy Φ is easy, because the Poisson equation

${\displaystyle \nabla ^{2}\Phi =4\pi G{\rho },\,}$

where G is Newton's constant and ${\displaystyle {\rho }}$ is the density (number of particles at the mesh points), is trivial to solve by using the fast Fourier transform to go to the frequency domain where the Poisson equation has the simple form

${\displaystyle {\hat {\Phi }}=-4\pi G{\frac {\hat {\rho }}{k^{2}}},\,}$

where ${\displaystyle {\vec {k}}}$ is the comoving wavenumber and the hats denote Fourier transforms. The gravitational field can now be found by multiplying by ${\displaystyle {\vec {k}}}$ and computing the inverse Fourier transform (or computing the inverse transform and then using some other method). Since this method is limited by the mesh size, in practice a smaller mesh or some other technique (such as combining with a tree or simple particle-particle algorithm) is used to compute the small-scale forces. Sometimes an adaptive mesh is used, in which the mesh cells are much smaller in the denser regions of the simulation. 

Special-case optimizations

Several different gravitational perturbation algorithms are used to get fairly accurate estimates of the path of objects in the solar system.

People often decide to put a satellite in a frozen orbit. The path of a satellite closely orbiting the Earth can be accurately modeled starting from the 2-body elliptical orbit around the center of the Earth, and adding small corrections due to the oblateness of the Earth, gravitational attraction of the Sun and Moon, atmospheric drag, etc. It is possible to find a frozen orbit without calculating the actual path of the satellite.

The path of a small planet, comet, or long-range spacecraft can often be accurately modeled starting from the 2-body elliptical orbit around the sun, and adding small corrections from the gravitational attraction of the larger planets in their known orbits.

Some characteristics of the long-term paths of a system of particles can be calculated directly. The actual path of any particular particle does not need to be calculated as an intermediate step. Such characteristics include Lyapunov stability, Lyapunov time, various measurements from ergodic theory, etc. 

Two-particle systems

Although there are millions or billions of particles in typical simulations, they typically correspond to a real particle with a very large mass, typically 10⁹ solar masses. This can introduce problems with short-range interactions between the particles such as the formation of two-particle binary systems. As the particles are meant to represent large numbers of dark matter particles or groups of stars, these binaries are unphysical. To prevent this, a softened Newtonian force law is used, which does not diverge as the inverse-square radius at short distances. Most simulations implement this quite naturally by running the simulations on cells of finite size. It is important to implement the discretization procedure in such a way that particles always exert a vanishing force on themselves.

Incorporating baryons, leptons and photons into simulations

Many simulations simulate only cold dark matter, and thus include only the gravitational force. Incorporating baryons, leptons and photons into the simulations dramatically increases their complexity and often radical simplifications of the underlying physics must be made. However, this is an extremely important area and many modern simulations are now trying to understand processes that occur during galaxy formation which could account for galaxy bias. 

Computational complexity

Reif et al. prove that if the n-body reachability problem is defined as follows – given n bodies satisfying a fixed electrostatic potential law, determining if a body reaches a destination ball in a given time bound where we require a poly(n) bits of accuracy and the target time is poly(n) is in PSPACE. 

On the other hand, if the question is whether the body eventually reaches the destination ball, the problem is PSPACE-hard. These bounds are based on similar complexity bounds obtained for ray tracing.

Three-body problem

From Wikipedia, the free encyclopedia

https://en.wikipedia.org/wiki/Three-body_problem 

Approximate trajectories of three identical bodies located at the vertices of a scalene triangle and having zero initial velocities. It is seen that the center of mass, in accordance with the law of conservation of momentum, remains in place.

 

In physics and classical mechanics, the three-body problem is the problem of taking the initial positions and velocities (or momenta) of three point masses and solving for their subsequent motion according to Newton's laws of motion and Newton's law of universal gravitation. The three-body problem is a special case of the n-body problem. Unlike two-body problems, no general closed-form solution exists, as the resulting dynamical system is chaotic for most initial conditions, and numerical methods are generally required.

Historically, the first specific three-body problem to receive extended study was the one involving the Moon, the Earth, and the Sun. In an extended modern sense, a three-body problem is any problem in classical mechanics or quantum mechanics that models the motion of three particles.

Mathematical description

The mathematical statement of the three-body problem can be given in terms of the Newtonian equations of motion for vector positions ${\displaystyle \mathbf {r_{i}} =(x_{i},y_{i},z_{i})}$ of three gravitationally interacting bodies with masses ${\displaystyle m_{i}}$:

${\displaystyle {\begin{aligned}{\ddot {\mathbf {r} }}_{\mathbf {1} }&=-Gm_{2}{\frac {\mathbf {r_{1}} -\mathbf {r_{2}} }{|\mathbf {r_{1}} -\mathbf {r_{2}} |^{3}}}-Gm_{3}{\frac {\mathbf {r_{1}} -\mathbf {r_{3}} }{|\mathbf {r_{1}} -\mathbf {r_{3}} |^{3}}},\\{\ddot {\mathbf {r} }}_{\mathbf {2} }&=-Gm_{3}{\frac {\mathbf {r_{2}} -\mathbf {r_{3}} }{|\mathbf {r_{2}} -\mathbf {r_{3}} |^{3}}}-Gm_{1}{\frac {\mathbf {r_{2}} -\mathbf {r_{1}} }{|\mathbf {r_{2}} -\mathbf {r_{1}} |^{3}}},\\{\ddot {\mathbf {r} }}_{\mathbf {3} }&=-Gm_{1}{\frac {\mathbf {r_{3}} -\mathbf {r_{1}} }{|\mathbf {r_{3}} -\mathbf {r_{1}} |^{3}}}-Gm_{2}{\frac {\mathbf {r_{3}} -\mathbf {r_{2}} }{|\mathbf {r_{3}} -\mathbf {r_{2}} |^{3}}}.\end{aligned}}}$

where ${\displaystyle G}$ is the gravitational constant. This is a set of 9 second-order differential equations. The problem can also be stated equivalently in the Hamiltonian formalism, in which case it is described by a set of 18 first-order differential equations, one for each component of the positions ${\displaystyle \mathbf {r_{i}} }$ and momenta ${\displaystyle \mathbf {p_{i}} }$:

${\displaystyle {\frac {d\mathbf {r_{i}} }{dt}}={\frac {\partial {\mathcal {H}}}{\partial \mathbf {p_{i}} }},\qquad {\frac {d\mathbf {p_{i}} }{dt}}=-{\frac {\partial {\mathcal {H}}}{\partial \mathbf {r_{i}} }},}$

where ${\displaystyle {\mathcal {H}}}$ is the Hamiltonian:

${\displaystyle {\mathcal {H}}=-{\frac {Gm_{1}m_{2}}{|\mathbf {r_{1}} -\mathbf {r_{2}} |}}-{\frac {Gm_{2}m_{3}}{|\mathbf {r_{3}} -\mathbf {r_{2}} |}}-{\frac {Gm_{3}m_{1}}{|\mathbf {r_{3}} -\mathbf {r_{1}} |}}+{\frac {\mathbf {p_{1}} ^{2}}{2m_{1}}}+{\frac {\mathbf {p_{2}} ^{2}}{2m_{2}}}+{\frac {\mathbf {p_{3}} ^{2}}{2m_{3}}}.}$

In this case ${\displaystyle {\mathcal {H}}}$ is simply the total energy of the system, gravitational plus kinetic.

Restricted three-body problem

The circular restricted three-body problem is a valid approximation of elliptical orbits found in the Solar System, and this can be visualized as a combination of the potentials due to the gravity of the two primary bodies along with the centrifugal effect from their rotation (Coriolis effects are dynamic and not shown). The Lagrange points can then be seen as the five places where the gradient on the resultant surface is zero (shown as blue lines), indicating that the forces are in balance there.

 

In the restricted three-body problem, a body of negligible mass (the "planetoid") moves under the influence of two massive bodies. Having negligible mass, the planetoid exerts no force on the two massive bodies, which can therefore be described in terms of a two-body motion. Usually this two-body motion is taken to consist of circular orbits around the center of mass, and the planetoid is assumed to move in the plane defined by the circular orbits. 

The restricted three-body problem is easier to analyze theoretically than the full problem. It is of practical interest as well since it accurately describes many real-world problems, the most important example being the Earth-Moon-Sun system. For these reasons, it has occupied an important role in the historical development of the three-body problem.

Mathematically, the problem is stated as follows. Let ${\displaystyle m_{1,2}}$ be the masses of the two massive bodies, with (planar) coordinates ${\displaystyle (x_{1},y_{1})}$ and ${\displaystyle (x_{2},y_{2})}$, and let ${\displaystyle (x,y)}$ be the coordinates of the planetoid. For simplicity, choose units such that the distance between the two massive bodies, as well as the gravitational constant, are both equal to ${\displaystyle 1}$. Then, the motion of the planetoid is given by

${\displaystyle {\begin{aligned}{\frac {d^{2}x}{dt^{2}}}=-m_{1}{\frac {x-x_{1}}{r_{1}^{3}}}-m_{2}{\frac {x-x_{2}}{r_{2}^{3}}}\\{\frac {d^{2}y}{dt^{2}}}=-m_{1}{\frac {y-y_{1}}{r_{1}^{3}}}-m_{2}{\frac {y-y_{2}}{r_{2}^{3}}},\end{aligned}}}$

where ${\displaystyle r_{i}={\sqrt {(x-x_{i})^{2}+(y-y_{i})^{2}}}}$. In this form the equations of motion carry an explicit time dependence through the coordinates ${\displaystyle x_{i}(t),y_{i}(t)}$. However, this time dependence can be removed through a transformation to a rotating reference frame, which is an important simplification in any subsequent analysis.

Solutions

General solution

There is no general analytical solution to the three-body problem given by simple algebraic expressions and integrals. Moreover, the motion of three bodies is generally non-repeating, except in special cases.

On the other hand, in 1912 the Finnish mathematician Karl Fritiof Sundman proved that there exists a series solution in powers of t^1/3 for the 3-body problem. This series converges for all real t, except for initial conditions corresponding to zero angular momentum. (In practice the latter restriction is insignificant since such initial conditions are rare, having Lebesgue measure zero.)

An important issue in proving this result is the fact that the radius of convergence for this series is determined by the distance to the nearest singularity. Therefore, it is necessary to study the possible singularities of the 3-body problems. As it will be briefly discussed below, the only singularities in the 3-body problem are binary collisions (collisions between two particles at an instant) and triple collisions (collisions between three particles at an instant).

Collisions, whether binary or triple (in fact, any number), are somewhat improbable, since it has been shown that they correspond to a set of initial conditions of measure zero. However, there is no criterion known to be put on the initial state in order to avoid collisions for the corresponding solution. So Sundman's strategy consisted of the following steps:

1. Using an appropriate change of variables to continue analyzing the solution beyond the binary collision, in a process known as regularization.
2. Proving that triple collisions only occur when the angular momentum L vanishes. By restricting the initial data to L ≠ 0, he removed all real singularities from the transformed equations for the 3-body problem.
3. Showing that if L ≠ 0, then not only can there be no triple collision, but the system is strictly bounded away from a triple collision. This implies, by using Cauchy's existence theorem for differential equations, that there are no complex singularities in a strip (depending on the value of L) in the complex plane centered around the real axis (shades of Kovalevskaya).
4. Find a conformal transformation that maps this strip into the unit disc. For example, if s = t^1/3 (the new variable after the regularization) and if |ln s| ≤ β, then this map is given by

${\displaystyle \sigma ={\frac {e^{\frac {\pi s}{2\beta }}-1}{e^{\frac {\pi s}{2\beta }}+1}}.}$

This finishes the proof of Sundman's theorem. 

Unfortunately, the corresponding series converges very slowly. That is, obtaining a value of meaningful precision requires so many terms that this solution is of little practical use. Indeed, in 1930, David Beloriszky calculated that if Sundman's series were to be used for astronomical observations, then the computations would involve at least 10^8000000 terms.

Special-case solutions

In 1767, Leonhard Euler found three families of periodic solutions in which the three masses are collinear at each instant.

In 1772, Lagrange found a family of solutions in which the three masses form an equilateral triangle at each instant. Together with Euler's collinear solutions, these solutions form the central configurations for the three-body problem. These solutions are valid for any mass ratios, and the masses move on Keplerian ellipses. These four families are the only known solutions for which there are explicit analytic formulae. In the special case of the circular restricted three-body problem, these solutions, viewed in a frame rotating with the primaries, become points which are referred to as L₁, L₂, L₃, L₄, and L₅, and called Lagrangian points, with L₄ and L₅ being symmetric instances of Lagrange's solution.

In work summarized in 1892–1899, Henri Poincaré established the existence of an infinite number of periodic solutions to the restricted three-body problem, together with techniques for continuing these solutions into the general three-body problem. 

In 1893, Meissel stated what is now called the Pythagorean three-body problem: three masses in the ratio 3:4:5 are placed at rest at the vertices of a 3:4:5 right triangle. Burrau further investigated this problem in 1913. In 1967 Victor Szebehely and C. Frederick Peters established eventual escape for this problem using numerical integration, while at the same time finding a nearby periodic solution.

In the 1970s, Michel Hénon and Roger A. Broucke each found a set of solutions that form part of the same family of solutions: the Broucke–Henon–Hadjidemetriou family. In this family the three objects all have the same mass and can exhibit both retrograde and direct forms. In some of Broucke's solutions two of the bodies follow the same path.

An animation of the figure-8 solution to the three-body problem over a single period T ≃ 6.3259.

 

In 1993, a zero angular momentum solution with three equal masses moving around a figure-eight shape was discovered numerically by physicist Cris Moore at the Santa Fe Institute. Its formal existence was later proved in 2000 by mathematicians Alain Chenciner and Richard Montgomery. The solution has been shown numerically to be stable for small perturbations of the mass and orbital parameters, which raises the intriguing possibility that such orbits could be observed in the physical universe. However, it has been argued that this occurrence is unlikely since the domain of stability is small. For instance, the probability of a binary-binary scattering event resulting in a figure-8 orbit has been estimated to be a small fraction of 1%.

In 2013, physicists Milovan Šuvakov and Veljko Dmitrašinović at the Institute of Physics in Belgrade discovered 13 new families of solutions for the equal-mass zero-angular-momentum three-body problem.

In 2015, physicist Ana Hudomal discovered 14 new families of solutions for the equal-mass zero-angular-momentum three-body problem.

In 2017, researchers Xiaoming Li and Shijun Liao found 669 new periodic orbits of the equal-mass zero-angular-momentum three-body problem. This was followed in 2018 by an additional 1223 new solutions for a zero-momentum system of unequal masses.

In 2018, Li and Liao reported 234 solutions to the unequal-mass "free-fall" three body problem. The free fall formulation of the three body problem starts with all three bodies at rest. Because of this, the masses in a free-fall configuration do not orbit in a closed "loop", but travel forwards and backwards along an open "track". 

Numerical approaches

Using a computer, the problem may be solved to arbitrarily high precision using numerical integration although high precision requires a large amount of CPU time. In 2019, Breen et al. announced a fast neural network solver, trained using a numerical integrator.

History

The gravitational problem of three bodies in its traditional sense dates in substance from 1687, when Isaac Newton published his "Principia" (Philosophiæ Naturalis Principia Mathematica). In Proposition 66 of Book 1 of the "Principia", and its 22 Corollaries, Newton took the first steps in the definition and study of the problem of the movements of three massive bodies subject to their mutually perturbing gravitational attractions. In Propositions 25 to 35 of Book 3, Newton also took the first steps in applying his results of Proposition 66 to the lunar theory, the motion of the Moon under the gravitational influence of the Earth and the Sun. 

The physical problem was addressed by Amerigo Vespucci and subsequently by Galileo Galilei; in 1499, Vespucci used knowledge of the position of the Moon to determine his position in Brazil. It became of technical importance in the 1720s, as an accurate solution would be applicable to navigation, specifically for the determination of longitude at sea, solved in practice by John Harrison's invention of the marine chronometer. However the accuracy of the lunar theory was low, due to the perturbing effect of the Sun and planets on the motion of the Moon around the Earth. 

Jean le Rond d'Alembert and Alexis Clairaut, who developed a longstanding rivalry, both attempted to analyze the problem in some degree of generality; they submitted their competing first analyses to the Académie Royale des Sciences in 1747. It was in connection with their research, in Paris during the 1740s, that the name "three-body problem" (French: Problème des trois Corps) began to be commonly used. An account published in 1761 by Jean le Rond d'Alembert indicates that the name was first used in 1747.

Other problems involving three bodies

The term 'three-body problem' is sometimes used in the more general sense to refer to any physical problem involving the interaction of three bodies. 

A quantum mechanical analogue of the gravitational three-body problem in classical mechanics is the helium atom, in which a helium nucleus and two electrons interact according to the inverse-square Coulomb interaction. Like the gravitational three-body problem, the helium atom cannot be solved exactly.

In both classical and quantum mechanics, however, there exist nontrivial interaction laws besides the inverse-square force which do lead to exact analytic three-body solutions. One such model consists of a combination of harmonic attraction and a repulsive inverse-cube force. This model is considered nontrivial since it is associated with a set of nonlinear differential equations containing singularities (compared with, e.g., harmonic interactions alone, which lead to an easily solved system of linear differential equations). In these two respects it is analogous to (insoluble) models having Coulomb interactions, and as a result has been suggested as a tool for intuitively understanding physical systems like the helium atom.

The gravitational three-body problem has also been studied using general relativity. Physically, a relativistic treatment becomes necessary in systems with very strong gravitational fields, such as near the event horizon of a black hole. However, the relativistic problem is considerably more difficult than in Newtonian mechanics, and sophisticated numerical techniques are required. Even the full two-body problem (i.e. for arbitrary ratio of masses) does not have a rigorous analytic solution in general relativity.

n-body problem

The three-body problem is a special case of the n-body problem, which describes how n objects will move under one of the physical forces, such as gravity. These problems have a global analytical solution in the form of a convergent power series, as was proven by Karl F. Sundman for n = 3 and by Qiudong Wang for n > 3. However, the Sundman and Wang series converge so slowly that they are useless for practical purposes; therefore, it is currently necessary to approximate solutions by numerical analysis in the form of numerical integration or, for some cases, classical trigonometric series approximations (see n-body simulation). Atomic systems, e.g. atoms, ions, and molecules, can be treated in terms of the quantum n-body problem. Among classical physical systems, the n-body problem usually refers to a galaxy or to a cluster of galaxies; planetary systems, such as stars, planets, and their satellites, can also be treated as n-body systems. Some applications are conveniently treated by perturbation theory, in which the system is considered as a two-body problem plus additional forces causing deviations from a hypothetical unperturbed two-body trajectory.

In popular culture

• The problem is a plot device in the science fiction trilogy by Chinese author Cixin Liu, and its name has been used for both the first volume and the trilogy as a whole.