Enumerating fundamental normal surfaces: Algorithms, experiments and invariants

DOI10.1137/1.9781611973198.11zbMATH Open1431.57014arXiv1111.7055OpenAlexW1527961817MaRDI QIDQ5232496

Publication date: 12 September 2019

Published in: 2014 Proceedings of the Sixteenth Workshop on Algorithm Engineering and Experiments (ALENEX) (Search for Journal in Brave)

Abstract: Computational knot theory and 3-manifold topology have seen significant breakthroughs in recent years, despite the fact that many key algorithms have complexity bounds that are exponential or greater. In this setting, experimentation is essential for understanding the limits of practicality, as well as for gauging the relative merits of competing algorithms. In this paper we focus on normal surface theory, a key tool that appears throughout low-dimensional topology. Stepping beyond the well-studied problem of computing vertex normal surfaces (essentially extreme rays of a polyhedral cone), we turn our attention to the more complex task of computing fundamental normal surfaces (essentially an integral basis for such a cone). We develop, implement and experimentally compare a primal and a dual algorithm, both of which combine domain-specific techniques with classical Hilbert basis algorithms. Our experiments indicate that we can solve extremely large problems that were once though intractable. As a practical application of our techniques, we fill gaps from the KnotInfo database by computing 398 previously-unknown crosscap numbers of knots.

Full work available at URL: https://arxiv.org/abs/1111.7055

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) General topology of 3-manifolds (57K30)