The Algorithms Behind GAIO — Set Oriented Numerical Methods for Dynamical Systems

In a given dynamical system there are essentially two different types of information which could be of practical interest: on the one hand there is the need to describe the behavior of single trajectories in detail. This information is helpful for the analysis of transient behavior and also in the investigation of geometric properties of dynamical systems. On the other hand, if the underlying invariant set is generated by complicated dynamics then the computation of single trajectories may give misleading results. In this case there still exists important set related information covering both topological and statistical aspects of the underlying dynamical behavior. Within the DFG-Schwerpunkt we have focussed on the development of set oriented methods for the numerical approximation of invariant sets (e.g. invariant manifolds, global attractors, chain recurrent sets) (natural) invariant measures almost invariant sets The basic concept is a subdivision algorithm which is similar in spirit to the well known cell mapping techniques but with the crucial difference that the numerical effort mainly depends on the complexity of the dynamics rather than on the dimension of the underlying state space. First, the invariant set is covered by boxes and then the dynamical behavior on the set is approximated by a Markov chain based on transition probabilities between elements of this covering. The algorithms have been implemented in the software package GAIO (Global Analysis of Invariant Objects), and in this article we describe both the related numerical techniques together with their theoretical foundations and how to use them within GAIO. We will also discuss details concerning the implementation such as adaptive versions of the methods.