Titre : Calcul incrémental d’invariants topologiques au cours d’un processus de construction
Résumé : La thématique de ce séminaire est la modélisation géométrique à base topologique. Plus précisément, nous nous intéressons au calcul des groupes d’homologie d’un objet géométrique subdivisé en cellules de différentes de dimensions. Ce dernier évolue dans un processus de construction par application d’opérations locales, qui ne modifie que légèrement l’objet. En particulier, nous nous intéressons à l’opération d’identification, consistant à fusionner des cellules entre elles. À chaque étape, nous souhaitons détecter les changements de structure de l’objet en calculant incrémentalement ses groupes d’homologie, c’est-à-dire en tenant compte de l’opération et de l’information homologique de l’étape précédente. Pour ce faire, nous utilisons un théorème d’homologie effective : le théorème des suites exactes courtes effectives (théorème SECE), à l’aide duquel il est possible, au fil des étapes, de maintenir l’information homologique au travers de la notion d’équivalence homologique. D’abord, nous analysons les calculs impliqués par le théorème en vue de proposer une implantation efficace, tirant parti de la localité des opérations. Nous proposons une structure de donnée adaptée aux prérequis ainsi relevés, utilisée dans le cadre d’une analyse expérimentale montrant, entre autres, qu’il est possible dans certains cas de limiter la complexité algorithmique du maintien de l’équivalence homologique à la taille de l’opération. Ensuite, nous étudions la faisabilité du théorème SECE lorsque l’objet est distribué car trop volumineux pour être manipulé par une seule unité de calcul. Dans ce cadre, nous proposons un algorithme de répartition d’identification permettant de minimiser l’opération de reconstruction de la distribution, dont va dépendre la complexité du calcul d’homologie. Enfin, nous proposons quelques pistes permettant d’établir un lien entre le théorème SECE et des travaux d’homologie persistante, un autre paradigme de calcul d’homologie.
Commentaires récents