The "Butterfly Effect" refers to the idea that a butterfly flapping its
wings in Hawaii can affect the weather over L.A. a few weeks later.
The Butterfy Effect is an example of "sensitive dependence on small
changes", which is exhibited by many nonlinear dynamical systems, from
integrated circuits to galaxies. When such systems are simulated on a
computer, this sensitivity causes small numerical errors to become
exponentially magnified, leading to the possibility that trajectories
of such simulations are the result of nothing but magnified noise. To
justify the reliability of such simulations, we turn to the study of
"shadowing". A "shadow" is an exact trajectory that stays close to a
numerical trajectory for a long time, even in the face of sensitive
dependence. From the standpoint of physics, a numerical trajectory
that has a shadow can be viewed as an experimental observation of that
shadow, which means that the dynamics observed in the simulation are
real. This is a very strong statement of simulation reliability.
However, verifying the existence of a shadow formally takes time
O(N^3), where N is the number of components in the system. In this talk
I will outline how I demonstrated the existence of shadows of galaxy
simulations in which N=10^8.
Biographical Sketch:
Wayne Hayes received his undergraduate degree in Computer Science and
Astrophysics, and his M.Sc. and Ph.D. degrees under Ken Jackson from
the Department of Computer Science, all at the University of Toronto.
As an undergraduate working with Mart Molle he designed and published
an improvement to the Ethernet network protocol that attracted the
interest of Cisco Systems, Inc. He spent a year with the IBM optimizing
compiler group, a year programming financial risk analysis software at
Algorithmics, Inc., and a year at Altera Corporation programming
heuristics to solve NP-hard optimization problems in FPGA design and
fitting. He was a post-doctoral fellow under Wayne Enright at the
Fields Institute for Research in Mathematical Sciences, and spent a
summer studying protein folding at the Samuel Lunenfeld Research
Institute with Chris Hogue. He was a Research Associate at the
Institute for Physical Science and Technology at the University of
Maryland, College Park, where he worked under recent Japan Prize winner
James Yorke and collaborated with members of The Institute for Genome
Research (TIGR) and The Baylor College of Medicine to advance the art
of genome sequence assembly. He is currently an Assistant Professor of
Computer Science at the University of California, Irvine.
