|
CGAL 6.3-dev - Homological Discrete Vector Fields
|
Algebraic topology, introduced more than a century ago, studies topological spaces using algebraic tools derived from them (e.g. groups). Since the 70's and 80's, pioneering works (MacLane, Hilton, Munkres...) paved the way to computational homology, which studies the "holes" of an object. In particular, Munkres introduced an algorithm computing Betti numbers based on the pseudo-diagonalization of boundary matrices (Smith Normal Form).
In the 90's, persistent homology emerged independently through the work of H. Edelsbrunner et al. (North Carolina), P. Frosini et al. (Bologna), and V. Robins (Colorado), extending the study of homology to sequences of complexes (filtrations). This later theory proved to have a wide range of applications in topological data analysis and hence quickly developed and spread in the scientific community. In parallel, in the late 80's, R. Forman defined a discrete version of Morse theory for CW-complexes, while F. Sergeraert introduced effective homology theory.
In [AGL, 2017], A. Gonzalez-Lorenzo et al. defined the homological discrete vector field (which we refer to as HDVF in the present package), a combinatorial object that generalizes previous approaches. Precisely, HDVFs combine discrete Morse and effective homology theory and fully encode homology information (homology groups decomposition, Betti numbers, homology generators) for cellular complexes. HDVFs encompass discrete Morse theory, effective homology and Smith Normal form, and: persistent homology can be computed with HDVFs (see [AGL, 2016]), relative homology and Alexander duality (see [AGL, 2025]).
Figure 99.1 HDVF on a twirl model. Left: a perfect HDVF over the model; Middle: Homology generators associated to this HDVF; Right: Corresponding cohomology generators.
Unlike other main stream state of art approaches and librairies (largely based on persistent homology), HDVFs provide a framework for "geometric" homology and cohomology computation, where holes are not only enumerated, but also "localized" (through homology, cohomology generators, annotations...).
The HDVF package is dedicated to homology and cohomology computation for discrete objects and provides tools to compute:
Homology and cohomology are well know topological invariants which accounts for the holes of an object using commutative groups built from the object. In Mathematics, homology and cohomology can be defined for general Hausdorff topological spaces; we speak then about "singular homology and cohomology". However, such a general definition is not computable and thus, homology/cohomology computation requires a discretization of spaces into cells of various dimensions. Such a discretization is called a complex:
Actually, a set of cells is called a complex \(K\) when:
Figure 99.2 Illustration of complexes. Left: a simplicial complex of dimension 3; Right: A cubical complex of dimension 3.
In order to compute homology and cohomology, algebraic objects are built from such "geometric" complexes, namely chain complexes.
In order to define this algebraic structure, one first need to chose a ring of coefficients \(A\) ( \(A\) is often taken to be \(Z\) or a \(\mathbb Z/p\mathbb Z\) field).
Given a complex \(K\) of dimension \(d\), a chain complex \(C\) is:
\[C = \cdots C_{q+1} \xrightarrow{\partial_{q+1}} C_q \xrightarrow{\partial_{q}} C_{q-1} \xrightarrow{\partial_{q-1}} \cdots \to C_1 \xrightarrow{\partial_1} C_0 \xrightarrow{\partial_0 = 0} 0\]
a sequence of morphisms between chain groups, called boundary morphisms \(\partial_q\,:\, C_q\to C_{q-1}\) for any \(0\leqslant q \leqslant d\), "mimicking" algebraically the geometric boundary and satisfying
\[\partial_q\partial_{q+1} = 0\]
Coming back to the example of Figure 99.3, as we will see in section Simplicial chain complexes, the boundary of the edge \(e_{45}\) is the 0-chain \(v_5-v_4\) (ordering is given by vertices indices). Hence, on easily gets that \(\partial_1(\gamma_1)=0\) and \(\partial_1(\gamma_2)=v_8-v_4\), which is a very intuitive result.
Figure 99.3 Examples of chains representation in a simplicial complex (with \(A = \mathbb Z\)). Pink: representation the 1-chain (of edges) \(\gamma_1 = e_{24}+e_{46}-e_{26}\); Blue: representation of the 1-chain \(\gamma_2 = e_{45}+e_{56}+e_{67}+e_{78}\).
The definition of the boundary operator depends on the underlying complex, it is detailed in next sections for simplicial and cubical complexes respectively.
Notation
Given a chain \(\gamma\in C_q\) and \(\sigma\) a \(q\)-cell, we denote by \(\langle\gamma,\sigma\rangle\) the coefficient of \(\sigma\) in \(\gamma\in C_q\).
An abstract simplicial complex of dimension \(d\) is built from:
A geometric simplicial complex equips vertices with coordinates in \(\mathbb R^q\) so that \(q\)-simplices are convex hulls of \(q+1\) points.
Given a simplicial complex (abstract or geometric) \(K\), the associated chain complex \((C,\partial)\), called a simplicial chain complex is defined as follows:
The \(q\)-th boundary morphism is defined over the \(q\)-simplices (ie. the basis) by:
\[\partial_q : \begin{array}{rcl} C_q & \to & C_{q-1} \\ \langle v_0,\ldots,v_{q}\rangle & \mapsto & \sum_{i=0}^q (-1)^i\cdot \langle v_0,\ldots,\hat{v_i}, \ldots, v_{q}\rangle \\ \end{array} \]
where \(\hat{v_i}\) means that the \(i\)-th vertex has been discarded.
For instance, in our previous example:
A cubical complex of dimension \(d\) is a set of cells defined as cartesian products:
\[\sigma = [n_1,n_1+\delta_1]\times\cdots \times [n_d,n_d+\delta_d]\]
with \(n_i\in \mathbb N\) and \(\delta_i\in\{0,1\}\) for \(i=1\ldots d\). The dimension of such a cell is \(\sum_{i=1}^d \delta_i\). As stated in previous section, a complex is closed under the "face" operation (if a cell belongs to the complex, so do its faces).
Khalimsky coordinates** associate to each cell, whatever its dimension, a unique coordinate in \(\mathbb N^d\) defined as:
\[\mathrm{khal}(\sigma) = (2 n_1+\delta_1,\ldots, 2 n_d+\delta_d)\]
The dimension of a cell in this coordinate system is thus the number of odd coordinates.
Figure 99.4 A cubical complex of dimension 3.
For instance, in the example above:
Given a cubical complex \(K\), the associated chain complex \((C,\partial)\), called a cubical chain complex is defined as follows:
\[\partial_q(x_1,\ldots,x_d) = \sum_{\substack{i=1\\i\text{ odd}}}^d (-1)^{i+1}\Big((x_1,\ldots, x_i+1,\ldots, x_d) - (x_1,\ldots, x_i-1,\ldots, x_d)\Big)\]
For instance, in the example above:

In the "mathematical world", singular cohomology is defined on dual groups \(C^q = C_q^* = \mathrm{Hom}(C_q,A)\) with coboundary morphisms: \(\partial^q\,:\, C^q \to C^{q+1} = \partial_q^*\).
However in our discrete setting of finite complexes, a space and its dual can be identified. Hence cohomology can be defined in a more intuitive way:
\[C^* = \cdots C^{q+1} \xleftarrow{\partial^{q}} C^q \xleftarrow{\partial^{q-1}} C^{q-1} \leftarrow \cdots \leftarrow C^2 \xleftarrow{\partial^1} C^1 \xleftarrow{\partial^0} C^0\]
\[\partial^q\partial^{q-1} = 0\]
The following figure illustrates the coboundary morphism
Figure 99.5 Illustration of the coboundary morphism (with \(A = \mathbb Z\)) Pink: coboundary of vertex \(v_6\) ( \(\partial^0(v_6) = e_{26} + e_{46}+e_{56} - e_{67} - e_{68}\)); Blue: coboundary of edge \(e_{24}\) ( \(\partial^1(e_{24} ) = f_{246} - f_{234}\)).
Homology is a topological invariant characterizing the holes of an object of various dimension. What is a hole?
Figure 99.6 Illustration of the holes of a double torus. Black: 1 connected component (dimension 0); Red: 4 holes of dimension 1; Blue 1 cavity of dimension 2.
Let us now come back to our simplicial complex example:
Figure 99.7 Cycles on a simplicial complex. Blue: this cycle is the boundary of \(f_{234}+f_{246}\); Pink: this cycle is not a boundary.
This example suggests that holes are delineated by cycles which are not a boundaries:
\[Z_q(C) = \ker(\partial_q) \]
\[B_q(C) = \mathrm{Im}(\partial_{q+1}) \]
\[H_q(C) = Z_q(C)/B_q(C) \]
For finite complexes, these groups are finitely generated and we have the following decomposition (theorem of decomposition of finitely generated groups):
\[H_q(C) = A^{\beta_q}\oplus A/\lambda_1A\oplus \cdots \oplus A/\lambda_k A \]
where:
Let us assume homology groups have no torsion; homology can be computed "at different levels":
Most libraries focus on persistent homology computation for topological data analysis (see section Persistent homology), which is a "level 1" homology computation. The HDVF package is dedicated to a "level 2" homology computation, which is computationally more complex but provides "geometric" informations about holes (generators, annotations...).
Starting from a cochain complex:
\[C^* = \cdots C^{q+1} \xleftarrow{\partial^{q}} C^q \xleftarrow{\partial^{q-1}} C^{q-1} \leftarrow \cdots \leftarrow C^2 \xleftarrow{\partial^1} C^1 \xleftarrow{\partial^0} C^0\]
one can define:
\[Z^q(C^*) = \ker(\partial^q) \]
\[B^q(C^*) = \mathrm{Im}(\partial^{q-1}) \]
\[H^q(C^*) = Z^q(C^*)/B^q(C^*) \]
Figure 99.8 Illustration of homology and cohomology generators for a simple 2D cubical complex \(C\) (computed with HDVFs). Left: both generators of \(H_1(C)\); Middle, right: both cohomology generators \(H^1(C)\) (for convenience, the dual of cohomology generators has been displayed with bulleted pink lines).
Figure 99.9 Cofaces representation of cohomology generators.
Figure Figure 99.8 and Figure 99.9 illustrate homology and cohomology generators in a simple cubical complex. Actually:
Therefore homology and cohomology provide isomorphic (and dual) results. Actually, the following proposition holds in finite dimension:
\[H^q(C^*) \sim H_q(C)\]
First results on the computation of discrete homology and cohomology date back to the 80's (see for instance [Munkres]). They are based on a diagonalisation of boundary matrices (called Smith Normal form). Nowadays, computational (co)homology approaches can be classified into three branches illustrated in figure Figure 99.10.
Figure 99.10 Overview of approaches in computational homology. HDVFs are in-between discrete Morse theory and effective homology (and they encompass persistent homology, relative homology and tri-partitions).
Effective homology considers homology computations from a categorical perspective ; its main results are theorems building functors providing a computation of homology for infinite spaces (locally effective spaces) starting from finite ones (effective spaces).
Among the tools of effective homology, reductions characterise how to map a (large) chain complex onto a (small) one with isomorphic homology groups. Formally, a reduction from a chain complex \(C\) to a chain complex \(C'\) is a triple of graded maps \((f,g,h)\):
\[\begin{array}{cccccc} \cdots & C_{q+1} & \substack{\xrightarrow{\partial_{q+1}}\\ \xleftarrow[h_{q}]{}} & C_{q} & \substack{\xrightarrow{\partial_{q}}\\ \xleftarrow[h_{q-1}]{}} & \cdots \\ & f_{q+1}\Big\downarrow \Big\uparrow g_{q+1} & & f_{q}\Big\downarrow \Big\uparrow g_{q} & & \\ \cdots & C'_{q+1} & \xrightarrow{\partial'_{q+1}} & C'_{q} & \xrightarrow{\partial'_{q}} & \cdots \\ \end{array} \]
such that:
\(h_{q+1} h_q = 0\), \(f_{q+1} h_{q} = 0\) and \(h_{q} g_q = 0\) for any \(q\)
\(C'\) is called the reduced complex and \(\partial'\) the reduced boundary.
Under these assumptions, the homology and cohomology groups of \(C\) and \(C'\) are isomorphic.
A reduction is perfect when the reduced boundary is null; then for any \(q\):
\[H_q(C) \sim g(C'_q)\]
in other words, homology groups are isomorphic to the image of the reduced complex by \(g\),
\[H^q(C) \sim f^*(C'_q)\]
and cohomology groups are isomorphic to the image of the reduced complex by \(f^*\).
Discrete Morse theory was introduced by Forman in the 90's as a combinatorial approach for homology computation directly inspired by Morse theory (on compact manifolds). He showed that in the discrete context, Morse functions are better defined through their gradient: a vector field defined over the complex connecting cells and one of their co-faces. In this context, gradients of Morse functions can be easily characterized by acyclicity conditions.
More precisely, given a complex \(K\), a discrete gradient vector field (called DGVF here after) can be built as follows:
The FILTR file format is a very simple text format encoding filtrations:
This section presents a brief introduction to HDVFs, see [AGL, 2016] for more details.
HDVFs are an "in-between" theory:
Let \(K\) be a complex (simplicial, cubical...) and let \((\mathscr C, \partial)\) be its associated chain complex.
Notation** Starting from now on, we will use \(\mathscr C\) for chain complexes and \(C\) for critical cells.
Formally a HDVF \(X=(P,S,C)\) is a partition of the cells of \(K\):
\[K = P\cup S\cup C\]
with \(P\) primary cells, \(S\) secondary cells and \(C\) critical cells, such that the sub-matrix:
\[\partial (S)|_P\text{ is invertible.} \]
where \(\partial (S)|_P\) means that the matrix of \(\partial\) is restricted to columns of secondary cells and rows of primary cells.
As stated earlier, this definition is both combinatorial (partition of cells) and algebraic (invertibility of a sub-matrix) but it cannot be simplified or reduced to either of these approaches.
Given such an HDVF \(X=(P,S,C)\), we can define the following associated reduction \((f,g,h)\):
\[\begin{array}{cccccc} \cdots & \mathscr C_{q+1} & \substack{\xrightarrow{\partial_{q+1}}\\ \xleftarrow[h_{q}]{}} & \mathscr C_{q} & \substack{\xrightarrow{\partial_{q}}\\ \xleftarrow[h_{q-1}]{}} & \cdots \\ & f_{q+1}\Big\downarrow \Big\uparrow g_{q+1} & & f_{q}\Big\downarrow \Big\uparrow g_{q} & & \\ \cdots & C_{q+1} & \xrightarrow{\mathrm d_{q+1}} & C_{q} & \xrightarrow{\mathrm d_{q}} & \cdots \\ \end{array} \]
\(\mathrm d\) is the reduced boundary (over critical cells) and the reduction is defined as follows:
\[\begin{array}{c} \ \ \ \ \ \ \ \ \ \ P_q \ \ \ \ S_q \ \ \ \ C_q \\ \begin{array}{c} P_{q+1} \\ S_{q+1} \\ C_{q+1} \\ \end{array} \begin{array}{|c|c|c|} \hline 0 & 0 & 0 \\ \hline H_q & 0 & 0 \\ \hline 0 & 0 & 0 \\ \hline \end{array} \end{array} \]
with\[H_q = (\partial (S_{q+1})|_{P_q})^{-1}\]
.\[\begin{array}{c} \ \ \ \ \ \ P_q \ \ \ \ S_q \ \ \ \ C_q \\ \begin{array}{c} C_q \\ \end{array} \begin{array}{|c|c|c|} \hline F_q & 0 & \mathrm{Id} \\ \hline \end{array} \end{array} \]
with\[ F_q = - \partial(S_{q+1})|_{C_q}\cdot H_q\]
\[\begin{array}{c} \ \ \ \ \ \ C_q \\ \begin{array}{c} P_q \\ S_q \\ C_q \\ \end{array} \begin{array}{|c|} \hline 0 \\ \hline G_q \\ \hline \mathrm{Id} \\ \hline \end{array} \end{array} \]
with\[ G_q = - H_{q-1} \cdot \partial(C_{q})|_{P_{q-1}}\]
\[\begin{array}{c} \ \ \ \ \ \ C_q \\ \begin{array}{c} C_{q-1} \\ \end{array} \begin{array}{|c|} \hline DD_q \\ \hline \end{array} \end{array} \]
with\[ D_q = \partial(C_{q})|_{C_{q-1}} + F_{q-1} \cdot \partial(C_{q})|_{P_{q-1}} = \partial(C_{q})|_{C_{q-1}} + \partial(S_{q})|_{C_{q-1}} \cdot G_q \]
Therefore the HDVF "reduces" the complex to a smaller complex over critical cells.
A HDVF is called perfect when the reduced boundary is null, then for any \(q \in \{0\ldots d\}\):
Hence a perfect HDVF computes homology and provides a rich homological information.
Moreover, the reduction provides various informations on cycles and co-cycles:
\[\text{if }f(\gamma) = \sum_i \alpha_i\cdot \sigma_i,\ \ \ \sigma_i\in C_q\]
\[\text{then }\ \ \ \gamma = \sum_i \alpha_i\cdot g(\sigma_i) + \beta,\ \ \ \beta \in B_q(\mathscr C)\]
\[\text{if }g^*(\gamma) = \sum_i \alpha_i\cdot \sigma_i,\ \ \ \sigma_i\in C^q\]
\[\text{then }\ \ \ \gamma = \sum_i \alpha_i\cdot f^*(\sigma_i) + \beta,\ \ \ \beta \in B^q(\mathscr C)\]
Annotations and co-annotations provide convenient tests to decide if to cycles (resp. co-cycles) belong to the same homology (resp. cohomology) class:
Figure Figure 99.8 shows an example of HDVF together with corresponding homology and cohomology generators. In all the package, we use the following colors convention:
Let us point out that HDVFs can be represented in a "discrete Morse theory" style, with arrows (ie. a vector field) pairing a primary and a secondary cell among its co-faces (the vector field associated to a HDVF is not unique). But DGVF are a strict subset of HDVFs:
The following figures show an HDVF and an associated vector field:

And the following figure exhibits the vector field representation of a HDVF with a cycle (on the right, the cycle is highlighted in purple):

Hence this vector field is a valid HDVF ( \(\partial(S)|_P\) is invertible) but it is not a DGVF.
HDVFs can be computed using previous matrix expression; however, Aldo Gonzalez-Lorenzo has shown that several operations on HDVF can be introduced, not only to built, but also transform HDVFs.
\[ A(X) = \Big(P\cup\{\gamma_1\}, S\cup\{\gamma_2\}, C\backslash \{\gamma_1, \gamma_2\}\Big)\]
and the operation is valid (ie. produces an HDVF) if and only if:\[ \langle \mathrm d(\gamma_2),\gamma_1\rangle \text{ is invertible}\]
Figures below illustrate this operation on a cubical chain complex: (left) an HDVF such that \((\gamma_1,\gamma_2)\) meet the A condition, (right) the HDVF obtained after \(A(\gamma_1,\gamma_2)\).

\[ R(X) = \Big(P\backslash\{\pi\}, S\backslash\{\sigma\}, C\cup \{\pi, \sigma\}\Big)\]
and the operation is valid (ie. produces an HDVF) if and only if:\[ \langle h(\pi),\sigma\rangle \text{ is invertible}\]
Operations A and R are inverse one another.
\[ M(X) = \Big(P\backslash \{\pi\} \cup\{\gamma\}, S, C\backslash \{\gamma\}\cup \{\pi\}\Big)\]
and the operation is valid (ie. produces an HDVF) if and only if:\[ \langle \mathrm f(\pi),\gamma\rangle \text{ is invertible}\]
The M operation modifies the homology generator associated to \(\gamma\) (while preserving is associated cohomology generator). The following figure illustrates the M operation.
Figure 99.11 M operation on a cubical complex \(K\). Left: perfect HDVF over \(K\) with cells \((\pi, \gamma)\) meeting the M operation condition (blue: homology generator associated with \(\gamma\), pink: cohomology generator associated with \(\gamma\)); Right: perfect HDVF obtained with \(M(\pi,\gamma)\) and updated generators (associated to \(\pi\) which is now critical).
\[ W(X) = \Big(P, S\backslash\{\sigma\}\cup \{\gamma\}, C\backslash \{\gamma\}\cup \{\sigma\}\Big)\]
and the operation is valid (ie. produces an HDVF) if and only if:\[ \langle \mathrm g(\gamma),\sigma\rangle \text{ is invertible}\]
The W operation modifies the cohomology generator associated to \(\gamma\) (while preserving is associated homology generator). The following figure illustrates the W operation.
Figure 99.12 W operation on a cubical complex \(K\). Left: perfect HDVF over \(K\) with cells \((\sigma, \gamma)\) meeting the W operation condition (blue: homology generator associated with \(\gamma\), pink: cohomology generator associated with \(\gamma\)); Right: perfect HDVF obtained with \(W(\pi,\gamma)\) and updated generators (associated to \(\sigma\) which is now critical).
\[ MW(X) = \Big(P\backslash\{\pi\}\cup \{\sigma\}, S\backslash\{\sigma\}\cup \{\pi\}, C\Big)\]
and the operation is valid (ie. produces an HDVF) if and only if:\[ \langle \partial h(\pi),\sigma\rangle \text{ and } \langle h\partial(\sigma),\pi\rangle\text{ are invertible}\]
The MW operation modifies both homology and cohomology generators. The following figure illustrates the W operation.
Figure 99.13 MW operation on a cubical complex \(K\). Top: perfect HDVF over \(K\) with cells \((\pi_1, \sigma_1)\) and \((\pi_2, \sigma_2)\) meeting the MW operation condition (blue: homology generators, pink: cohomology generators); Down, left: perfect HDVF obtained with \(MW(\pi_1,\sigma_1)\) and updated generators (a cohomology generator is modified); Down, right: perfect HDVF obtained with \(MW(\pi_2,\sigma_2)\) and updated generators (a homology generator is modified).
Recent works by Yann-Situ Gazull [YSG1], [YSG2] proved that (when \(A\) is a field):
Hence, using appropriate combinations of such operations, one can change a HDVF until corresponding homology or cohomology generators meet a given basis or delineate a hole.
Let us consider the following simple cubical complex and a perfect HDVF (top) together with the three corresponding homology generators (bottom, highlighted in pink):


A W operation between cells of Khalimsky coordinates \(\sigma = (3,2)\) (CRITICAL) and \(\tau=(5,2)\) (SECONDARY) produces the following HDVF (homology generators did not change; note that cohomology generators are modified):


Then, a MW operation between cells of Khalimsky coordinates \(\sigma' = (4,1)\) (PRIMARY) and \(\tau=(3,2)\) (SECONDARY) produces the following HDVF where homology generators become "minimal":


This section describes the HDVF package implementing the theory described in previous sections.
In order to compute the homology/cohomology of a discrete object with an HDVF, the process is as follows:
Figure 99.14 Overview of homology/cohomology computation with the HDVF package.
The ring of coefficients must be a model of the IntegralDomainWithoutDivision concept:
The HDVF package provides several chain complexes: Abstract_simplicial_chain_complex, Geometric_simplicial_chain_complex and Cubical_chain_complex.
In order to build such a chain complex, discrete objects are first imported into a temporary combinatorial structure storing input cells. The chain complex is then built from this intermediate structure by adding all the faces of cells and computing the corresponding boundary matrix.
Let us point out that whatever the type of chain complex, cells are indexed along each dimension; hence a cell is identified by an index and a dimension.
Figure 99.15 Primal and dual constructions of cubical chain complexes from a binary volume. Left: a 3D binary volume; Middle: PRIMAL cubical (chain) complex associated to the volume; Right: DUAL cubical (chain) complex associated to the volume).
Figure taken from [AGL, 2016].
The SIMP file format is a very simple text format listing, encoding simplicial complexes. It enumerates simplices line by line (described by the indices of their vertices). The file doesn't need to provide an exhaustive enumeration of simplices (with all their faces), indeed, the simplicial chain complex constructors fill them with faces. Figure Figure 99.16 illustrate the format on a simple simplicial complex.
Figure 99.16 Example of simp file. Left: a simplicial complex; Right: associated simp files describing maximal simplices.
The CUB file format is a very simple text format encoding binary volumes:
The file doesn't need to provide an exhaustive enumeration of cells (with all their faces), indeed, the cubical chain complex constructors fill them with faces. Figure Figure 99.17 illustrate the format on a simple cubical complex.
Figure 99.17 Example of cub file. Left: a cubical complex; Right: associated cub files describing maximal cells.
An empty HDVF is built from a chain complex:
Several HDVF options are available:
The HDVF obtained is empty (all cells are critical). In order to compute homology/cohomology that is a perfect HDVF, the package provides two methods:
or
When the ring of coefficients is a field, these methods always produce a perfect HDVF. However for \(\mathbb Z\)-(co)homology (without torsion), the existence of complexes admitting no perfect HDVF is still an open question (and the answer is negative for "reasonable" objects, indeed we still have no counter example). The method is_perfect_hdvf() checks if a HDVF is perfect.
For specific applications, HDVFs can be built by iterating the A operation:
performs a pairing between the cells \(\gamma_1\) (index id1 in dimension q) and \(\gamma_2\) (index id2 in dimension q+1).
The package provide a family of methods to search for valid pairings:
How to extract (co)homological information then? Various solutions and output are available:
The HDVF file format is a simple text format used to save HDVFs. It relies on the OSM format described in section The OSM file format.
The following examples exhibit the computation of a perfect HDVF over a simplicial (resp. cubical) chain complex built from a .off file (resp. a .pgm file). Generators are then exported to .vtk. Example: HDVF/hdvf_simplicial.cpp
Example: HDVF/hdvf_cubical.cpp
All maps (boundary operator, \(f\), \(g\), \(h\) and \(\mathrm d\)) are stored in sparse matrices and chains are stored in sparse chains. The OSM library provides an implementation of the SparseMatrix and SparseChain concepts, that is sparse structures optimized for topological operations (block operations).
The structure is based on a mapped matrix implementation, hence, matrices and chains are either column or row major (CGAL::OSM::COLUMN or CGAL::OSM::ROW type).
In order to speed up both block operations and iterators (over non empty columns or row according to the type), a bitboard structure is used (inherited from chess programming community). Hence, in order to iterate over the major dimension of a matrix, one should actually iterate a bitboard (providing indices of non empty columns / rows). See Sparse_matrix_structure documentation for more details.
Iterating over sparse chains them comes to iterate over a map.
The following example builds a column major matrix, iterate over its non empty columns (ie. chains) and then iterate over each chain.
Example: HDVF/matrix_chain.cpp
All standard linear algebra operators are provided (and optimized according to the matrix/chain types).
The .osm file format is a simple text format to store OSM sparse matrices:
[AGL, 2017] Aldo Gonzalez-Lorenzo, Alexandra Bac, Jean-Luc Mari, Pedro Real. Allowing cycles in discrete Morse theory, Topology and its Applications, Volume 228, 2017, Pages 1-35.
[AGL, 2016] Aldo Gonzalez-Lorenzo. Computational Homology Applied to Discrete Objects. Discrete Mathematics [PhD]. Aix-Marseille UniversiteĢ; Universidad de Sevilla, 2016.
[AGL, 2025] Aldo Gonzalez-Lorenzo, Alexandra Bac and Yann-Situ Gazull. A constructive approach of Alexander duality. J Appl. and Comput. Topology 9, 2 (2025).
[YSG1, 2025] Yann-Situ Gazull, Aldo Gonzalez-Lorenzo and Alexandra Bac. Characterization of the computed homology and cohomology bases. DGMM 2025 (to appear).
[YSG2, 2025] Yann-Situ Gazull, Aldo-Gonzalez-Lorenzo and Alexandra Bac. Space of homological computations: connectivity and paths (submitted to Journal of Applied and Computational Topology).
[Munkres] J. Munkres. Elements of Algebraic Topology, Addison Wesley Publishing Company, (1984)