From Finite Vector Field Data to Combinatorial Dynamical Systems in the Sense of Forman

The concept of combinatorial vector fields, introduced by Robin Forman [6] [5] [7], is a useful tool to discretize continuous problems in mathematics [13], in imaging [17], and in the computation of homology [9]. We are interested in the combinatorial dynamical system, because it gives a qualitative approach to study dynamical systems. We are interested to study the global dynamics by approximating the underlying dynamical system with combinatorial vector field. More development in [10] shows that classical dynamical system and combinatorial dynamical system are similar on the level of Conley Index. In recent years, a generalization for combinatorial dynamical system is the combinatorial multivector field studied has been proposed by [14]. A reason for this generalization is that the original Forman’s definition of combinatorial vector field is hard to implement. We show that it is possible to construct a combinatorial dynamical system in the sense of Forman with finite vector field data.

There are algorithms to construct a multivector field [3], and combinatorial gradient vector field in the sense of Forman from simplicial complex with value on vertices in $\mathbb{R}$ [17] [11], and $\mathbb{R}^{d}$ [1]. But there is no algorithm to construct a Forman’s combinatorial dynamical system with cyclic behaviour. There are multiple results that we can apply on a combinatorial dynamical system. As an example, we can construct a semi flow [15], a cell decomposition[10] and a Morse decomposition [2] for combinatorial dynamical systems.

By means of an example, it has been argued in [14] that combinatorial dynamical system in the sense of Forman might not be best suited for applications. The article [14] generalize it to combinatorial multivector field. For more information on combinatorial vector field, we refer this article [12] to the reader. In this paper, we argue that we can obtain a combinatorial dynamical system by Forman from data and we find an approximation of the global behaviour of the dynamical system with our method.

Let us take the same example at [14] in the section 3.4 and apply our method on it. We have the following equations:

The dynamical system (1) has a repulsive stationary point at $(0,0)$. It also has an attracting periodic orbit with a radius $1$ with a center at $(0,0)$ and a repulsive periodic orbit with a radius $2$ with a center at $(0,0)$. For the dataset, we take the following data points $X=\{(0.22+0.44i,0.22+0.44j)\mid i=-8,-7,-6,\ldots,6,7\text{ and }j=-8,-7,-6,\ldots,6,7\}$. We construct the cubical complex of this dataset. The length of the side of a square is $0.44$. By applying our algorithm, we obtain the Figure (1). At the middle we obtain a critical square that represents a repulsive behaviour. The arrows in yellow are all part of an attracting periodic orbit. The arrows in purple are all part of a repulsive periodic orbit. The blue arrows represent the gradient behaviour. We obtain the expected results of a repulsive stationary point, an attracting periodic orbit and a repulsive periodic orbit.

The main result is the construction of a combinatorial dynamical system from finite vector field data. The data is $X$ a set of points and $\dot{X}$ the set of vector associates to each point. Let $X=\{x_{1},x_{2},\ldots,x_{N}\}$ such as $x_{i}\in\mathbb{R}^{d}$ and $\dot{X}=\{\dot{x_{1}},\dot{x_{2}},\ldots,\dot{x_{N}}\}$ such as each $\dot{x_{i}}\in\mathbb{R}^{d}$ is a vector associate to the point $x_{i}$. The algorithm is done in three steps. First, we need to construct a simplicial complex. For the purpose of this paper, we use a method based on the Delaunay complex and the Dowker complex. We can also use a cubical complex. Next, we assign a vector to each simplex in the simplicial complex. The assignment is different if we have a Delaunay complex or a Dowker complex. Finally, we match a $n$-simplex with a $(n+1)$-simplex or itself to satisfy the definition of a combinatorial dynamical system. We use a linear minimization with binary variables and linear equality constraints. Let $K$ a simplicial complex, $N$ the number of simplices in $K$ and $x_{i},x_{j}\in K$. Let’s define $A_{N}(\{0,1\})$ a matrix with binary entries. The matrix $A$ is called the matching matrix and induce a matching. If $a_{ij}=1$, then we match the simplex $x_{i}$ to $x_{j}$. If $a_{ij}=0$, then we don’t match the simplex $x_{i}$ to $x_{j}$. For each $a_{ij}$, we associate a cost $c_{ij}$. We set a high cost if the matching is not admissible or the matching is bad. We put a low cost if the matching is good. If $i=j$, then we set a fix cost to a parameter $\alpha$. The constraints guarantee that each simplex is matched only once. We obtain the following minimization problem:

We have an integer linear problem(ILP). We obtain our main result.

The article is organized as follows. In Section 2, we explain basic definitions related to simplicial complex and combinatorial dynamical system. In Section 3, we show how to construct a simplicial complex by using the Delaunay Complex or the Dowker Complex. In Section 4, we assign a vector to each simplex. The assignment is different, if we use a Delaunay complex or a Dowker complex. In Section 5, we define the minimization problem. We also show that the global minimum of the minimization problem induces a matching that satisfies the definition of combinatorial dynamical system. In Section 6, we use our method to the Lotka-Volterra model and the Lorenz attractor model. In Section 7, we show two extensions to the algorithm. We can apply a barycentric subdivision to a simplicial complex before solving the optimization problem. The second extension is to obtain a combinatorial dynamical system which is a gradient field. We can choose the parameter $\alpha$ so that the solution from the minimization problem is gradient or we can add constraints to the minimization problem removing cycles in the solution.

In this section, we discuss about simplicial complex and combinatorial dynamical system in the sense of Forman. For more information on simplicial complex, we refer to the reader this book [16] for simplicial complex and these papers [10] [5] for combinatorial dynamical systems.

An abstract simplicial complex is a set $K$ that contains finite non-empty sets such that if $A\in K$, then for all subsets of $A$ is also in $K$. We also use the geometric simplex defined as follows. A geometric $n$-simplex is the convex hull of a geometrically independent set $\{v_{0},v_{1},\ldots,v_{n}\}\subset\mathbb{R}^{d}$. This is the set of $x$ such as $x=\sum_{i=0}^{n}t_{i}v_{i}$ and $\sum_{i=0}^{n}t_{i}=1$. $t_{i}$ are called barycentric coordinates. We denote $[v_{0},v_{1},\ldots,v_{n}]$ a $n$-simplex spanned by the vertices $v_{0},v_{1},\ldots,v_{n}$. A simplicial complex $K$ is a collection of simplices such that for all $\sigma\in K$, if $\tau\leq\sigma$, then $\tau\in K$ and if $\tau=\sigma_{1}\cap\sigma_{2}$ then $\tau$ is either empty or a face of $\sigma_{1}$ and $\sigma_{2}$. We note $K_{n}$ the set of all $n$-simplices in $K$. Any simplex spanned by the subsets of $\{v_{0},v_{1},\ldots,v_{n}\}$ are called faces. We note $\sigma\leq\tau$. If $\sigma\leq\tau$ and $\sigma\neq\tau$, then we say that $\sigma$ is a proper face of $\tau$. We note $\sigma<\tau$. The closure of $\sigma$ is the union of all faces of $\sigma$ noted $\operatorname*{Cl\,}\sigma$. The boundary of $\sigma$ is the union of all proper faces of $\sigma$ noted $\operatorname*{Bd\,}\sigma$.

We define a partial map $f\subset X\times Y$ if $f$ is a relation and $(x,y),(x,y^{\prime})\in f$, then $y=y^{\prime}$. We write $f:X\nrightarrow Y$. We define the domain and the image of $f$ as follows:

• •

  $\operatorname*{Dom\,}f:=\{x\in X\mid\exists y\in Y,(x,y)\in f\}$;

• •

  $\operatorname*{Im\,}f:=\{y\in Y\mid\exists x\in X,(x,y)\in f\}$.

A partial map $f$ is injective, if for $x,x^{\prime}\in X$ we have $f(x)=f(x^{\prime})$ implies that $x=x^{\prime}$. We can now define a combinatorial dynamical system. We use the same definition as [10].

This definition is equivalent to the definition of combinatorial dynamical system in the sense of Forman [5] [7]. But our definition uses a partial map. The first condition defines the combinatorial vector of $\mathcal{V}$. The second condition is that every simplex is in a matching. The third condition is that only critical simplices are in both the image and the domain of $\mathcal{V}$.

To visualize combinatorial dynamical system, we draw a vector from the barycenter of $\sigma$ to the barycenter of $\mathcal{V}(\sigma)$ for each $\sigma\in\operatorname*{Dom\,}\mathcal{V}\setminus\operatorname*{Crit\,}\mathcal{V}$. If $\sigma\in\operatorname*{Crit\,}\mathcal{V}$, then we color the critical simplex in red. In the Figure 3, we have some examples of combinatorial dynamical system and some counter-examples at Figure 2.

This definition is useful in our minimization problem.

A multivalued map is a map $F:X\to P(X)$ where $P(X)$ is the power set of $X$. We write a multivalued map by $F:X\multimap X$.

$\Pi_{\mathcal{V}}$ induces the dynamics in combinatorial dynamical systems.

We define a cycle to be a solution $\varrho$ with $I=[0,n]\cap\mathbb{Z}$ such as $\varrho(0)=\varrho(n)$. We say a cycle is elementary, if every simplex is unique in $\varrho(i)$ for $i=1,2,\ldots,n-1$. The image of a cycle has $n$-simplex and $(n+1)$-simplex or a critical simplex. Because the only way to go up in dimension is from a simplex in $\operatorname*{Dom\,}\mathcal{V}\setminus\operatorname*{Crit\,}\mathcal{V}$ and we cannot have two simplices $\in\operatorname*{Dom\,}\mathcal{V}\setminus\operatorname*{Crit\,}\mathcal{V}$ in a row inside a solution. We denote a $d$-cycle where $d$ is the dimension of simplex in $\operatorname*{Dom\,}\mathcal{V}\cap\operatorname*{Im\,}\varrho$ and $\operatorname*{Crit\,}\mathcal{V}\cap\operatorname*{Im\,}\varrho=\emptyset$. We can use the strongly connected components from the directed graph of $\Pi_{\mathcal{V}}$ to understand the recurrent dynamics of $\mathcal{V}$. This will help us to study the method in the experiments. We say that a cycle $\varrho$ self-intersect at $\tau$, if $\operatorname*{card\,}(\operatorname*{Im\,}\varrho\cap\Pi_{\mathcal{V}}(\tau))>1$.

In this section, we want to construct a simplicial complex. We remind the dataset is $X\in\mathbb{R}^{d}$. For each $x\in X$, there is an associate vector $\dot{x}\in\mathbb{R}^{n}$. In this article, we will show two different ways to construct a simplicial complex : the Delaunay complex [4] and the Dowker complex [8].

The Delaunay complex works better if the sampling of the data is uniform. When the sampling is not uniform, this causes a great variation in the volume of $n$-simplices. It is harder to analyze the data. The Dowker complex is a solution for a non-uniform sampling of finite vector field data.

For the purpose of this paper, we use $X$ to store data and we need to choose the set $Y$ and a relation $R$ between $X$ and $Y$.

In this section, we define two ways of assigning a vector to each simplex. We construct an application $V:K\to\mathbb{R}^{n}$.

Let $K$ be a Delaunay complex. We compute a vector for a simplex by taking an average of vectors from the vertices of the simplex. More precisely, let $\sigma=[x_{0},x_{1},\ldots,x_{n}]$:

Let $K$ be a Dowker complex. Let $X$ and $\dot{X}$ from the data and $Y$ a set and a relation $R$ between $X$ and $Y$. We define an application $w:K\to X$ by $w(\sigma)=\{\dot{x}\in\dot{X}\mid\text{if for all }y\in\sigma,xRy\}$.

We assign a vector to a simplex $\sigma=[x_{0},x_{1},\ldots,x_{n}]$:

In this section, we describe the matching algorithm. We minimize a linear program with binary variables and linear equality constraints.

First, let’s define the variables. Let $N$ the number of simplices and $x_{i}$ the simplex where $0\leq i<N$. We define a matrix $A\in M_{N}(\{0,1\})$ of dimensions $N\times N$ where the entries are binary values. We call $A$ the matching matrix. We do the matching as follows :

• •

  If $a_{ij}=1$, match $x_{i}$ to $x_{j}$ $(\mathcal{V}(x_{i})=x_{j})$

• •

  If $a_{ij}=0$, do not match $x_{i}$ to $x_{j}$ $(\mathcal{V}(x_{i})\neq x_{j})$

Now, let us define the matrix $C\in M_{N}(\mathbb{R})$ called the cost matrix. Let $V:K\to\mathbb{R}^{n}$ be the map that takes a simplex and returns the vector value from the data. Let $b:K\to\mathbb{R}^{n}$ be the map sending each simplex to its barycenter and $W:K\times K\to\mathbb{R}^{n}$ be given by $W(x_{i},x_{j})=b(x_{j})-b(x_{i})$. Then, $W(x_{i},x_{j})$ is a vector that starts from the barycenter of $x_{i}$ and ends at the barycenter of $x_{j}$. The main idea is to compare the vector $V(x_{i})$ to the vector $W(x_{i},x_{j})$ when the matching is admissible. Given $x_{i}\neq x_{j}$, the matching is admissible if $x_{i}<x_{j}$ and $\dim x_{i}+1=\dim x_{j}$. We use the cosine distance to compare them. It is defined as follows:

where $\theta$ is the angle between $x$ and $y$. If $d(x,y)=0$, then $x$ and $y$ are parallel in the same direction. If $d(x,y)=1$, then $x$ and $y$ are perpendicular. If $d(x,y)=2$, then $x$ and $y$ are parallel in opposite directions. We set $c_{ij}=d(V(x_{i}),W(x_{i},x_{j}))$ when $x_{i}$ and $x_{j}$ is an admissible matching and $V(x_{i})\neq 0$.

If $V(x_{i})=0$ and $a_{ij}$ is an admissible matching, then $c_{ij}=2$. Indeed, $d(x,0)=1$ for every $x\in\mathbb{R}^{d}$. This means that all vectors are perpendicular to $\vec{0}$. But $x_{i}$ should be a critical simplex. By setting higher value for his cost, it has a higher chance that the solution will set this simplex to be critical.

If $i=j$, then we set to value $c_{ii}$ to $\alpha\in[0,2]$. $\alpha$ is a parameter choose by the user. If the $\alpha$ value is low, then we have more critical simplices. If the $\alpha$ value is high, then we have less critical simplices.

Let us explain the geometric interpretation of the parameter $\alpha$. There exists $\beta\in[-1,1]$ such as $\alpha=1-\beta$. Fix a simplex $x_{i}$ and consider all the admissible matching $a_{ij}$. Suppose that for all $c_{ij}>\alpha$ and let $\theta_{j}$ the angle between $V(x_{i})$ and $W(x_{i},x_{j})$. We obtain:

where $\arccos(\beta)$ represents the critical angle. If for all $\theta_{j}>\arccos(\beta)$, then the minimization problem (9) put simplex $x_{i}$ is a critical simplex or it matches with another simplex of lower dimensions.

If the matching is not admissible and $i\neq j$, then $C_{ij}=\max(2\alpha+1,3)$.

Finally, we obtain this equality for the entries of the matrix $C$ :

Finally, we obtain the following minimization linear problem with binary variables and linear equality constraints:

Let us explain the double sum in the constraint for a fixed $k$. The sum $\sum_{i=0}^{N-1}a_{ik}$ counts the number of vectors going into $x_{i}$ i.e. $\mathcal{V}(x_{i})=x_{k}$. The $\sum_{j=0}^{N-1}a_{kj}$ counts the number of vectors going out of $x_{i}$ i.e $\mathcal{V}(x_{k})=x_{i}$. We remove the term $a_{kk}$ because it is counted twice.

If $A$ is not an admissible matching for a combinatorial dynamical system, then we can always find a matrix $B$ that satisfies the constraint of (9), and $f(B)<f(A)$.

We can use the proposition (5.2) to transform $A$ to an admissible matching with a simple procedure by setting simplices in inadmissible matching too critical.

Let us explain the meaning of the value of $f(A)$ of the problem (9). Let $A$ be a solution of (9) and suppose that $V(x_{i})\neq\vec{0}$ for all $i$. Let $\mathcal{I}$ be the set of $(i,j)$ such that $a_{ij}=1$ with $i\neq j$. Let $\mathcal{K}$ be the set of $k$ such that $a_{kk}=1$.

where $|\mathcal{I}|$ is the number of matchings, $|\mathcal{K}|$ is the number of critical simplices and the sum in the middle is the sum of the cosine angle between $V(x_{i})$ and $W(x_{i},x_{j})$. If $\alpha$ is high, then the minimization will set more admissible matching. If $\alpha$ is low, then the minimization will set more critical simplices.

If our problem has a lot of simplices, we could only consider the variables $a_{ij}$ such as $(x_{i},x_{j})$ is an admissible matching. This reduces greatly the number of variables for the minimization problem (9). Let’s define the minimization problem with reduced binary variables.

Let $z$ be a vector such that $z_{k}$ is assigned to an admissible matching $(x_{i},x_{j})$ and $z_{k}\in\{0,1\}$. Let $m$ be the number of variables in $z$. Let $c$ be the vector with $c_{k}=c_{ij}$ for the variable $z_{k}$. Let $D\in M_{N,m}(\{0,1\})$ the constraint matrix. We define the entries of $D$ as follows. Let $x_{i}$ be a simplex and $z_{j}$ be assigned to the matching $x_{a}\to x_{b}$. Then $D_{i,j}=1$, if $i=a$ or $i=b$. Otherwise $D_{i,j}=0$. We obtain the new minimization problem :

We put a lower bound and an upper bound to the number of variables of the minimization problem (10). We can now easily show the next Lemma 5.3.