Effective homology
of a modified model


Aldo Gonzalez-Lorenzo
Aix-Marseille Université
LIS UMR 7020 CNRS

Introduction

How to recompute the homology of a model we have just modified?

Homology

  • Algebraic topology → homology
  • Linear algebra, algorithms in O(n³)
  • Invariants: Betti numbers (of holes)

Homology

Cell complex

Homology groups

Chain complex:

  • \(\cdots \mathsf{C}_3 \xrightarrow{\hspace{5pt} d_3 \hspace{5pt}} \mathsf{C}_2 \xrightarrow{\hspace{5pt} d_2 \hspace{5pt}} \mathsf{C}_1 \xrightarrow{\hspace{5pt} d_1 \hspace{5pt}} \mathsf{C}_0 \xrightarrow{\hspace{5pt} d_0\hspace{5pt} } 0\)
  • \(d_q d_{q+1} = 0 \Rightarrow \text{im}(d_{q+1}) \subset \ker(d_q)\)
  • \(\mathsf{C}_q\): vector space generated (spanned) by cells of dimension q

Homology groups:

  • \(H_q(K) := \ker(d_q) / \text{im}(d_{q+1}) = \mathbb{Z}^{\beta_q} \oplus \mathbb{T}\)
  • Betti numbers of dimension q: \(\beta_q\)

Reduction

Triplet \(\rho = (h, f, g)\) of homomorphisms between
two chain complexes

Both chain complexes have
isomorphic homology groups

A reduction is perfect if \(d' = 0\). Hence

  • \(\mathsf{C}' \cong H(\mathsf{C})\)
  • \(g(\mathsf{C}')\) = homology generators
  • \(f^*(\mathsf{C}')\) = cohomology generators

HDVF

Let \(K\) be a CW complex, \(P, S \subset K, P \cap S = \emptyset\).
A homological discrete vector field (HDVF) is a pair \(X = (P, S)\) such that \(d(S)_{|P}\) is an invertible matrix.

Boundary (incidence) matrix \(d\)

Boundary (incidence) matrix \(d\)

Boundary (incidence) matrix \(d\)

Boundary (incidence) matrix \(d\)

What can we do with a HDVF (its reduction)?

Decompose a cycle into homology generators
( i.e. critical cells)

Homology generator

Cohomology generator

Add a pair of critical cells

\(\mathtt{A}(X, \gamma, \gamma') = (P \cup \{\gamma\}, S \cup \{\gamma'\})\)

\(\mathtt{A}(X, \gamma, \gamma')\) is a HDVF if \(\langle d'(\gamma'), \gamma \rangle = 1\)

Remove a pair of cells

\(\mathtt{R}(X, \sigma, \tau) = (P \setminus \{\sigma\}, S \setminus \{\tau\})\)

\(\mathtt{R}(X, \sigma, \tau)\) is a HDVF if \(\langle h(\sigma), \tau \rangle = 1\)

To recompute the reduction (matrices H, F, G, D) of \(\mathtt{A}(X, \gamma, \gamma')\) of \(\mathtt{R}(X, \sigma, \tau)\) in O(n²)

  • Compute a perfect HDVF: O(n³)
  • Modify a complex without recomputing all its HDVF: O(n²) instead of O(n³)

Modifications

Two classes of operations:

  1. Modify the HDVF
  2. Modify the complex

→ recompute the reduction \(\rho\)

(1/6) Add a cell

  1. Recompute D: O(n²)
  2. \(\mathtt{A}\): O(n²)

(2/6) Remove a cell

  1. \(\mathtt{R}\): O(n²)
  2. Recompute D: O(n)
  3. \(\mathtt{A}\): O(n²)

(3/6) Divide a cell

  1. \(\mathtt{R}\): O(n²)
  2. Recompute D: O(n²)
  3. \(\mathtt{A}, \mathtt{A}\): O(n²)

(4/6) Merge two cells

  1. \(\mathtt{R}, \mathtt{R}, \mathtt{R}\): O(n²)
  2. Recompute D: O(n)
  3. \(\mathtt{A}, \mathtt{A}\): O(n²)

(5/6) Glue two cells

  1. \(\mathtt{R}, \mathtt{R}\): O(n²)
  2. Recompute D: O(n)
  3. \(\mathtt{A}, \mathtt{A}\): O(n²)

(6/6) Separate two cells

  1. \(\mathtt{R}\): O(n²)
  2. Recompute D: O(n²)
  3. \(\mathtt{A}\): O(n²)

Conclusion

  • Use HDVF for computing homology information
  • HDVF (not any reduction) allows for \(\mathtt{R}\) ⇒ remove, divide, merge, glue, separate cells
  • Update HDVF after elementary operations in O(n²) time and space
  • More optimisations still possible

Thanks