Calcul des groupes d'homologie

d’objets discretsSylvie Alayrangues - Jacques-Olivier Lachaud

AS géométrie discrète

09 juillet 2003

Plan

• Utilité des groupes d'homologie

• Définition

• Algorithme de calcul

• Pistes de recherche

Utilité des groupes d'homologie

• Invariant topologiqueMoins puissant que les groupes d'homotopieCalculables pour des structures discrètes

• Caractérisation d'objets Deux objets qui n’ont pas les mêmes groupes

d’homologie ont des topologies différentes Mais deux objets avec les mêmes groupes d’homologie

n’ont pas forcément la même topologie

• Plusieurs types d'homologie :Ici homologie simpliciale

• A un n-complexe simplicial sont associés (n+1) groupes d'homologie : Hk, k = 0..n k= rang de Hk (nombres de Betti)

• Intuitivement :Hk permet, entre autres, de compter les trous k-dimensionnels

d'un objet, de définir des générateurs de ces trous…0 : nb de composantes connexes

Définition des groupes d'homologie (1)

Définition des groupes d'homologie (2)

• Formellement :Complexe simplicial K : ensemble de simplexes tel que

toute face d'un simplexe de K est dans K, et que l'intersection de deux simplexes de K est face de chacun d'eux

Cp(K,G) : Ensemble des p-chaines de K à coefficients dans G (groupe abélien - ici le groupe des entiers)

p : Cp(K,G) Cp-1(K,G) : opérateur bord

• Zp(K,G)= Ker p et Bp-1(K,G)= Im p

p p+1 = 0

Hp(K,G) = Zp(K,G)/Bp(K,G)

2

4

1

3

Exemple

• C0(K) = (1,2,3,4)• C1(K) = (12,13,14,23,24,34)

1(12)=2-11(12+23-13)=0

• Matrice d’incidence

1 2 3 4

12 -1 1 0 0

13 -1 0 1 0

14 -1 0 0 1

23 0 -1 1 0

24 0 -1 0 1

34 0 0 -1 1

1

Principe du calcul (1)

• Hp(K,G) = ...Zb1Zb2... Zbqp

= βp Zb1Zb2... Zbqp

b1,b2,...,bqp sont les facteurs invariants

• bi / bj pour tout i et j, tels que i < j

p est le nombre de betti associé

• Calcul de Hp(K,G) = calcul de βp, b1,b2,...,bqp

Exemple de torsion sur la bouteille de Klein

• w = [1,4]+[4,5]+[5,1]

• soit s2 la somme de tous les 2-simplexes s2= 2 w cycle w = élément de torsion

• on montre que c = 0 c = n ([1,2]+[2,3]+[3,1]) + mw avec n = 0 et m pair

• H1 Z Z2

1

1

1

1

2

3

3

5

5

4

4

6 7

8

9 10

2

Principe du calcul (2)

• Obtenir la forme normale de Smith des matrices d'incidence

• On peut montrer que : Smith(p) donne les coefficients

de torsion de Hp-1(K)

βp (K) = rank Cp(K) - rank p(K) - rank p+1 (K)

q000

1000001

1

Principe du calcul (3)

• Problèmes :Réduction d'une matrice d'entiers

• À toutes les étapes, on manipule des entiers

• Les éléments des matrices intermédiaires peuvent devenir très grands

Dépassements mémoire

Complexité en temps élevée

• Sujet actif de recherche (algèbre)

Optimisations possibles

• Construction de la matrice d'incidencePrise en compte du caractère creux de la matrice (choix

du stockage)

• Manipulation des matricesSuppression des lignes nulles au fur et à mesureCalculs les plus coûteux effectués sur des sous-matrices

choisies de manière appropriéeUtilisation d’un modulo pour effectuer les calculs

(résultat de Storjohann)

Algorithme

• Construction d'une matrice d'incidence : i

• Calcul de la forme normale de Smith de i

Triangularisation de la matrice avec un maximum de pivots de valeur 1 : i'

• Mémorisation du nombre de 1

• Extraction de la sous-matrice i'' contenant toutes les lignes qui n'ont pas 1 pour pivot

Obtention de la forme normale de Smith de i''

Construction de i

• Complexe simplicial défini par ses faces maximalesCalcul de la liste de ses faces de dimension i

• Ordre lexicographique

• Matrice i obtenue par ligne :1 ligne / i-simplexe, 1 colonne / (i-1)-simplexe

• À partir de chaque i-simplexe, on construit chacune de ses (i-1) faces en enlevant à chaque fois un sommet, on récupère l'indice de la face obtenue (i.e. le numéro de la colonne) dans la liste des (i-1) simplexes et on remplit la matrice en alternant les valeurs 1 et -1

• Matrice bien ordonnée

Triangularisation de i' (1)

• 1ère étape : réalisée ligne par ligne :ri : index de la colonne de la première valeur non nulle de

la ligne i

Recherche d'un maximum de lignes avec des ri distincts et telles que i'[i,ri] = 1

• Modifications de chaque ligne avec des opérations élémentaires (li = +/-li +/- k*lj) jusqu'à ce que :

Ligne = vecteur nul ligne retirée de la matriceLigne dans la forme recherchée ligne gardée telle quelleri distinct de rj pour tous les j précédemment rencontrés

mais Di'[i,ri] 1 traitement de la ligne différé

Triangularisation de i' (2)

• 2ème étape : traitement des lignes différéesLignes traitées comme précédemment mais utilisation

d'opérations plus coûteuses (gcd)Obtention d'une matrice avec beaucoup de pivots valant

1 et éventuellement quelques pivots différents de 1

• 3ème étape : calcul des éventuelles torsionsExtraction de la matrice telle que les pivots sont

différents de 1 et calcul de la forme de smith de cette matrice (méthode décrite par Munkres).

Exemple : bouteille de Klein

• Triangulation possible : ((1,2,6)(1,4,6)(1,2,9)(1,5,9)(1,3,7)(1,5,7)(1,3,10)(1,4,10)(2,3,6)(2,9,10)(2,3,10)(3,6,7)(4,5,6)(4,5,10)(5,6,9)(5,7,10)(6,8,9)(6,7,8)(7,8,10)(8,9,10))

• Nombres de Betti et torsions :

[1 ()][1 (2(1))][0 ()]

2

1

1

1

1

2

3

3

5

5

4

4

6 7

8

9 10

Exemple : plan projectif

• Triangulation possible : ((1,2,7)(1,2,11)(1,6,7)(1,6,11)(2,3,7)(2,3,11)(3,4,8)(3,4,10)(3,7,8)(3,10,11)(4,5,8)(4,5,10)(5,6,7)(5,6,11)(5,7,10)(5,8,11)(7,8,9)(7,9,10)(8,9,11)(9,10,11))

• Nombres de Betti et torsions :[1 ()][0 (2 (1))][0 ()]

4

1

1

42

3

3

2

5

5

6

6

7 8

9

10 11

Pistes de recherche

• Utiliser ces calculs pour des objet définis à l'aide d'ordres, et de complexes cellulairesPb : comment construire la matrice d’incidence “le mieux

possible” ?

• Adapter pour calculer des groupes d’homologie locaux

• Algorithme défini pour un objet statique Algorithme incrémental pour des objets dont la topologie

évolue ?