Computational topology

Last updated October 31, 2023

Algorithmic topology, or computational topology, is a subfield of topology with an overlap with areas of computer science, in particular, computational geometry and computational complexity theory.

Major algorithms by subject area

Algorithmic 3-manifold theory

A large family of algorithms concerning 3-manifolds revolve around normal surface theory, which is a phrase that encompasses several techniques to turn problems in 3-manifold theory into integer linear programming problems.

Rubinstein and Thompson's 3-sphere recognition algorithm. This is an algorithm that takes as input a triangulated 3-manifold and determines whether or not the manifold is homeomorphic to the 3-sphere. It has exponential run-time in the number of tetrahedral simplexes in the initial 3-manifold, and also an exponential memory profile. Moreover, it is implemented in the software package Regina.^[3] Saul Schleimer went on to show the problem lies in the complexity class NP.^[4] Furthermore, Raphael Zentner showed that the problem lies in the complexity class coNP,^[5] provided that the generalized Riemann hypothesis holds. He uses instanton gauge theory, the geometrization theorem of 3-manifolds, and subsequent work of Greg Kuperberg ^[6] on the complexity of knottedness detection.
The connect-sum decomposition of 3-manifolds is also implemented in Regina, has exponential run-time and is based on a similar algorithm to the 3-sphere recognition algorithm.
Determining that the Seifert-Weber 3-manifold contains no incompressible surface has been algorithmically implemented by Burton, Rubinstein and Tillmann^[7] and based on normal surface theory.
The Manning algorithm is an algorithm to find hyperbolic structures on 3-manifolds whose fundamental group have a solution to the word problem.^[8]

At present the JSJ decomposition has not been implemented algorithmically in computer software. Neither has the compression-body decomposition. There are some very popular and successful heuristics, such as SnapPea which has much success computing approximate hyperbolic structures on triangulated 3-manifolds. It is known that the full classification of 3-manifolds can be done algorithmically,^[9] in fact, it is known that deciding whether two closed, oriented 3-manifolds given by triangulations (simplicial complexes) are equivalent (homeomorphic) is elementary recursive.^[10] This generalizes the result on 3-sphere recognition.

Conversion algorithms

SnapPea implements an algorithm to convert a planar knot or link diagram into a cusped triangulation. This algorithm has a roughly linear run-time in the number of crossings in the diagram, and low memory profile. The algorithm is similar to the Wirthinger algorithm for constructing presentations of the fundamental group of link complements given by planar diagrams. Similarly, SnapPea can convert surgery presentations of 3-manifolds into triangulations of the presented 3-manifold.
D. Thurston and F. Costantino have a procedure to construct a triangulated 4-manifold from a triangulated 3-manifold. Similarly, it can be used to construct surgery presentations of triangulated 3-manifolds, although the procedure is not explicitly written as an algorithm in principle it should have polynomial run-time in the number of tetrahedra of the given 3-manifold triangulation.^[11]
S. Schleimer has an algorithm which produces a triangulated 3-manifold, given input a word (in Dehn twist generators) for the mapping class group of a surface. The 3-manifold is the one that uses the word as the attaching map for a Heegaard splitting of the 3-manifold. The algorithm is based on the concept of a layered triangulation.

Algorithmic knot theory

Determining whether or not a knot is trivial is known to be in the complexity classes NP ^[12] as well as co-NP.^[13]
The problem of determining the genus of a knot is known to have complexity class PSPACE.^[12]
There are polynomial-time algorithms for the computation of the Alexander polynomial of a knot.^[14]
The Jones polynomial, the HOMFLY polynomial and Reshetikhin–Turaev invariants are fixed parameter tracktable, while the Jones polynomial is also known to be #P-hard.^[15] Computing the first coefficient of the HOMFLYPT and Kauffman polynomial is in P.^[16]
Additive approximation of the Jones polynomial is BQP-complete, i.e., equivalently hard as polynomial time quantum algorithms.^[17]
Given two (tame) knots by link diagrams deciding whether they are equivalent is ER. This is established by reducing knot equivalence (isotopy) to equivalence (homeomorphy) of the associated knot complements which are 3-manifolds which in turn can be encoded by triangulations. Since these knot complements are Haken manifolds one then uses a result that the equivalence problem of these manifolds is in ER. There does not seem to be a good reference for this, these results are scattered across the literature in the field, but well-known by the community.

Computational homotopy

Computational methods for homotopy groups of spheres.
Computational methods for solving systems of polynomial equations.
Brown has an algorithm to compute the homotopy groups of spaces that are finite Postnikov complexes,^[18] although it is not widely considered implementable.

Computational homology

Computation of homology groups of cell complexes reduces to bringing the boundary matrices into Smith normal form. Although this is a completely solved problem algorithmically, there are various technical obstacles to efficient computation for large complexes. There are two central obstacles. Firstly, the basic Smith form algorithm has cubic complexity in the size of the matrix involved since it uses row and column operations which makes it unsuitable for large cell complexes. Secondly, the intermediate matrices which result from the application of the Smith form algorithm get filled-in even if one starts and ends with sparse matrices.

Efficient and probabilistic Smith normal form algorithms, as found in the LinBox library.
Simple homotopic reductions for pre-processing homology computations, as in the Perseus software package.
Algorithms to compute persistent homology of filtered complexes, as in the TDAstats R package.^[19]

Related Research Articles

In topology, knot theory is the study of mathematical knots. While inspired by knots which appear in daily life, such as those in shoelaces and rope, a mathematical knot differs in that the ends are joined so it cannot be undone, the simplest knot being a ring. In mathematical language, a knot is an embedding of a circle in 3-dimensional Euclidean space, $. Two mathematical knots are equivalent if one can be transformed into the other via a deformation of upon itself ; these transformations correspond to manipulations of a knotted string that do not involve cutting it or passing it through itself.$

In algebraic topology, a homology sphere is an n-manifold X having the homology groups of an n-sphere, for some integer $. That is,$

In quantum computing, a quantum algorithm is an algorithm which runs on a realistic model of quantum computation, the most commonly used model being the quantum circuit model of computation. A classical algorithm is a finite sequence of instructions, or a step-by-step procedure for solving a problem, where each step or instruction can be performed on a classical computer. Similarly, a quantum algorithm is a step-by-step procedure, where each of the steps can be performed on a quantum computer. Although all classical algorithms can also be performed on a quantum computer, the term quantum algorithm is usually used for those algorithms which seem inherently quantum, or use some essential feature of quantum computation such as quantum superposition or quantum entanglement.

<span class="mw-page-title-main">Polygon triangulation</span> Partition of a simple polygon into triangles

In computational geometry, polygon triangulation is the partition of a polygonal area $P$ into a set of triangles, i.e., finding a set of triangles with pairwise non-intersecting interiors whose union is $P$ .

The Fulkerson Prize for outstanding papers in the area of discrete mathematics is sponsored jointly by the Mathematical Optimization Society (MOS) and the American Mathematical Society (AMS). Up to three awards of $1,500 each are presented at each (triennial) International Symposium of the MOS. Originally, the prizes were paid out of a memorial fund administered by the AMS that was established by friends of the late Delbert Ray Fulkerson to encourage mathematical excellence in the fields of research exemplified by his work. The prizes are now funded by an endowment administered by MPS.

The Hauptvermutung of geometric topology is a now refuted conjecture asking whether any two triangulations of a triangulable space have subdivisions that are combinatorially equivalent, i.e. the subdivided triangulations are built up in the same combinatorial pattern. It was originally formulated as a conjecture in 1908 by Ernst Steinitz and Heinrich Franz Friedrich Tietze, but it is now known to be false.

In mathematics, Floer homology is a tool for studying symplectic geometry and low-dimensional topology. Floer homology is a novel invariant that arises as an infinite-dimensional analogue of finite-dimensional Morse homology. Andreas Floer introduced the first version of Floer homology, now called Lagrangian Floer homology, in his proof of the Arnold conjecture in symplectic geometry. Floer also developed a closely related theory for Lagrangian submanifolds of a symplectic manifold. A third construction, also due to Floer, associates homology groups to closed three-dimensional manifolds using the Yang–Mills functional. These constructions and their descendants play a fundamental role in current investigations into the topology of symplectic and contact manifolds as well as (smooth) three- and four-dimensional manifolds.

<span class="mw-page-title-main">Ciprian Manolescu</span> Romanian-American mathematician

Ciprian Manolescu is a Romanian-American mathematician, working in gauge theory, symplectic geometry, and low-dimensional topology. He is currently a professor of mathematics at Stanford University.

In computational complexity, problems that are in the complexity class NP but are neither in the class P nor NP-complete are called NP-intermediate, and the class of such problems is called NPI. Ladner's theorem, shown in 1975 by Richard E. Ladner, is a result asserting that, if P ≠ NP, then NPI is not empty; that is, NP contains problems that are neither in P nor NP-complete. Since it is also true that if NPI problems exist, then P ≠ NP, it follows that P = NP if and only if NPI is empty.

Regina is a suite of mathematical software for 3-manifold topologists. It focuses upon the study of 3-manifold triangulations and includes support for normal surfaces and angle structures.

<span class="mw-page-title-main">Unknotting problem</span> Determining whether a knot is the unknot

In mathematics, the unknotting problem is the problem of algorithmically recognizing the unknot, given some representation of a knot, e.g., a knot diagram. There are several types of unknotting algorithms. A major unresolved challenge is to determine if the problem admits a polynomial time algorithm; that is, whether the problem lies in the complexity class P.

In knot theory, a virtual knot is a generalization of knots in 3-dimensional Euclidean space, $R 3$ , to knots in thickened surfaces $modulo an equivalence relation called stabilization/destabilization. Here is required to be closed and oriented. Virtual knots were first introduced by Kauffman (1999).$

In mathematics, real algebraic geometry is the sub-branch of algebraic geometry studying real algebraic sets, i.e. real-number solutions to algebraic equations with real-number coefficients, and mappings between them.

Smale's problems are a list of eighteen unsolved problems in mathematics proposed by Steve Smale in 1998 and republished in 1999. Smale composed this list in reply to a request from Vladimir Arnold, then vice-president of the International Mathematical Union, who asked several mathematicians to propose a list of problems for the 21st century. Arnold's inspiration came from the list of Hilbert's problems that had been published at the beginning of the 20th century.

Greg Kuperberg is a Polish-born American mathematician known for his contributions to geometric topology, quantum algebra, and combinatorics. Kuperberg is a professor of mathematics at the University of California, Davis.

In applied mathematics, topological data analysis (TDA) is an approach to the analysis of datasets using techniques from topology. Extraction of information from datasets that are high-dimensional, incomplete and noisy is generally challenging. TDA provides a general framework to analyze such data in a manner that is insensitive to the particular metric chosen and provides dimensionality reduction and robustness to noise. Beyond this, it inherits functoriality, a fundamental concept of modern mathematics, from its topological nature, which allows it to adapt to new mathematical tools.

In discrete mathematics and theoretical computer science, the rotation distance between two binary trees with the same number of nodes is the minimum number of tree rotations needed to reconfigure one tree into another. Because of a combinatorial equivalence between binary trees and triangulations of convex polygons, rotation distance is equivalent to the flip distance for triangulations of convex polygons.

In discrete mathematics and theoretical computer science, reconfiguration problems are computational problems involving reachability or connectivity of state spaces.

References

↑ Afra J. Zomorodian, Topology for Computing, Cambridge, 2005, xi
↑ Blevins, Ann Sizemore; Bassett, Danielle S. (2020), Sriraman, Bharath (ed.), "Topology in Biology", Handbook of the Mathematics of the Arts and Sciences, Cham: Springer International Publishing, pp. 1–23, doi:10.1007/978-3-319-70658-0_87-1, ISBN 978-3-319-70658-0, S2CID 226695484
↑ Burton, Benjamin A. (2004). "Introducing Regina, the 3-manifold topology software" (PDF). Experimental Mathematics. 13 (3): 267–272. doi:10.1080/10586458.2004.10504538. S2CID 16566807.
↑ Schleimer, Saul (2011). "Sphere Recognition Lies in NP" (PDF)– via University of Warwick.
↑ Zentner, Raphael (2018). "Integer homology 3-spheres admit irreducible representations in SL(2,C)". Duke Mathematical Journal . 167 (9): 1643–1712. arXiv: 1605.08530 . doi:10.1215/00127094-2018-0004. S2CID 119275434.
↑ Kuperberg, Greg (2014). "Knottedness is in NP, modulo GRH". Advances in Mathematics . 256: 493–506. arXiv: 1112.0845 . doi: 10.1016/j.aim.2014.01.007 . S2CID 12634367.
↑ Burton, Benjamin A.; Hyam Rubinstein, J.; Tillmann, Stephan (2009). "The Weber-Seifert dodecahedral space is non-Haken". Transactions of the American Mathematical Society . 364 (2): 911–932. arXiv: 0909.4625 . doi:10.1090/S0002-9947-2011-05419-X. S2CID 18435885.
↑ J.Manning, Algorithmic detection and description of hyperbolic structures on 3-manifolds with solvable word problem, Geometry and Topology 6 (2002) 1–26
↑ S.Matveev, Algorithmic topology and the classification of 3-manifolds, Springer-Verlag 2003
↑ Kuperberg, Greg (2019). "Algorithmic homeomorphism of 3-manifolds as a corollary of geometrization". Pacific Journal of Mathematics. 301: 189–241. arXiv: 1508.06720 . doi:10.2140/pjm.2019.301.189. S2CID 119298413.
↑ Costantino, Francesco; Thurston, Dylan (2008). "3-manifolds efficiently bound 4-manifolds". Journal of Topology . 1 (3): 703–745. arXiv: math/0506577 . doi:10.1112/jtopol/jtn017. S2CID 15119190.
1 2 Hass, Joel; Lagarias, Jeffrey C.; Pippenger, Nicholas (1999), "The computational complexity of knot and link problems", Journal of the ACM , 46 (2): 185–211, arXiv: math/9807016 , doi:10.1145/301970.301971, S2CID 125854
↑ Lackenby, Marc (2021), "The efficient certification of Knottedness and Thurston norm", Advances in Mathematics , 387: 107796, arXiv: 1604.00290 , doi:10.1016/j.aim.2021.107796, S2CID 119307517
↑ " Main_Page ", The Knot Atlas .
↑ Maria, Clément (2019). "Parameterized complexity of quantum invariants". arXiv: 1910.00477 [math.GT].
↑ Przytycki, Jozef H. (2017). "The first coefficient of Homflypt and Kauffman polynomials: Vertigan proof of polynomial complexity using dynamic programming". arXiv: 1707.07733 [math.GT].
↑ Aharonov, Dorit; Jones, Vaughan; Landau, Zeph (2005). "A Polynomial Quantum Algorithm for Approximating the Jones Polynomial". arXiv: quant-ph/0511096 .
↑ Brown, Edgar H. (1957), "Finite Computability of Postnikov Complexes", Annals of Mathematics (2), 65 (1): 1–20, doi:10.2307/1969664, JSTOR 1969664
↑ Wadhwa, Raoul; Williamson, Drew; Dhawan, Andrew; Scott, Jacob (2018). "TDAstats: R pipeline for computing persistent homology in topological data analysis". Journal of Open Source Software. 3 (28): 860. Bibcode:2018JOSS....3..860R. doi: 10.21105/joss.00860 . PMC 7771879 . PMID 33381678.

External links

Books

Tomasz Kaczynski; Konstantin Mischaikow; Marian Mrozek (2004). Computational Homology. Springer. ISBN 0-387-40853-3.
Afra J. Zomorodian (2005). Topology for Computing. Cambridge. ISBN 0-521-83666-2.
Computational Topology: An Introduction, Herbert Edelsbrunner, John L. Harer, AMS Bookstore, 2010, ISBN 978-0-8218-4925-5

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[1] Afra J. Zomorodian, Topology for Computing, Cambridge, 2005, xi

[2] Blevins, Ann Sizemore; Bassett, Danielle S. (2020), Sriraman, Bharath (ed.), "Topology in Biology", Handbook of the Mathematics of the Arts and Sciences, Cham: Springer International Publishing, pp. 1–23, doi:10.1007/978-3-319-70658-0_87-1, ISBN 978-3-319-70658-0, S2CID 226695484

[3] Burton, Benjamin A. (2004). "Introducing Regina, the 3-manifold topology software" (PDF). Experimental Mathematics. 13 (3): 267–272. doi:10.1080/10586458.2004.10504538. S2CID 16566807.

[4] Schleimer, Saul (2011). "Sphere Recognition Lies in NP" (PDF)– via University of Warwick.

[5] Zentner, Raphael (2018). "Integer homology 3-spheres admit irreducible representations in SL(2,C)". Duke Mathematical Journal . 167 (9): 1643–1712. arXiv: 1605.08530 . doi:10.1215/00127094-2018-0004. S2CID 119275434.

[6] Kuperberg, Greg (2014). "Knottedness is in NP, modulo GRH". Advances in Mathematics . 256: 493–506. arXiv: 1112.0845 . doi: 10.1016/j.aim.2014.01.007 . S2CID 12634367.

[7] Burton, Benjamin A.; Hyam Rubinstein, J.; Tillmann, Stephan (2009). "The Weber-Seifert dodecahedral space is non-Haken". Transactions of the American Mathematical Society . 364 (2): 911–932. arXiv: 0909.4625 . doi:10.1090/S0002-9947-2011-05419-X. S2CID 18435885.

[8] J.Manning, Algorithmic detection and description of hyperbolic structures on 3-manifolds with solvable word problem, Geometry and Topology 6 (2002) 1–26

[9] S.Matveev, Algorithmic topology and the classification of 3-manifolds, Springer-Verlag 2003

[10] Kuperberg, Greg (2019). "Algorithmic homeomorphism of 3-manifolds as a corollary of geometrization". Pacific Journal of Mathematics. 301: 189–241. arXiv: 1508.06720 . doi:10.2140/pjm.2019.301.189. S2CID 119298413.

[11] Costantino, Francesco; Thurston, Dylan (2008). "3-manifolds efficiently bound 4-manifolds". Journal of Topology . 1 (3): 703–745. arXiv: math/0506577 . doi:10.1112/jtopol/jtn017. S2CID 15119190.

[HLP-12] 1 2 Hass, Joel; Lagarias, Jeffrey C.; Pippenger, Nicholas (1999), "The computational complexity of knot and link problems", Journal of the ACM , 46 (2): 185–211, arXiv: math/9807016 , doi:10.1145/301970.301971, S2CID 125854

[13] Lackenby, Marc (2021), "The efficient certification of Knottedness and Thurston norm", Advances in Mathematics , 387: 107796, arXiv: 1604.00290 , doi:10.1016/j.aim.2021.107796, S2CID 119307517

[14] " Main_Page ", The Knot Atlas .

[15] Maria, Clément (2019). "Parameterized complexity of quantum invariants". arXiv: 1910.00477 [math.GT].

[16] Przytycki, Jozef H. (2017). "The first coefficient of Homflypt and Kauffman polynomials: Vertigan proof of polynomial complexity using dynamic programming". arXiv: 1707.07733 [math.GT].

[17] Aharonov, Dorit; Jones, Vaughan; Landau, Zeph (2005). "A Polynomial Quantum Algorithm for Approximating the Jones Polynomial". arXiv: quant-ph/0511096 .

[18] Brown, Edgar H. (1957), "Finite Computability of Postnikov Complexes", Annals of Mathematics (2), 65 (1): 1–20, doi:10.2307/1969664, JSTOR 1969664

[19] Wadhwa, Raoul; Williamson, Drew; Dhawan, Andrew; Scott, Jacob (2018). "TDAstats: R pipeline for computing persistent homology in topological data analysis". Journal of Open Source Software. 3 (28): 860. Bibcode:2018JOSS....3..860R. doi: 10.21105/joss.00860 . PMC 7771879 . PMID 33381678.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]