Large scale computations of 3-manifolds invariants
Calculs à grande échelle d'invariants de 3-variétés
Résumé
Topology is the study of shapes modulo deformations, without cutting or gluing: the famous example of this is the mug that can be morphed into a doughnut. Among all the objects studied by topologists, manifolds are of particular interest: they are generalizations of surfaces to higher dimensions that are studied by many mathematicians, and they allow to represent many shapes in a rather natural way.This thesis is focused on low dimensional topology, and more precisely on the study of 3-manifolds. 3-manifolds have a peculiar status for computer scientists: while problems tend to be polynomial on 2-manifolds and undecidable on 4-manifolds, see for instance the homeomorphism problem, problems tend to be doable but difficult on 3-manifolds. Furthermore, all 3-manifolds admit a triangulation and thus can be manipulated by computers.3-manifolds are also an effective way to study knots. Knots can be seen as knotted closed curves in the space, they are used as modeling tools and are linked to quantum physics. The Gordon-Luecke theorem states that the complement of a knot in the 3-sphere is a 3-manifold that contains all the information about the knot. Using 3-manifolds, the study of knots leaped forward with Thurston's classification theorem: a knot is either torus, if its complement contains an annulus whose boundary lies on the knot, satellite, if its complement contains a torus that contains the knot, and hyperbolic otherwise.Distinguishing pairs of manifolds, and pairs of knots in particular, is a complex and central problem in topology. For knot diagrams, a projection of the knot in a plane, one could try to modify one into another, but these kind of approaches are infamously expensive. A more realistic approach is to use topological characteristics: the invariants. These invariants are mathematical objects that encode some of the topological information of the manifold, thus they do not depend on the representation of an object, such as the triangulation for a manifold or the diagram for a knot, and they are subject to intensive study.While computing invariants is, in general, simpler than solving directly the homeomorphism problem, their computations are often non trivial, which calls for efficient algorithms and implementations. This is particularly true today as, with the increasing computation power, very large censuses of knots and manifolds are available, requiring extensions and analysis. The needs of the community in terms of software is demonstrated by the popularity and ubiquity of libraries like SnapPy and Regina.This thesis is dedicated to two invariants: the hyperbolic volume and the invariants of Turaev-Viro. In both cases we propose contributions in term of algorithm, software, and analysis.For the hyperbolic volume, we propose an approach based on theorems of Casson and Rivin to compute complete hyperbolic structures (CHS). Given a triangulation, we use convex optimization on its polytope of angle structures; this either leads to a CHS, or to a blocking configuration we resolve in order to proceed further. In addition to this algorithm and the analysis of its results, we propose an hybridization with SnapPy's method that outperforms the state-of-the art.For the Turaev-Viro invariants, which are indexed by an integer r, we propose a preprocessing method based on polytope theory to select the triangulation on which existing algorithms will perform the best. We then introduce multiprecision arithmetics to Regina in order to perform large r computations of the invariant and verify a volume conjecture based on the Turaev-Viro invariants.
La topologie est l'étude des objets à déformation près, sans couper ni coller: l'illustration la plus répandue est sans doute la transformation d'une tasse en donut. Parmi tous les sujets d'études en topologie, les variétés présentent un intérêt particulier: elles sont la généralisation en toutes dimensions des surfaces et permettent de représenter naturellement de nombreux objets.Cette thèse se concentre sur la topologie en basses dimensions, et plus précisément à l'étude des 3-variétés. Celles-ci ont un statut privilégié pour les informaticiens: alors que les problèmes ont tendance à être simples en dimension 2 et impossibles en dimension 4, à l'instar du problème de l'homéomorphisme, les problèmes tendent à être difficiles mais possibles avec les 3-variétés. De plus, les 3-variétés sont triangulables et donc manipulables par des ordinateurs.Les 3-variétés peuvent également être utilisées pour étudier les nœuds. Les nœuds peuvent être vus comme des courbes fermées et nouées, ils sont utilisés en modélisation et en physique quantique. Par le théorème de Gordon-Luecke, le complément d'un nœud est une 3-variété qui contient toutes les informations à propos de celui-ci. Avec les 3-variétés, l'étude des nœuds a connu de nombreux avancements incluant notamment le théorème de classification de Thurston qui les classes en trois familles: les nœuds toriques, satellites et hyperboliques.Différencier des couples de variétés, ou de nœuds, est un problème difficile et central en topologie. Pour les diagrammes de nœuds, une projection d'un nœud dans le plan, il est possible d'essayer de le modifier pour le transformer en un autre, mais ces approches sont connues pour être très difficiles. Une approche plus réaliste est d'utiliser des caractéristiques topologiques: les invariants. Ce sont des objets mathématiques qui encodent une partie de l'information topologique d'un autre objet, ils ne dépendent donc pas de la représentation de la variété ou du diagramme du nœud, et ils sont l'objet d'intenses recherches en mathématiques.Si calculer directement un invariant est, en général, plus simple que de résoudre le problème de l'homéomorphisme, leur calcul n'est pas toujours simple, d'où des besoins en terme de logiciels et d'implémentations. C'est d'autant plus vrai aujourd'hui qu'avec l'augmentation des puissances de calcul, de grands recensements de variétés et de nœuds sont disponibles, nécessitants analyse et extension. Les besoins de la communauté en matière de logiciels sont bien illustrés par la popularité des bibliothèques comme SnapPy et Regina.Cette thèse est dédiée à deux invariants: le volume hyperbolique et les invariants de Turaev-Viro. Dans les deux cas des contributions sont proposées en terme d'algorithmes, de logiciels et d'analyses.Pour le volume hyperbolique, nous proposons une approche basée sur des théorèmes de Casson et Rivin pour calculer des structures hyperboliques complètes (CHS). Étant donnée une triangulation, nous utilisons de l'optimisation convexe sur son polytope des structures angulaires ; ce qui mène soit à une CHS, soit à une configuration bloquante que nous simplifions avant de continuer. En plus de ces résultats nous proposons une hybridation entre notre méthode et celle de SnapPy qui est plus rapide que l'état de l'art.Pour les invariants de Turaev-Viro, qui sont indexés par un entier r, nous proposons une méthode pour déterminer, étant donnée une collection de triangulations, sur laquelle les algorithmes de calculs seront le plus efficaces. Nous ajoutons également de l'arithmétique multiprécision à Regina dans le but de pouvoir calculer l'invariant, même pour de grandes valeurs de r, ce qui permet de vérifier expérimentalement une conjecture du volume basée sur les invariants de Turaev-Viro.
Origine : Version validée par le jury (STAR)