Soutenance memoire charly finette .pdf

---

À propos / Télécharger Aperçu

---

Ce document au format PDF 1.5 a été généré par LaTeX with Beamer class / pdfTeX-1.40.20, et a été envoyé sur fichier-pdf.fr le 01/07/2020 à 14:46, depuis l'adresse IP 77.206.x.x. La présente page de téléchargement du fichier a été vue 93 fois.
Taille du document: 1.9 Mo (51 pages).
Confidentialité: fichier public
Auteur vérifié

Aperçu du document

---

Introduction
Méthodes algorithmiques de calcul de l’homologie
Mise à jour incrémentale de l’homologie
Conclusion

Calcul incrémental de l’homologie : vers une
mise à jour en temps linéaire ?
Charly Finette

Juin 2020

Charly Finette

Soutenance de mémoire

1 / 51

Introduction
Méthodes algorithmiques de calcul de l’homologie
Mise à jour incrémentale de l’homologie
Conclusion

Introduction
Contexte du stage

Stage encadré par :
Alexandra Bac, Maître de conférences, HDR
Aldo Gonzalez-Lorenzo, Maître de conférences

Charly Finette

Soutenance de mémoire

2 / 51

Introduction
Méthodes algorithmiques de calcul de l’homologie
Mise à jour incrémentale de l’homologie
Conclusion

Introduction
Problématique et objectifs

Charly Finette

Soutenance de mémoire

3 / 51

Introduction
Méthodes algorithmiques de calcul de l’homologie
Mise à jour incrémentale de l’homologie
Conclusion

Introduction
Problématique et objectifs

Charly Finette

Soutenance de mémoire

4 / 51

Introduction
Méthodes algorithmiques de calcul de l’homologie
Mise à jour incrémentale de l’homologie
Conclusion

Introduction
Problématique et objectifs

Charly Finette

Soutenance de mémoire

5 / 51

Introduction
Méthodes algorithmiques de calcul de l’homologie
Mise à jour incrémentale de l’homologie
Conclusion

Table of contents

1

Introduction

2

Méthodes algorithmiques de calcul de l’homologie

3

Mise à jour incrémentale de l’homologie

4

Conclusion

Charly Finette

Soutenance de mémoire

6 / 51

Introduction
Méthodes algorithmiques de calcul de l’homologie
Mise à jour incrémentale de l’homologie
Conclusion

Contexte
Topologie algébrique

La topologie analyse la structure essentielle d’un objet
La topologie algébrique classifie les espaces topologiques

Charly Finette

Soutenance de mémoire

7 / 51

Introduction
Méthodes algorithmiques de calcul de l’homologie
Mise à jour incrémentale de l’homologie
Conclusion

Contexte
Topologie algébrique

La topologie analyse la structure essentielle d’un objet
La topologie algébrique classifie les espaces topologiques

Charly Finette

Soutenance de mémoire

8 / 51

Introduction
Méthodes algorithmiques de calcul de l’homologie
Mise à jour incrémentale de l’homologie
Conclusion

Contexte
Topologie algébrique

La topologie analyse la structure essentielle d’un objet
La topologie algébrique classifie les espaces topologiques

−→ Analyse de la structure des trous

Charly Finette

Soutenance de mémoire

9 / 51

Introduction
Méthodes algorithmiques de calcul de l’homologie
Mise à jour incrémentale de l’homologie
Conclusion

Contexte
Topologie algébrique

Si deux espaces topologiques sont homéomorphes alors ils ont la
même homologie.

Charly Finette

Soutenance de mémoire

10 / 51

Introduction
Méthodes algorithmiques de calcul de l’homologie
Mise à jour incrémentale de l’homologie
Conclusion

Contexte
Théorie de l’homologie

Charly Finette

Soutenance de mémoire

11 / 51

Introduction
Méthodes algorithmiques de calcul de l’homologie
Mise à jour incrémentale de l’homologie
Conclusion

Contexte
Théorie de l’homologie

Charly Finette

Soutenance de mémoire

12 / 51

Introduction
Méthodes algorithmiques de calcul de l’homologie
Mise à jour incrémentale de l’homologie
Conclusion

Contexte
Théorie de l’homologie

Figure – Objets discrets : Ensemble semi-simplicial, complexe
simplicial, complexe cubique
Charly Finette

Soutenance de mémoire

13 / 51

Introduction
Méthodes algorithmiques de calcul de l’homologie
Mise à jour incrémentale de l’homologie
Conclusion

Contexte
Théorie de l’homologie

Charly Finette

Soutenance de mémoire

14 / 51

Introduction
Méthodes algorithmiques de calcul de l’homologie
Mise à jour incrémentale de l’homologie
Conclusion

Contexte
Théorie de l’homologie

Definition
Un complexe de chaînes (C, ∂) est une suite de groupes abéliens
{Cq }q≥0 munie de morphismes {∂q }q≥0 tels que ∂q−1 ∂q = 0
∂

∂

∂

∂

3
2
1
0
... −→
C2 −→
C1 −→
C0 −→
0

Charly Finette

Soutenance de mémoire

15 / 51

Introduction
Méthodes algorithmiques de calcul de l’homologie
Mise à jour incrémentale de l’homologie
Conclusion

Contexte
Théorie de l’homologie

Charly Finette

Soutenance de mémoire

16 / 51

Introduction
Méthodes algorithmiques de calcul de l’homologie
Mise à jour incrémentale de l’homologie
Conclusion

Contexte
Théorie de l’homologie

Definition
Les groupes d’homologie d’un complexe de chaîne (C, ∂) sont les
quotients
Hq = ker(∂q )/im(∂q+1 )
Hq = Zβq × Z/λ1 Z × ... × Z/λk Z
(λ1 , ..., λn ) sont les coefficients de torsion de dimension q.
On appelle l’entier βq « nombre de Betti de dimension q ».

Charly Finette

Soutenance de mémoire

17 / 51

Introduction
Méthodes algorithmiques de calcul de l’homologie
Mise à jour incrémentale de l’homologie
Conclusion

Contexte
Théorie de l’homologie

Charly Finette

Soutenance de mémoire

18 / 51

Introduction
Méthodes algorithmiques de calcul de l’homologie
Mise à jour incrémentale de l’homologie
Conclusion

Contexte
Théorie de l’homologie

Les groupes d’homologie du tore sont :
H0 = Z donc β0 = 1 ;
H1 = Z2 donc β1 = 2 ;
H2 = Z donc β2 = 1 ;
Hn = 0, pour tous n > 2.

Charly Finette

Soutenance de mémoire

19 / 51

Introduction
Méthodes algorithmiques de calcul de l’homologie
Mise à jour incrémentale de l’homologie
Conclusion

Contexte
Méthodes algorithmiques de calcul de l’homologie

Charly Finette

Soutenance de mémoire

20 / 51

Introduction
Méthodes algorithmiques de calcul de l’homologie
Mise à jour incrémentale de l’homologie
Conclusion

Contexte
Méthodes algorithmiques de calcul de l’homologie

Charly Finette

Soutenance de mémoire

21 / 51

Introduction
Méthodes algorithmiques de calcul de l’homologie
Mise à jour incrémentale de l’homologie
Conclusion

Contexte
Méthodes algorithmiques de calcul de l’homologie

Charly Finette

Soutenance de mémoire

22 / 51

Introduction
Méthodes algorithmiques de calcul de l’homologie
Mise à jour incrémentale de l’homologie
Conclusion

Contexte
Méthodes algorithmiques de calcul de l’homologie

Definition
Une réduction ρ : (C 0 , ∂ 0 )  (C 1 , ∂ 1 ) est un diagramme :

avec
gf = 1C 0 − dh − hd,
f g = 1C 1 gh ,
hh, f h, hg = 0.
Une telle réduction assure que (C 0 , ∂ 0 ) et (C 1 , ∂ 1 ) ont les
mêmes groupes d’homologie.
Charly Finette

Soutenance de mémoire

23 / 51

Introduction
Méthodes algorithmiques de calcul de l’homologie
Mise à jour incrémentale de l’homologie
Conclusion

Contexte
Méthodes algorithmiques de calcul de l’homologie

Charly Finette

Soutenance de mémoire

24 / 51

Introduction
Méthodes algorithmiques de calcul de l’homologie
Mise à jour incrémentale de l’homologie
Conclusion

Contexte
Méthodes algorithmiques de calcul de l’homologie

Charly Finette

Soutenance de mémoire

25 / 51

Introduction
Méthodes algorithmiques de calcul de l’homologie
Mise à jour incrémentale de l’homologie
Conclusion

Mise à jour incrémentale de l’homologie
Introduction au problème

Problème du calcul de l’homologie

Charly Finette

Soutenance de mémoire

26 / 51

Introduction
Méthodes algorithmiques de calcul de l’homologie
Mise à jour incrémentale de l’homologie
Conclusion

Mise à jour incrémentale de l’homologie
Introduction au problème

Problème de la mise à jour incrémentale de l’homologie

Charly Finette

Soutenance de mémoire

27 / 51

Introduction
Méthodes algorithmiques de calcul de l’homologie
Mise à jour incrémentale de l’homologie
Conclusion

Mise à jour incrémentale de l’homologie
État des lieux de la recherche

Charly Finette

Soutenance de mémoire

28 / 51

Introduction
Méthodes algorithmiques de calcul de l’homologie
Mise à jour incrémentale de l’homologie
Conclusion

Mise à jour incrémentale de l’homologie
Etat des lieux de la recherche

Charly Finette

Soutenance de mémoire

29 / 51

Introduction
Méthodes algorithmiques de calcul de l’homologie
Mise à jour incrémentale de l’homologie
Conclusion

Mise à jour incrémentale de l’homologie
HDVF

Definition
Un HDVF (Homological Discrete Vector Field) X = (P, S) sur
un complexe simplicial K est une partition K = P t S t C telle
que d(Sq+1 ) Pq est une matrice inversible dans Z, pour tout
q ≥ 0, où Pq et Sq sont les restrictions de P et S aux q-cellules
et d(Sq+1 ) Pq est la sous-matrice de la matrice de bord dq+1
dont les colonnes sont associées aux (q+1)-cellules secondaires
et les lignes sont associées aux q-cellules primaires.

Charly Finette

Soutenance de mémoire

30 / 51

Introduction
Méthodes algorithmiques de calcul de l’homologie
Mise à jour incrémentale de l’homologie
Conclusion

Mise à jour incrémentale de l’homologie
HDVF

Partition entre cellules primaires, secondaires et critiques
Nombres de cellules critiques de dim q ≥ β q
Chaque HDVF implique une réduction

Charly Finette

Soutenance de mémoire

31 / 51

Introduction
Méthodes algorithmiques de calcul de l’homologie
Mise à jour incrémentale de l’homologie
Conclusion

Mise à jour incrémentale de l’homologie
HDVF

Ajout d’une cellule

Charly Finette

Soutenance de mémoire

32 / 51

Introduction
Méthodes algorithmiques de calcul de l’homologie
Mise à jour incrémentale de l’homologie
Conclusion

Mise à jour incrémentale de l’homologie
HDVF

Division d’une cellule

Charly Finette

Soutenance de mémoire

33 / 51

Introduction
Méthodes algorithmiques de calcul de l’homologie
Mise à jour incrémentale de l’homologie
Conclusion

Mise à jour incrémentale de l’homologie
HDVF

Identification de deux cellules

Charly Finette

Soutenance de mémoire

34 / 51

Introduction
Méthodes algorithmiques de calcul de l’homologie
Mise à jour incrémentale de l’homologie
Conclusion

Mise à jour incrémentale de l’homologie
Poitiers

Definition
Une équivalence d’homologie Υ entre deux complexes de
chaînes, (C, ∂) et (C S , ∂ S ) est une paire de réductions ρ et ρS en
relation avec un complexe de chaîne (C B , ∂ B ), telles que :
ρ

ρS

Υ : (C, ∂)  (C B , ∂ B )  (C S , ∂ S )
On note parfois :
Υ : (C, ∂)  (C S , ∂ S )

Charly Finette

Soutenance de mémoire

35 / 51

Introduction
Méthodes algorithmiques de calcul de l’homologie
Mise à jour incrémentale de l’homologie
Conclusion

Mise à jour incrémentale de l’homologie
Poitiers

Opération de cône

Le cône d’un ensemble semi-simplicial quelconque a
toujours la même homologie
On lui associe donc une équivalence d’homologie en temps
linéaire
on utilise pas l’équivalence d’homologie initiale
Charly Finette

Soutenance de mémoire

36 / 51

Introduction
Méthodes algorithmiques de calcul de l’homologie
Mise à jour incrémentale de l’homologie
Conclusion

Mise à jour incrémentale de l’homologie
Poitiers

Opération d’identification

Charly Finette

Soutenance de mémoire

37 / 51

Introduction
Méthodes algorithmiques de calcul de l’homologie
Mise à jour incrémentale de l’homologie
Conclusion

Mise à jour incrémentale de l’homologie
Poitiers

Charly Finette

Soutenance de mémoire

38 / 51

Introduction
Méthodes algorithmiques de calcul de l’homologie
Mise à jour incrémentale de l’homologie
Conclusion

Mise à jour incrémentale de l’homologie
Poitiers

Charly Finette

Soutenance de mémoire

39 / 51

Introduction
Méthodes algorithmiques de calcul de l’homologie
Mise à jour incrémentale de l’homologie
Conclusion

Mise à jour incrémentale de l’homologie
Poitiers

Opération d’identification

Pas d’estimation de la complexité en temps de calcul
La complexité dépend de Υ1 qui est quelconque.
Charly Finette

Soutenance de mémoire

40 / 51

Introduction
Méthodes algorithmiques de calcul de l’homologie
Mise à jour incrémentale de l’homologie
Conclusion

Mise à jour incrémentale de l’homologie
Poitiers

Construction par identification des simplexes de dimension
croissante
1 Décomposition de l’ESS K

Charly Finette

Soutenance de mémoire

41 / 51

Introduction
Méthodes algorithmiques de calcul de l’homologie
Mise à jour incrémentale de l’homologie
Conclusion

Mise à jour incrémentale de l’homologie
Poitiers

Charly Finette

Soutenance de mémoire

42 / 51

Introduction
Méthodes algorithmiques de calcul de l’homologie
Mise à jour incrémentale de l’homologie
Conclusion

Mise à jour incrémentale de l’homologie
Poitiers

Construction par identification des simplexes de dimension
croissante
1 Décomposition de l’ESS K
2

On associe Υ1 à la décomposition

Charly Finette

Soutenance de mémoire

43 / 51

Introduction
Méthodes algorithmiques de calcul de l’homologie
Mise à jour incrémentale de l’homologie
Conclusion

Mise à jour incrémentale de l’homologie
Poitiers

Figure – Υ1

Charly Finette

Soutenance de mémoire

44 / 51

Introduction
Méthodes algorithmiques de calcul de l’homologie
Mise à jour incrémentale de l’homologie
Conclusion

Mise à jour incrémentale de l’homologie
Poitiers

Construction par identification des simplexes de dimension
croissante
1 Décomposition de l’ESS K
2
3

On associe Υ1 à la décomposition
On identifie les simplexes de dimension 0 et on obtient Υ2
grâce au SES theorem

Charly Finette

Soutenance de mémoire

45 / 51

Introduction
Méthodes algorithmiques de calcul de l’homologie
Mise à jour incrémentale de l’homologie
Conclusion

Mise à jour incrémentale de l’homologie
Poitiers

Construction par identification des simplexes de dimension
croissante
1 Décomposition de l’ESS K
2
3

On associe Υ1 à la décomposition
On identifie les simplexes de dimension 0 et on obtient Υ2
grâce au SES theorem

4

...

5

On identifie les simplexes de dimension n − 2 et on obtient
Υn , une équivalence d’homologie associée à K.

Charly Finette

Soutenance de mémoire

46 / 51

Introduction
Méthodes algorithmiques de calcul de l’homologie
Mise à jour incrémentale de l’homologie
Conclusion

Mise à jour incrémentale de l’homologie
Poitiers

Theorem
La complexité en temps du calcul de Υn est linéaire par rapport
à n fois la taille de Υ1 .
Usuellement, on estime la complexité par rapport à la taille
de K (le nombre de ses simplexes)
Un de mes résultats estime que Υ1 est de taille
exponentielle par rapport à K dans certains cas.

Charly Finette

Soutenance de mémoire

47 / 51

Introduction
Méthodes algorithmiques de calcul de l’homologie
Mise à jour incrémentale de l’homologie
Conclusion

Conclusion
Résultats et réponse à la problématique

Traduction en termes matricielles de la méthode de Poitiers
et simplification
L’identification et la construction ne sont pas linéaires
Le cône est linéaire
On ne peut pas améliorer les HDVF à l’aide de la méthode
de Poitiers.

Charly Finette

Soutenance de mémoire

48 / 51

Introduction
Méthodes algorithmiques de calcul de l’homologie
Mise à jour incrémentale de l’homologie
Conclusion

Conclusion
Perspectives

Les réductions calculées par Poitiers pour l’opération de
cône et d’identification peuvent être décrites par des HDVF.
Il est probablement possible de créer un SES theorem pour
les HDVF

Charly Finette

Soutenance de mémoire

49 / 51

Introduction
Méthodes algorithmiques de calcul de l’homologie
Mise à jour incrémentale de l’homologie
Conclusion

Contexte
Homologie d’un espace topologique

Definition
Un ensemble semi-simplicial S = (K, (dj )j=0,...,n ) de dimension
n est défini par :
S
K = i=0,...,n Ki , où Ki est un ensemble dont les éléments
sont nommés i-simplexes.
∀j ∈ {0, ..., n}, dj : K −→ K , appelé opérateur de face, est
tel que :
1

2

∀i ∈ {1, .., n}, ∀j ∈ {0, .., i}, dj : Ki −→ Ki−1 ; ∀j > i, dj
n’est pas défini sur Ki , et aucun opérateur de face n’est
défini sur K0 ;
Soit σ un i-simplexe, ∀j, k ∈ {0, .., i}, dj dk = dk dj−1 pour
k < j.
Charly Finette

Soutenance de mémoire

50 / 51



Sur le même sujet..

---