for the degree of Master of Science

Graduate Department of Computer Science

University of Toronto

© Copyright by Wayne Hayes January 1995

- Short Abstract
- Long Abstract
- Acknowledgements
- Introduction and Motivation
- Shadowing
- High Dimensional Shadowing & Optimizations to the GHYS Refinement Algorithm
- Some preliminary results of high-dimensional shadowing
- Further work
- Appendix: Review of the astrophysical
*N*-body problem - References
- About this document ...

*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.

Sun Dec 29 17:43:41 EST 1996

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