Collapses and persistent homology

Effondrements et homologie persistante Dans cette thèse, nous introduisons deux nouvelles approches pour calculer l'homologie persistante(HP) d'une séquence de complexes simpliciaux. L'idée de base est de simplifier les complexes de la séquence d'entrée en utilisant des types spéciaux de collapses (effondrement), les collapses forts et les collapses d'arêtes, et de calculer l'HP d'une séquence réduite de plus petite taille qui a la même HP que la séquence initiale. Notre première approche utilise les collapses forts introduits par J. Barmak et E. Miniam [DCG (2012)]. Un collapse fort supprime les sommets dits dominés d'un complexe simplicial. Notre approche utilisant les collapses forts a plusieurs caractéristiques qui la distinguent des travaux antérieurs. La méthode n'est pas limitée aux filtrations (c'est-à-dire aux séquences de sous-complexes simpliciaux imbriqués) mais fonctionne pour d'autres types de séquences comme les tours et les zigzags. Par ailleurs, pour implémenter les collapses forts, il suffit de représenter les simplexes maximaux du complexe, et pas l'ensemble de tous ses simplexes, ce qui économise beaucoup d'espace et de temps. De plus, les complexes de la séquence peuvent être collapsés indépendamment et en parallèle.Dans le cas des complexes en drapeaux (flag complexes), les collapses forts peuvent être réalisés sur le 1-squelette du complexe et le complexe résultat est également un complexe en drapeau. Nous montrons que si l'on restreint la classe des complexes simpliciaux aux complexes en drapeaux, on peut améliorer la complexité en temps et en espace de facon décisive par rapport aux travaux antérieurs. Lorsque les collapses forts sont appliqués aux complexes d'une tour de complexes en drapeau, nous obtenons une séquence réduite qui est aussi une tour de complexes en drapeau que nous appelons le coeur de la tour. Nous convertissons ensuite le coeur de la tour en une filtration équivalente pour calculer son HP. Là encore, nous n'utilisons que les 1-squelettes des complexes. La méthode résultante est simple et extrêmement efficace.Nous étendons la notion de sommet dominé au cas de simplexes de dimension quelconque. Le concept d'arête dominée apparait très puissant et nous l'étudions dans le cas des complexes en drapeaux de faconplus détaillée. Nous montrons que les collapses d'arêtes (suppression des arêtes dominées) dans un complexe en drapeaux peut être effectué, comme précédemment, en utilisant uniquement le 1-squelette du complexe. En outre, le complexe résiduel est également un complexe de drapeaux. Ensuite, nous montrons que, comme dans le cas des collapses forts, on peut utiliser les collapses d'arêtes pour réduire une filtration de complexes en drapeaux en une filtration de complexes en drapeaux plus petite qui a la même HP. Là encore, nous utilisons uniquement le 1-squelettes des complexes.Comme l'ont démontré de nombreuses expériences sur des données publiques, les approches développées sont extrêmement rapides et efficaces en mémoire. En particulier, la méthode utilisant les collapses d'arêtes offre de meilleures performances que toutes les méthodes connues, y compris l'approche par collapses forts. Enfin, nous pouvons faire des compromis entre précision et temps de calcul en choisissant le nombre de complexes simpliciaux de la séquence à collapser.