Loading...
Searching...
No Matches
Persistent Cohomology

## Classes

class | Gudhi::persistent_cohomology::Persistent_cohomology< FilteredComplex, CoefficientField >
| Computes the persistent cohomology of a filtered complex. More...
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...

## Functions

template<class FiltrationRange, class OutputFunctor, class Compare = std::less<>>
void | Gudhi::persistent_cohomology::compute_persistence_of_function_on_line (FiltrationRange const &input, OutputFunctor &&out, Compare &&lt={})
| Computes the persistent homology of the sublevelsets of a PL function defined on \(\mathbb{R}\) in linear time.

## Detailed Description

Author
  Clément Maria

Computation of persistent cohomology using the algorithm of [DBLP:journals/dcg/SilvaMV11] and [DBLP:conf/compgeom/DeyFW14] and the Compressed Annotation Matrix implementation of [DBLP:conf/esa/BoissonnatDM13] . Some special cases using different algorithms are also provided at the end of this page.

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:

- type `Indexing_tag`, which is a model of the concept `IndexingTag`, describing the nature of the indexing scheme,
- type Simplex_handle to manipulate simplices,
- method `int dimension(Simplex_handle)` returning the dimension of a simplex,
- type and method `Boundary_simplex_range boundary_simplex_range(Simplex_handle)` that returns a range giving access to the codimension 1 subsimplices of the input simplex, as-well-as the coefficients \((-1)^i\) in the definition of the operator \(\partial\). The iterators have value type `Simplex_handle`,
- type and method `Filtration_simplex_range filtration_simplex_range ()` that returns a range giving access to all the simplices of the complex read in the order assigned by the indexing scheme,
- type and method `Filtration_value filtration (Simplex_handle)` that returns the value of the filtration on the simplex represented by the handle.

# 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 [Munkres-elementsalgtop1984] for an introduction to homology theory and to [DBLP:books/daglib/0025666] 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 [DBLP:journals/dcg/ZomorodianC05] , and zigzag ones \(\bullet \longrightarrow \bullet \longleftarrow \cdots \longrightarrow \bullet \longleftarrow \bullet \) in zigzag persistent homology [DBLP:journals/focm/CarlssonS10]. 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.

- Rips_complex/rips_persistence.cpp computes the Rips complex of a point cloud and outputs its persistence diagram.
  $> ./rips_persistence ../../data/points/tore3D_1307.off -r 0.25 -m 0.5 -d 3 -p 3
  The complex contains 177838 simplices
  and has dimension 3
  3 0 0 inf
  3 1 0.0983494 inf
  3 1 0.104347 inf
  3 2 0.138335 inf

More details on the Rips complex utilities dedicated page.

- Persistent_cohomology/rips_multifield_persistence.cpp computes the Rips complex of a point cloud and outputs its persistence diagram with a family of field coefficients.

- Rips_complex/rips_distance_matrix_persistence.cpp computes the Rips complex of a distance matrix and outputs its persistence diagram.

The file should contain square or lower triangular distance matrix with semicolons as separators. The code do not check if it is dealing with a distance matrix. It is the user responsibility to provide a valid input. Please refer to data/distance_matrix/lower_triangular_distance_matrix.csv for an example of a file.

More details on the Rips complex utilities dedicated page.

- Rips_complex/rips_correlation_matrix_persistence.cpp computes the Rips complex of a correlation matrix and outputs its persistence diagram.

Note that no check is performed if the matrix given as the input is a correlation matrix. It is the user responsibility to ensure that this is the case. The input is to be given either as a square or a lower triangular matrix. Please refer to data/correlation_matrix/lower_triangular_correlation_matrix.csv for an example of a file.

More details on the Rips complex utilities dedicated page.

- Alpha_complex/alpha_complex_3d_persistence.cpp computes the persistent homology with \(\mathbb{Z}/2\mathbb{Z}\) coefficients of the alpha complex on points sampling from an OFF file.
  $> ./alpha_complex_3d_persistence ../../data/points/tore3D_300.off -p 2 -m 0.45
  Simplex_tree dim: 3
  2 0 0 inf
  2 1 0.0682162 1.0001
  2 1 0.0934117 1.00003
  2 2 0.56444 1.03938

More details on the Alpha complex utilities dedicated page.

CGAL can be forced to compute the exact values, it is slower, but it is necessary when points are on a grid for instance (the fast version --fast would give incorrect values).

$> ./alpha_complex_3d_persistence ../../data/points/sphere3D_pts_on_grid.off --exact -p 2 -m 0.1
Simplex_tree dim: 3
2 0 0 inf
2 2 0.0002 0.2028

It can also compute the persistent homology with \(\mathbb{Z}/2\mathbb{Z}\) coefficients of the weighted alpha complex on points sampling from an OFF file and a weights file.

$> ./alpha_complex_3d_persistence ../../data/points/tore3D_300.off
--weight-file ../../data/points/tore3D_300.weights -p 2 -m 0.45
Simplex_tree dim: 3
2 0 -1 inf
2 1 -0.931784 0.000103311
2 1 -0.906588 2.60165e-05
2 2 -0.43556 0.0393798

One can also compute the persistent homology with \(\mathbb{Z}/2\mathbb{Z}\) coefficients of the periodic alpha complex on points sampling from an OFF file. The second parameter is a Iso-cuboid file with coordinates of the periodic cuboid. Note that the lengths of the sides of the periodic cuboid have to be the same.

$> ./alpha_complex_3d_persistence ../../data/points/grid_10_10_10_in_0_1.off
--cuboid-file ../../data/points/iso_cuboid_3_in_0_1.txt -p 3 -m 1.0
Simplex_tree dim: 3
3 0 0 inf
3 1 0.0025 inf
3 1 0.0025 inf
3 1 0.0025 inf
3 2 0.005 inf
3 2 0.005 inf
3 2 0.005 inf
3 3 0.0075 inf

In order to compute the persistent homology with \(\mathbb{Z}/2\mathbb{Z}\) coefficients of the periodic alpha complex on weighted points from an OFF file. The additional parameters of this program are:
(a) The file with the weights of points. The file consist of a sequence of numbers (as many as points). Note that the weight of each single point have to be bounded by 1/64 times the square of the cuboid edge length.
(b) A Iso-cuboid file with coordinates of the periodic cuboid. Note that the lengths of the sides of the periodic cuboid have to be the same.

$> ./alpha_complex_3d_persistence ../../data/points/shifted_sphere.off
--weight-file ../../data/points/shifted_sphere.weights
--cuboid-file ../../data/points/iso_cuboid_3_in_0_10.txt -p 3 -m 1.0
Simplex_tree dim: 3
3 0 -0.0001 inf
3 1 16.0264 inf
3 1 16.0273 inf
3 1 16.0303 inf
3 2 36.8635 inf
3 2 36.8704 inf
3 2 36.8838 inf
3 3 58.6783 inf

- Alpha_complex/alpha_complex_persistence.cpp computes the persistent homology with \(\mathbb{Z}/p\mathbb{Z}\) coefficients of the alpha complex on points sampling from an OFF file.
  $> ./alpha_complex_persistence -r 32 -p 2 -m 0.45 ../../data/points/tore3D_300.off
  Alpha complex is of dimension 3 - 9273 simplices - 300 vertices.
  Simplex_tree dim: 3
  2 0 0 inf
  2 1 0.0682162 1.0001
  2 1 0.0934117 1.00003
  2 2 0.56444 1.03938

More details on the Alpha complex utilities dedicated page.

- Persistent_cohomology/plain_homology.cpp computes the plain homology of a simple simplicial complex without filtration values.

# Special cases

In order to compute the persistent homology of a piecewise-linear function on \(\mathbb{R}\), the standard strategy would be to create a path complex (special case of cubical or simplicial complex), define a lower-star filtration on it, and finally apply a general persistence algorithm. compute_persistence_of_function_on_line() computes this persistence diagram directly on the function in linear time using the algorithm of [arxivpers1d] .

#include <gudhi/Persistence_on_a_line.h>
#include <vector>
#include <iostream>
int main() {
std::vector<float> data{ 0., 1.5, .7, 2.8, 3.1, -1., 2. };
Gudhi::persistent_cohomology::compute_persistence_of_function_on_line(data,
[](float b, float d){ std::cout << b << ' ' << d << '\n'; });
}
Gudhi::persistent_cohomology::compute_persistence_of_function_on_line
void compute_persistence_of_function_on_line(FiltrationRange const &input, OutputFunctor &&out, Compare &&lt={})
Computes the persistent homology of the sublevelsets of a PL function defined on in linear time.
Definition Persistence_on_a_line.h:37

outputs

0.7 1.5
0 3.1
-1 inf

## Function Documentation

## compute_persistence_of_function_on_line()

template<class FiltrationRange, class OutputFunctor, class Compare = std::less<>>

void Gudhi::persistent_cohomology::compute_persistence_of_function_on_line | ( | FiltrationRange const & | input,
|  | OutputFunctor && | out,
|  | Compare && | lt = {} )

Computes the persistent homology of the sublevelsets of a PL function defined on \(\mathbb{R}\) in linear time.

Not all input values appear in the output (they would be part of pairs of length 0 with a simplicial / cubical complex).

Parameters

  [in] | input | Range of filtration values.
  [out] | out | Functor that is called as out(birth, death) for each persistence pair. By convention, it is also called one last time on the minimum and std::numeric_limits<Filtration>::infinity().
  [in] | lt | Functor that compares 2 filtration values.

Author
  Marc Glisse