Decomposition and Clustering for the Visualization of Dynamical Systems

Abstract

We discuss recently developed methods for the visualization of dynamical systems which are based on the decomposition of the phase space of the system. The information of the system is represented by a directed graph and then the graph will be decomposed into smaller subsets which eventually defines a partition of the phase space. Depending on the purpose of visualization and the nature of the system, two different decompositions are introduced. The first decomposition algorithm is called Conley-Morse decomposition, which decompose the system according to the gradient-like structure of the system. On the other hand, the latter algorithm, an application of the peer pressure clustering algorithm for directed graphs, decompose each recurrent components of the system into further smaller non-invariant subsets according to the similarity of the dynamical behavior.

1 Introduction

An effective visualization of the global behavior of a dynamical system or a fluid simulation inevitably involves a sort of the partition, or the decomposition of the phase space of the system. This is because, in a generic dynamical system there exist uncountably many orbits having “similar” dynamical behaviors. If we plot too many of them then typically we end up with a picture carrying no information. For example, Fig. 1 illustrates 300 (left) and 3,000 (right) different trajectories of the standard map, the most important example of Hamiltonian dynamics, of length 100. It easy to imagine that this problem will be more serious in higher dimensional spaces where we can not use our geometric and physical intuition on the space.

Fig. 1

Plots of 300 (left) and 3,000 (right) orbits of $(x, y) \mapsto (x + k \sin y, x + y + k \sin y)$, the standard map with the parameter $k = 0.971635$. The map is

Thus, a natural way to visualize the global behavior of the systems is to classify the points in the phase space into a relatively small number of clusters, so that each cluster corresponds to a particular dynamical behavior.

In following sections, we will explain two recently proposed ideas for obtaining such a clustering of dynamical systems. In the next section, we will briefly review the Conley-Morse decomposition, a decomposition of the phase space according to the gradient-like structure of the system. Unfortunately this method does not work fine for conservative dynamics such as Hamiltonian dynamics and hence we will discuss another algorithm based on a graph clustering algorithm in the last section. This is a work in progress in the JST CREST project [9].

2 Conley-Morse Decomposition

In this section, we discuss the method of the Conley-Morse decomposition [1, 2]. The key idea here is to find small subsets in the phase space which are invariant under the dynamics, and then decompose the phase space into these subsets and connecting orbits among them. These invariant subsets will be called Morse sets.

Fig. 2

Collapsing strongly connected components of $G$

Historically, this idea was first applied to the gradient flows satisfying a certain non-degeneracy condition by M. Morse. Here by a gradient flow we mean a flow on a manifold $M$ that is defined by the gradient vector field $\mathrm {grad}\ f$ for a smooth function $f: M \rightarrow \mathbb {R}$. Note that in a gradient flow, there will be no periodic orbit (or, closed orbit) nor chaotic orbit and thus Morse sets are just equilibrium points of the flow. Note that equilibrium points of the flow generated by $\mathrm {grad}\ f$ are exactly the critical points of $f$.

Then C. Conley generalized the theory to arbitrary continuous dynamical systems yielding the celebrated Fundamental theorem of dynamical systems, which says that a dynamical system can always be decomposed into (possibly chaotic) Morse sets and non-chaotic connecting orbit among them. In this generalized case, since the dynamics is not assumed to be a gradient flow anymore, a Morse sets can be an equilibrium point, a periodic orbit, or a chaotic invariant set such as the Lorenz attractor. The fundamental theorem does not tell the detail of the dynamics inside Morse sets (except the fact they should satisfy a sort of recurrence condition called chain recurrence), but the point is that we can clearly separate chaotic and non-chaotic region of the dynamics.

When the dynamics enjoys the structural stability (essentially equivalent to the property called uniform hyperbolicity), there exists finitely many Morse sets and the dynamics on them can be described in a symbolic manner (Markov partition). Unfortunately, there may be infinitely many Morse sets in general and in such a case, the gradient structure outside the Morse sets will not be robust under small perturbations. However, since we are mainly interested in the application to practical problems in which noise and errors are inevitably involved, we can restrict ourselves to finitely many larger Morse sets. In practice, this can be achieved by fixing the grid size for our computation and ignoring Morse sets smaller than the grid size.

Given a dynamical system and a grid decomposition of the phase space, the first step of the algorithm is to define a graph $G$ whose edges imitate the dynamics. Usually, we simply subdivide the phase space into small cubes using a uniform grid, and then encode the dynamical behavior by looking how the image of each cube intersects other cubes (see Arai et al. [2, 4], for example).

Then we can expect that a Morse set corresponds to a strongly connected component in $G$. Given a directed graph $G$, a subset of vertices of $G$ is called strongly connected if for any $v, w$ in the set, there exist directed paths from $v$ to $w$ and $w$ to $v$. It is well knows that there exist linear-time algorithms that can decompose a directed graph $G$ into strongly connected components.

By collapsing each strongly connected component of $G$ to a single node, we can obtain a much smaller graph $\fancyscript{G}$ representing the structure of the Conley-Morse decomposition (Fig. 2). Note that $G$ could be very huge depending on the dimension of the phase space and the size of the grid we are using, however, the graph $\fancyscript{G}$ obtained after collapsing would be much smaller than $G$. A node in the collapsed graph corresponds to a Morse set of the system.

For each Morse set, we then compute the Conley index, which is an algebraic topological invariant carrying the information of the dynamics in a neighborhood of the Morse set [3, 6]. Finally, for each vertex of $\fancyscript{G}$ we associate the Conley index of the corresponding Morse set. The obtained data structure is called the Conley-Morse graph and the corresponding decomposition of the system is called the Conley-Morse decomposition.

Fig. 3

The “bifurcation” diagram of the Leslie population model

Figure 3 illustrates an example of the application of Conley-Morse decomposition to the Leslie population model, a map defined by

$$f(x_1, x_2; \theta _1, \theta _2) = ((\theta _1 x_1 + \theta _2 x_2) \cdot e^{-0.1(x_1 + x_2)}, 0.7 x_1).$$

The map defines a dynamical system $f: \mathbb {R}^2 \rightarrow \mathbb {R}^2$ with two parameters $\theta _1, \theta _2$ that represent the birth rate of the first and second generation, respectively. The figure shows a decomposition of the parameter $(\theta _1, \theta _2)$-plane according to the obtained Conley-Morse graph structure; adjacent boxes in the parameter space with equivalent Conley-Morse graphs are plotted in the same color. A square, a filled circle, a hollow circle in directed graphs indicates an attractor, a Morse set with non-trivial Conley index, and a Morse set with trivial Conley index, respectively. If the Conley index of a Morse set is non-trivial, then we can prove the Morse set is non-empty, that is, there really exist some orbit completely contained in the Morse set. On the other hand, if the Conley index is trivial, the Morse set might be empty; typically, this happens when our gird size is too coarse to distinguish a very slow dynamics from a true invariant set.

Fig. 4

Morse sets for a flow on the surface of a cooling jacket

Although the algorithm works fine for the Leslie model and some other lower dimensional problems, its computational cost is still expensive to be applied to more practical problems. To overcome this computational difficulty, Szymczak et al. developed the method of the piecewise constant approximation of a vector field [7, 8] using the theory of differential inclusions. The trajectories in a piecewise constant vector filed can be determined by simple geometric rules and hence we can avoid computationally expensive numerical integrations.

Fig. 5

A close up view of Morse sets

Figures 4 and 5 show the result of the application of Szymczak’s idea to the vector field on the surface of a cooling jacket which is induced by extrapolating data from 3D fluid simulation in the jacket (figures are provided by the courtesy of A. Szymczak). Note that the original 3D flow does not have any attractors nor repellers since it is incompressible, but the flow on the surface has a gradient-like structure illustrated in the figures, which represents the dynamics vertical to the surface.

3 Graph Clustering Algorithms

The idea of Conley-Morse decomposition that we have seen in the previous section works generally well for dissipative dynamics, in which we can expect the existence of attractors and repellers. On the other hand, in conservative systems, for example in Hamiltonian dynamics, there is no attractor and repeller and thus typically the Conley-Morse decomposition becomes a trivial one.

To obtain an effective visualization of conservative systems, therefore, another criterion for the phase space partition is required. Note that if the system $T: X \rightarrow X$ is ergodic, we can not use a function $f: X \rightarrow \mathbb {R}$ to define such a partition of $X$ because for almost all initial point $x \in X$, the time average

$$ \lim _{n \rightarrow \infty } \frac{1}{n} \sum _{i = 0}^{i = n}f(T^i(x)) $$

takes the same value. This suggests that our criterion should be based on the finite-time behavior of trajectories, rather than the asymptotic behavior as we have done in the Conley-Morse decomposition.

Here we propose a practical algorithm based on a graph clustering algorithm called Peer Pressure Clustering (PPC) [5]. A graph clustering algorithms classifies the nodes of a graph with respect to some similarity between nodes, where the similarity is defined suitably depending on the purpose of the clustering. These algorithms have been applied to the study of social networks, machine learning, data mining, pattern recognition, image analysis, and bioinformatics.

At the initial condition of PPC algorithm, each node of the graph compose a cluster to which only this node belongs. Then PPC iteratively refines the clustering so that the connectivity inside a cluster will be higher than the connectivity between different clusters. More precisely, in every iteration step, each node of the graph decides to which cluster it should belong by feeling the pressure from its friends (adjacent nodes); if there are many adjacent nodes that belong to a particular cluster, then the node choose to belong the same cluster. Unfortunately, the convergence of the algorithm is not guaranteed for a general graph; it may end up with a periodic emergence of different clustering. However, in most of our cases the algorithm stops after a small number of iterations and runs much faster than other clustering algorithms such as Markov clustering.

Fig. 6

A clustering of the phase space of the standard map obtained by PPC algorithm

In what follows, we apply PPC algorithm to the graph $G$ obtained from a given dynamics. The resulting clustering of $G$ corresponds to a partition of the phase space of the system. Since $G$ imitates the behavior of the original dynamics, we can expect that this partition of the phase space enjoys a property similar to the clustering of $G$; the mixing inside a cluster should be stronger than mixing between different clusters.

Figure 6 shows the result of PPC for a graph obtained from the standard map. We note that quasi-periodic motions and chaotic motions are clearly separated by the algorithm. We note that the directed graph obtained from the system is itself strongly connected, and hence the Conley-Morse decomposition algorithm gives the trivial decomposition, that is, the only non-empty Morse set is the entire phase space.

Fig. 7

The flow (top) and the results of coarser (bottom left) and finer (bottom right) PPC clustering

Figure 7 shows a 2D numerical fluid simulation using the Lattice-Boltzmann method and the result of PPC applied to it. Two PPC results are shown for different values of a parameter in the algorithm that control the granularity of the clustering.