Introduction

Comment recalculer l'homologie d'un modèle qu'on vient de modifier ?

Homologie

• Topologie algébrique → homologie
• Algèbre linéaire, algorithmes en O(n³)
• Invariants : nombres de Betti (de trous)

Homologie

Complexe cellulaire

Groupes d'homologie

Complexe de chaînes :

• \(\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\) : espace vectoriel généré par les cellules de dimension q

Groupes d'homologie :

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

Réduction

Triplet \(\rho = (h, f, g)\) d'homomorphismes entre deux complexes de chaînes

Les deux complexes de chaînes ont leurs groupes d'homologie isomorphes.

Une réduction est parfaite si \(d' = 0\). Alors

• \(\mathsf{C}' \cong H(\mathsf{C})\)
• \(g(\mathsf{C}')\) = générateurs d'homologie
• \(f^*(\mathsf{C}')\) = générateurs de cohomologie

HDVF

Soit \(K\) un CW complexe, \(P, S \subset K, P \cap S = \emptyset\).
Un champs de vecteurs discret homologique (HDVF) est une paire \(X = (P, S)\) telle que \(d(S)_{|P}\) est une matrice inversible.

Matrice de bord (incidence) \(d\)

Matrice de bord (incidence) \(d\)

Matrice de bord (incidence) \(d\)

Matrice de bord (incidence) \(d\)

Décomposer un cycle en générateurs d'homologie

Générateur d'homologie

Générateur de cohomologie

Ajouter une paire de cellules critiques

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

\(\mathtt{A}(X, \gamma, \gamma')\) est un HDVF si \(\langle d'(\gamma'), \gamma \rangle = 1\)

Enlever une paire de cellules

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

\(\mathtt{R}(X, \sigma, \tau)\) est un HDVF si \(\langle h(\sigma), \tau \rangle = 1\)

Recalculer la réduction (matrices H, F, G, D) de \(\mathtt{A}(X, \gamma, \gamma')\) ou \(\mathtt{R}(X, \sigma, \tau)\) en O(n²)

• Calculer un HDVF parfait : O(n³)
• Modifier un complexe sans recalculer
  tout son HDVF - O(n²) au lieu de O(n³)

Modifications

Deux classes d’opérations :

1. Modifier le HDVF
2. Modifier le complexe

→ recalculer la réduction \(\rho\)

(1/6) Ajouter une cellule

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

(2/6) Supprimer une cellule

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

(3/6) Diviser une cellule

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

(4/6) Fusionner deux cellules

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

(5/6) Coller une cellule

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

(6/6) Décoller une cellule

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

Conclusion

• Utiliser le HDVF pour calculer l'homologie
• Mise à jour des modifications élémentaires en O(n²)
• Encore des optimisations à faire