Efficient Shadowing of High Dimensional Chaotic Systems with the Large Astrophysical N-body Problem as an Example

Wayne Hayes

A thesis submitted in conformity with the requirements
for the degree of Master of Science
Graduate Department of Computer Science
University of Toronto
© Copyright by Wayne Hayes January 1995

This M.Sc. thesis is also available in postscript, and PDF.

Short Abstract

N-body systems are chaotic. This means that numerical errors in their solution are magnified exponentially with time, perhaps making the solutions useless. Shadowing tries to show that numerical solutions of chaotic systems still have some validity. A previously published shadowing refinement algorithm is optimized to give speedups of order 60 for small problems and asymptotic speedups of O(N) on large problems. This optimized algorithm is used to shadow N-body systems with up to 25 moving particles. Preliminary results suggest that average shadow length scales roughly as 1/N, ie., shadow lengths decrease rapidly as the number of phase-space dimensions of the system is increased. Some measures of simulation error for N-body systems are discussed that are less stringent than shadowing. Many areas of further research are discussed both for high-dimensional shadowing, and for N-body measures of error.

Table of Contents

• Short Abstract
• Long Abstract
• Acknowledgements
• Introduction and Motivation
  • Introduction
  • History of exponential divergence in N-body systems
  • The kinds of errors made in N-body simulations
  • Summary of this thesis
• Shadowing
  • Introduction
  • The refinement procedure of GHYS
  • A new shadowing procedure: SLES
  • A wider perspective: Why shadowing?
• High Dimensional Shadowing & Optimizations to the GHYS Refinement Algorithm
  • Introduction
  • The Optimizations
  • Reliability of refinement
• Some preliminary results of high-dimensional shadowing
  • High-dimensional N-body shadows encounter difficulty
  • One QT-like experiment with N=65,536, M=1
  • An explanation of one of QT's figures
• Further work
  • Future work in N-body shadowing
  • Further work on shadowing in general
• Appendix: Review of the astrophysical N-body problem
  • Basic N-body Equations
  • Jacobian of an N-M fixed-particle system
• References
• About this document ...

Long Abstract

Astrophysical N-body systems are chaotic. In other words, they have sensitive dependence on initial conditions. This means that the phase-space distance between two solutions whose initial conditions differ by an arbitrarily small amount will increase exponentially with time. Since computers constantly make small errors in the computation of such solutions, it is guaranteed (with probability 1) that a computed solution will diverge exponentially from the true solution with the same initial conditions. Thus, it is possible that numerical solutions for chaotic systems are overwhelmed by exponential magnification of small errors, which might mean computed solutions are worthless. This could be the case even if quantities such as energy or momentum are conserved to arbitrary accuracy, because there are infinitely many solutions whose energy is exactly the same, but have vastly different phase space trajectories.

Shadowing is a branch of chaotic systems theory that tries to show that, even in the face of the exponential magnification of small errors, numerical solutions have some validity. It does this by trying to show that, for any particular computed solution (the ``noisy'' solution), there exists a true solution with slightly different initial conditions that stays uniformly close to the computed solution. If such a solution exists, it is called a true shadow of the computed solution. An approximation to true shadowing is numerical shadowing, whereby an iterative refinement algorithm is applied to a noisy solution to produce a nearby solution with less noise. If this iterative process converges to a solution with noise close to the machine precision, the resulting solution is called a numerical shadow. Numerical shadowing is very computationally intensive, because it requires the storage and manipulation of the full phase-space trajectory of the system, at much higher precision than the original computation.

The main thrust of this thesis is to extend a previously published numerical shadowing refinement procedure to make it more efficient, thus allowing larger and more realistic systems to be shadowed. The astrophysical N-body problem is used as an example, although the refinement procedure could just as easily be used on any chaotic system. With various numerical tricks and physical insights, our algorithm runs, depending on the problem, between 5 and 100 times faster than the original algorithm.

Using this optimized algorithm, shadowing experiments were performed on N-body systems in which M bodies move amongst N-M fixed ones. For systems of using a variable-timestep integrator and no softening, our results show that the length of time an orbit is shadowable decreases with increasing M. However, it is unclear whether this is owing to collective effects of interacting moving particles, or whether each particle individually has a ``glitch rate'', causing the global glitch rate to increase linearly with the number of particles. However, for a system of N=65536,M=1 with softening and integrating using constant timestep leapfrog, we were able to shadow the moving particle for two dozen crossing times, which is encouraging.

Finally, there is much further work that should be done on both general N-body shadowing. We point out some possible directions for further research.

Access count (updated once a day) since 1 Jan 1997: 20159