Persistent Cohomology

Classes

class  Gudhi::persistent_cohomology::Field_Zp
 Structure representing the coefficient field $\mathbb{Z}/p\mathbb{Z}$. More...
 
class  Gudhi::persistent_cohomology::Multi_field
 Structure representing coefficients in a set of finite fields simultaneously using the chinese remainder theorem. More...
 
class  Gudhi::persistent_cohomology::Persistent_cohomology< FilteredComplex, CoefficientField >
 Computes the persistent cohomology of a filtered complex. More...
 

Detailed Description

Author
Clément Maria

Computation of persistent cohomology using the algorithm of [9] and [10] and the Compressed Annotation Matrix implementation of [6]

The theory of homology consists in attaching to a topological space a sequence of (homology) groups, capturing global topological features like connected components, holes, cavities, etc. Persistent homology studies the evolution – birth, life and death – of these features when the topological space is changing. Consequently, the theory is essentially composed of three elements: topological spaces, their homology groups and an evolution scheme.

Topological Spaces

Topological spaces are represented by simplicial complexes. Let $V = \{1, \cdots ,|V|\}$ be a set of vertices. A simplex $\sigma$ is a subset of vertices $\sigma \subseteq V$. A simplicial complex $\mathbf{K}$ on $V$ is a collection of simplices $\{\sigma\}$, $\sigma \subseteq V$, such that $\tau \subseteq \sigma \in \mathbf{K} \Rightarrow \tau \in \mathbf{K}$. The dimension $n=|\sigma|-1$ of $\sigma$ is its number of elements minus 1. A filtration of a simplicial complex is a function $f:\mathbf{K} \rightarrow \mathbb{R}$ satisfying $f(\tau)\leq f(\sigma)$ whenever $\tau \subseteq \sigma$.

We define the concept FilteredComplex which enumerates the requirements for a class to represent a filtered complex from which persistent homology may be computed. We use the vocabulary of simplicial complexes, but the concept is valid for any type of cell complex. The main requirements are the definition of:

Homology

For a ring $\mathcal{R}$, the group of n-chains, denoted $\mathbf{C}_n(\mathbf{K},\mathcal{R})$, of $\mathbf{K}$ is the group of formal sums of n-simplices with $\mathcal{R}$ coefficients. The boundary operator is a linear operator $\partial_n: \mathbf{C}_n(\mathbf{K},\mathcal{R}) \rightarrow \mathbf{C}_{n-1}(\mathbf{K},\mathcal{R})$ such that $\partial_n \sigma = \partial_n [v_0, \cdots , v_n] = \sum_{i=0}^n (-1)^{i}[v_0,\cdots ,\widehat{v_i}, \cdots,v_n]$, where $\widehat{v_i}$ means $v_i$ is omitted from the list. The chain groups form a sequence:

\[\cdots \ \ \mathbf{C}_n(\mathbf{K},\mathcal{R}) \xrightarrow{\ \partial_n\ } \mathbf{C}_{n-1}(\mathbf{K},\mathcal{R}) \xrightarrow{\partial_{n-1}} \cdots \xrightarrow{\ \partial_2 \ } \mathbf{C}_1(\mathbf{K},\mathcal{R}) \xrightarrow{\ \partial_1 \ } \mathbf{C}_0(\mathbf{K},\mathcal{R}) \]

of finitely many groups $\mathbf{C}_n(\mathbf{K},\mathcal{R})$ and homomorphisms $\partial_n$, indexed by the dimension $n \geq 0$. The boundary operators satisfy the property $\partial_n \circ \partial_{n+1}=0$ for every $n > 0$ and we define the homology groups:

\[\mathbf{H}_n(\mathbf{K},\mathcal{R}) = \ker \partial_n / \mathrm{im} \ \partial_{n+1}\]

We refer to [17] for an introduction to homology theory and to [11] for an introduction to persistent homology.

Indexing Scheme

"Changing" a simplicial complex consists in applying a simplicial map. An indexing scheme is a directed graph together with a traversal order, such that two consecutive nodes in the graph are connected by an arrow (either forward or backward). The nodes represent simplicial complexes and the directed edges simplicial maps.

From the computational point of view, there are two types of indexing schemes of interest in persistent homology: linear ones $\bullet \longrightarrow \bullet \longrightarrow \cdots \longrightarrow \bullet \longrightarrow \bullet$ in persistent homology [21] , and zigzag ones $\bullet \longrightarrow \bullet \longleftarrow \cdots \longrightarrow \bullet \longleftarrow \bullet $ in zigzag persistent homology [7]. These indexing schemes have a natural left-to-right traversal order, and we describe them with ranges and iterators. In the current release of the Gudhi library, only the linear case is implemented.

In the following, we consider the case where the indexing scheme is induced by a filtration. Ordering the simplices by increasing filtration values (breaking ties so as a simplex appears after its subsimplices of same filtration value) provides an indexing scheme.

Examples

We provide several example files: run these examples with -h for details on their use, and read the README file.

GUDHI  Version 2.0.0  - C++ library for Topological Data Analysis (TDA) and Higher Dimensional Geometry Understanding. Generated on Wed Apr 19 2017 22:26:16 for GUDHI by doxygen 1.8.11