Computational topology

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.

A primary concern of algorithmic topology, as its name suggests, is to develop efficient algorithms for solving topological problems using topological methods from computable topology to solve algorithmic problems from other fields.

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.

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.[5]

Conversion algorithms

Algorithmic knot theory

Computational homotopy

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.

See also

References

  1. B.~Burton. Introducing Regina, the 3-manifold topology software, Experimental Mathematics 13 (2004), 267–272.
  2. http://www.warwick.ac.uk/~masgar/Maths/np.pdf
  3. B. A. Burton, J. H. 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
  4. J.Manning, Algorithmic detection and description of hyperbolic structures on 3-manifolds with solvable word problem, Geometry and Topology 6 (2002) 1–26
  5. S.Matveev, Algorithmic topology and the classification of 3-manifolds, Springer-Verlag 2003
  6. F. Costantino, D.Thurston. 3-manifolds efficiently bound 4-manifolds. Journal of Topology 2008 1(3):703–745
  7. 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.
  8. "Main_Page", The Knot Atlas.
  9. E H Brown's "Finite Computability of Postnikov Complexes" annals of Mathematics (2) 65 (1957) pp 1–20

External links

Books