An Algorithmic Approach to The Lattice Structures of Attractors and Lyapunov functions

Ban and Kalies [3] proposed an algorithmic approach to compute attractor-
repeller pairs and weak Lyapunov functions based on a combinatorial multivalued
mapping derived from an underlying dynamical system generated by a continuous
map. We propose a more e cient way of computing a Lyapunov function for a Morse
decomposition. This combined work with other authors, including Shaun Harker,
Arnoud Goulet, and Konstantin Mischaikow, implements a few techniques that makes
the process of nding a global Lyapunov function for Morse decomposition very e -
cient. One of the them is to utilize highly memory-e cient data structures: succinct
grid data structure and pointer grid data structures. Another technique is to utilize
Dijkstra algorithm and Manhattan distance to calculate a distance potential, which is
an essential step to compute a Lyapunov function. Finally, another major technique
in achieving a signi cant improvement in e ciency is the utilization of the lattice
structures of the attractors and attracting neighborhoods, as explained in [32]. The
lattice structures have made it possible to let us incorporate only the join-irreducible
attractor-repeller pairs in computing a Lyapunov function, rather than having to use
all possible attractor-repeller pairs as was originally done in [3]. The distributive lattice structures of attractors and repellers in a dynamical
system allow for general algebraic treatment of global gradient-like dynamics. The
separation of these algebraic structures from underlying topological structure is the
basis for the development of algorithms to manipulate those structures, [32, 31].
There has been much recent work on developing and implementing general compu-
tational algorithms for global dynamics which are capable of computing attracting
neighborhoods e ciently. We describe the lifting of sublattices of attractors, which
are computationally less accessible, to lattices of forward invariant sets and attract-
ing neighborhoods, which are computationally accessible. We provide necessary and
su cient conditions for such a lift to exist, in a general setting. We also provide
the algorithms to check whether such conditions are met or not and to construct the
lift when they met. We illustrate the algorithms with some examples. For this, we
have checked and veri ed these algorithms by implementing on some non-invertible
dynamical systems including a nonlinear Leslie model.