Computational topology

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

A primary concern of algorithmic topology, as its name suggests, is to develop efficient algorithms for solving problems that arise naturally in fields such as computational geometry , graphics , robotics , structural biology and chemistry , using methods from computable topology . [1]

Major algorithms by subject area

Algorithmic 3-manifold theory

A large family of algorithms involving 3-manifolds revolves around normal surface theory, which is a phrase that encompasses several techniques to turn problems into 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 Regina software package . [2] Saul Schleimer went to the problem in the complexity class NP . [3] Furthermore, Raphael Zentner showed that the problem lies in the complexity class [4]Provided that the generalized Riemann hypothesis holds. He uses the momentum gauge theory, the geometrization theorem of 3-manifolds, and the subsequent work of Greg Kuperberg [5] 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 [6] and based on normal surface theory.
  • The Manning algorithm is an algorithm to find hyperbolic structures on 3-manifolds whose fundamental group has a solution to the word problem . [7]

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 SnapPeawhich 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. [8]

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 completions 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 three-manifold presentations of triangles, the procedure is not explicitly written on an algorithm in principle it should have a polynomial run-time in the tetrahedra number of the given 3-manifold triangulation. [9]
  • S. Schleimer has an algorithm which produces a triangulated 3-manifold, given input to 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 known in the NP complexity [10]
  • The problem of determining the genus of a knot is known to have complexity class PSPACE .
  • There are polynomial-time algorithms for the computation of the polynomial Alexander of a knot. [11]

Computational homotopy

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

Computational homology

Computation of homology groups of cell complex Reduces to Bringing the boundary matrices into normal form Smith . Although this is a completely problematic algorithmically, there are various technical obstacles to efficient computation for large complexes. There are two central obstacles. Firstly, the basic Smith form algorithm has many cubic complexity in the size of the matrix of operations that makes it easy for large cell complexes. Secondly, the intermediate matrices which results from the application of the Smith form algorithm get filled-in even if one starts and ends with sparse matrices.

  • Efficient and probabilistic normal Smith form algorithms, found in the LinBox library.
  • Simple homotopic cuts for pre-processing homology computations, as in the Perseus software package.
  • Algorithms to compute persistent homology of filtered complex.

See also

  • Computable Topology (the study of the topological nature of computation)
  • Computational geometry
  • Digital topology
  • Topological data analysis
  • Spatial-temporal reasoning
  • Experimental mathematics
  • Geometric modeling

References

  1. Jump up^ Afra J. Zomorodian,Topology for Computing, Cambridge, 2005, xi
  2. Jump up^ B. ~ Burton. Introducing Regina, the 3-manifold topology software, Experimental Mathematics 13 (2004), 267-272.
  3. Jump up^ http://www.warwick.ac.uk/~masgar/Maths/np.pdf
  4. Jump up^ R. Zentner. Integer homology 3-spheres admitted irreducible representations in SL (2, C),https://arxiv.org/abs/1605.08530
  5. Jump up^ G. Kuperberg. Knottedness is in NP, modulo GRH. Adv. Math., 256: 493-506, (2014),https://arxiv.org/abs/1112.0845
  6. Jump up^ BA Burton, JH Rubinstein and S. Tillmann, The Weber-Seifert dodecahedral space is non-Haken, Transactions of the American Mathematical Society 364 (2012), 911-932,http://arxiv.org/abs/0909.4625
  7. Jump up^ J.Manning, Algorithmic detection and description of hyperbolic structures on 3-manifolds with solvable word problem, Geometry and Topology 6 (2002) 1-26
  8. Jump up^ S.Matveev, Algorithmic topology and the classification of 3-manifolds, Springer-Verlag 2003
  9. Jump up^ F. Costantino, D.Thurston. 3-manifolds efficiently bound 4-manifolds. Journal of Topology 2008 1 (3): 703-745
  10. Jump up^ 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 .
  11. Jump up^ “Main_Page”, The Knot Atlas .
  12. Jump up^ EH Brown’s “Finite Computability of Postnikov Complexes” annals of Mathematics (2) 65 (1957) pp 1-20