## 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

#### 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. 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