Capturing the Global Behavior of Dynamical Systems with Conley-Morse Graphs

Abstract

We present a computational machinery for describing and capturing the global qualitative behavior of dynamical systems (Arai et al. SIAM J Appl Dyn Syst 8:757–789, 2009). Given a dynamical system, by subdividing the phase space into a finite number of blocks, we construct a directed graph which represents the topological behavior of the system. Then we apply fast graph algorithms for the automatic analysis of the dynamics. In particular, the dynamics can be easily decomposed into recurrent and gradient-like parts which allows further analysis of asymptotic dynamics. The automatization of this process allows one to scan large sets of parameters of a given dynamical system to determine changes in dynamics automatically and to search for “interesting” regions of parameters worth further attention. We also discuss an application of the method to time series analysis. The method presented in Sects. 1 –4 below is given in [1] for the first time, which is based on and combines a number of theoretical results as well as computational software packages developed earlier. For the details, see the original paper [1].

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

1 Conley-Morse Decompositions

Throughout the paper, we assume that the system is given by a family of continuous maps

$$f : {\mathbb{R}}^{n} \times {\mathbb{R}}^{d} \ni (x,\lambda )\mapsto {f}_{ \lambda }(x) \in {\mathbb{R}}^{n}.$$

We are interested in the analysis of global dynamics generated by f as the parameter λ is varied over ${\mathbb{R}}^{d}$. In most situations, only some bounded regions $R \subset {\mathbb{R}}^{n}$ and $\Lambda \subset {\mathbb{R}}^{d}$ have physical meaning for the analyzed model. If both R and Λ are rectangular regions then one can easily introduce finite rectangular grids $\mathcal{H}$ and ℒ in both of them.

A Morse decomposition of a dynamical system is a finite collection of disjoint isolated invariant sets S ₁, …, S _n (called Morse sets) with strict partial ordering ≺ on the index set {1, …, n} such that for every x in the phase space there exist indices i ≺ j such that the α- and ω-limit sets of x is contained in S _j and S _i , respectively. A Morse decomposition can be represented in terms of a directed graph G = (V, E) where V = { S ₁, …, S _n } and (S _i , S _j ) ∈ E iff j ≺ i. This graph is called a Morse graph. If each Morse set is assigned its Conley index [3, 4] then such a structure is called a Conley-Morse decomposition, and the corresponding graph is called a Conley-Morse graph [1].

Note that a Morse decomposition of X is not unique. In particular, if i, j are such indices that i ≺ j but there is no other index k such that i ≺ k ≺ j then one can create a coarser Morse decomposition by replacing S _i and S _j with S _i ∪S _j ∪C(i, j), where C(i, j) denotes the union of the images of all the complete orbits such that γ(t) → S _i and γ( − t) → S _j as t → ∞.

2 Graph Representation

Given a formula for f _λ and some grid $\mathcal{H}$ in the region $R \subset {\mathbb{R}}^{n}$, for each parameter set $L \in \mathcal{L}$ one can use the interval arithmetic directly to compute a combinatorial representation ${\mathcal{F}}_{L}: \mathcal{H}\multimap \mathcal{H}$ for f _λ, which then will be represented by a directed graph G = (V, E) where $V = \mathcal{H}$ and (v, w) ∈ E iff $w \in \mathcal{F}(v)$. It turns out that the analysis of the graph G can easily provide meaningful information on the asymptotic dynamics of f _λ represented by ${\mathcal{F}}_{L}$. For example, each combinatorial invariant set defined as a set $\mathcal{S}\subset \mathcal{H}$ for which $\mathcal{S}\subset \mathcal{F}(\mathcal{S}) \cap {\mathcal{F}}^{-1}(\mathcal{S})$ covers an isolated invariant set with respect to f _λ. More precisely, if $\mathcal{S}$ is a combinatorial invariant set then $\vert \mathcal{S}\vert$ is an isolating neighborhood, and if S is an isolated invariant set with respect to f _λ for some λ ∈ L then its minimal cover $\mathcal{S}$ is a combinatorial invariant set. Another example is a combinatorial attractor defined as a set $\mathcal{A}\subset \mathcal{H}$ such that $\mathcal{F}(\mathcal{A}) \subset \mathcal{A}$ which covers a real attractor for f _λ. In fact, if $\mathcal{A}$ is a combinatorial attractor then $\vert \mathcal{A}\vert$ is an isolating neighborhood whose invariant part $A :=\mathrm{ Inv}\vert \mathcal{A}\vert$ is stable in the sense of Conley, that is, every positive semitrajectory starting in some open neighborhood of A tends to A. In particular, if there exist two combinatorial attractors for ${\mathcal{F}}_{L}$ then this implies the existence of two disjoint attraction basins for f _λ for every λ ∈ L. See [2] for detail.

Extensive analysis of the dynamics can be obtained by computing the strongly connected components of G. It is known that all the strongly connected components of G form isolating neighborhoods for the union of all the chain recurrent sets of the dynamical system, and thus can serve as a combinatorial Morse decomposition $\{{\mathcal{M}}_{i} : i = 1,\ldots,k\}$, for some k > 0, which represents a family of isolating neighborhoods $\vert {\mathcal{M}}_{i}\vert$. The sets ${\mathcal{M}}_{i}$ are called combinatorial Morse sets. A partial order ≺ between the computed combinatorial Morse sets can be determined by the analysis of paths in G connecting those sets.

3 Continuation and Bifurcations

If two adjacent sets of parameters L ₁, L ₂ ⊂ Λ, with L ₁ ∩ L ₂ ≠ ∅, are considered, and the combinatorial Morse decompositions computed for L ₁ and L ₂ are equivalent then we talk about continuation of combinatorial Morse decompositions. More precisely, let $({\mathcal{M}}_{1}^{1},\ldots,{\mathcal{M}}_{{k}_{1}}^{1},{\prec }^{1})$ be a combinatorial Morse decomposition for ${\mathcal{F}}_{{L}_{1}}$ and let $({\mathcal{M}}_{1}^{2},\ldots,{\mathcal{M}}_{{k}_{2}}^{2},{\prec }^{2})$ be a combinatorial Morse decomposition for ${\mathcal{F}}_{{L}_{2}}$. We say that these decompositions are equivalent if $k := {k}_{1} = {k}_{2}$ and there exists a bijection b of the set {1, …, k} onto itself such that ${\mathcal{M}}_{i}^{1} \cap {\mathcal{M}}_{j}^{2}\not =\varnothing$ iff j = b(i), and b does not violate the order defined by the relations ≺ ¹ and ≺ ², that is, for no i, j one has i ≺ ¹ j and b(j) ≺ ² b(i).

This definition provides a very weak kind of continuation; it is, in fact, the continuation of isolating neighborhoods in the sense of Conley (see [3]). In particular, the lack of continuation suggests a substantial change in dynamics. It implies such a change only if one ignores spurious Morse sets in the comparison of combinatorial Morse decompositions. One can use the Conley index to determine which combinatorial Morse sets are not spurious, and the lack of continuation between those sets with nontrivial Conley indices implies that a bifurcation is taking place. The type of bifurcation can be determined to certain extent by analyzing failures of continuation; for example, a bifurcation that resembles the saddle-node bifurcation at the scale of isolating neighborhoods can be detected as a series of two failures of continuation: first, a combinatorial Morse set with a trivial index appears from nothing, and second, this set splits into two combinatorial Morse sets with non-trivial indices, one corresponding to a stable fixed point or periodic orbit, and the other one corresponding to an unstable fixed point or periodic orbit, respectively.

4 Applications

The practicality of the method is illustrated in [1] with the application to the 2-dimensional non-linear Leslie population model $f : {\mathbb{R}}^{2} \times {\mathbb{R}}^{4} \rightarrow {\mathbb{R}}^{2}$, which is given by

$$f(x,y;{\theta }_{1},{\theta }_{2},\kappa,p) = \big{(}({\theta }_{1}x + {\theta }_{2}y)\,\mathrm{{e}}^{-\kappa (x+y)},px\big{)}.$$

The numerical studies in [5] indicate that this system exhibits a wide variety of different dynamical behavior, and thus is considered a meaningful test for the usefulness of our method. In particular, the coexistence of multiple chaotic attractor, a very important behavior from a practical point of view, is observed for some parameter values [5]. However, the computation in [5] is done only for a limited set of parameters and therefore, we would like to ask when this coexistence happens for a larger parameter region.

Fig. 1

Morse decomposition for ${\theta }_{1} = {\theta }_{2} = 32.0$

The parameter κ is just a rescaling factor, so it is arbitrarily set to 0. 1, as in [5]. The parameter p is fixed to 0. 7, also the same as in [5].

By applying our method to the nonlinear Leslie model with ${\theta }_{1} = {\theta }_{2} = 32.0$, we obtain Figs. 1 and 2. Figure 1 shows resulting three Morse sets: the fixed point at the origin, the oval-shaped region in the middle and the largest one surrounding oval one. Figure 2 is the Conley-Morse graph. The numbers inside the vertices carry the information of Conley indexes of associated Morse sets. From this graph, we can read the coarse gradient behavior of the dynamics: the origin and the oval invariant set are relative repellers and there exist connecting orbits from these repellers to the attractor.

The result of the continuation analysis of the previous section is illustrated in Fig. 3. For simplicity, the parameter space (θ₁, θ₂) ∈ [10, 35]² is subdivided into 64 ×64 equal squares here. The bounded region R in the phase space is subdivided into 4096 ×4096 rectangles of the same size and a combinatorial Conley-Morse decomposition is computed for each parameter box using this grid. In the picture, adjacent boxes in the parameter space (θ₁, θ₂) with equivalent Morse decompositions are plotted in the same shade of gray and white squares correspond to parameter boxes for which no continuation could be found to any adjacent box. The transitive reduction of the Morse graph is illustrated for some regions; a square indicates an attractor, a filled circle corresponds to a Morse set with a nontrivial Conley index, and a hollow circle indicates a Morse set with the trivial Conley index. From the figure, we can easily identify the parameter region with multiple attractors. We want to emphasize here that this computation is fully automatic and no a priori knowledge is required. Therefore our method can also be applied for higher dimensional problems where it is difficult to answer the number of attractors from simple numerics.

Fig. 2

Conley-Morse graph for ${\theta }_{1} = {\theta }_{2} = 32.0$

Fig. 3

“Bifurcation” diagram

One can interactively explore computational results explained in this section at the project web site http://chomp.rutgers.edu/database/.

5 Time Series Analysis

In practical applications, the data of the system of our interest is often provided as a time series coming from experiments. In this section, we thus present some preliminary computations towards the application of Conley-Morse graph method to time series analysis.

We remark that in real experiments, the size of the data is always finite. Therefore even if we know that the system is driven by a continuous dynamical system, its behavior can not be entirely reconstructed from the data. Hence, our goal would be to reconstruct a coarse-grained system as close to the original one as possible. Since the Conley-Morse graph method explained in previous sections involves a procedure of coarsening, namely, fixing a grid-size on the phase space and ignoring the behavior of the system smaller than this grid size, it is natural to apply this method to time series analysis.

For this purpose, we need to notice that due to practical restrictions on experiments, a time series is usually not fully distributed on the phase space or attractors of the system. That is, the information of the system may be missing on significantly large parts of the phase space. And furthermore, a times series may contain unknown experimental noise. Therefore, we muse discuss the robustness of the Conley-Morse graph computation under the existence of noise and deficits.

Fig. 4

From a time series of length 30  × 2,000

Figure 4 illustrates the result of a Morse decomposition for a time series of length 30  × 2,000 (the data of 2,000 orbits of length 30) generated by the non-linear Leslie model with ${\theta }_{1} = {\theta }_{2} = 32.0$. Compared with Morse sets in Fig. 1 where we constructed them directly from the dynamics, we find that Morse sets reconstructed here from the time series miss some parts while their rough geometric shapes are similar.

Figure 5 is the same as Fig. 4, but for a time series of length 30  × 500. Notice that although the size of the series is one-fourth of the first figure, we still have a qualitatively similar decomposition of the invariant set.

Fig. 5

From a time series of length 30 ×500

Figure 6 shows the Morse decomposition obtained for a noisy time series. The parameter of the system is the same as before, but here we put Gaussian noise of standard deviation 0.15. Notice that the shape of Morse sets now blurs to some extent but still keeps the essential structure of the original decomposition.

Fig. 6

From a noisy time series

These computations advocate a vague kind of robustness of Conley-Morse graph and possible application to times series analysis. To obtain mathematically meaningful results, we need a more detailed study on it taking the dependency of Conley-Morse graph on noise and deficits into account. This will be discussed elsewhere.