Computational topology

Last updated

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.

Contents

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, social science, structural biology, and chemistry, using methods from computable topology. [1] [2] [3]

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, [10] in fact, it is known that deciding whether two closed, oriented 3-manifolds given by triangulations (simplicial complexes) are equivalent (homeomorphic) is elementary recursive. [11] 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. [12]
  • 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

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

Related Research Articles

<span class="mw-page-title-main">Knot theory</span> Study of mathematical knots

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,

<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.

In mathematics, the Alexander polynomial is a knot invariant which assigns a polynomial with integer coefficients to each knot type. James Waddell Alexander II discovered this, the first knot polynomial, in 1923. In 1969, John Conway showed a version of this polynomial, now called the Alexander–Conway polynomial, could be computed using a skein relation, although its significance was not realized until the discovery of the Jones polynomial in 1984. Soon after Conway's reworking of the Alexander polynomial, it was realized that a similar skein relation was exhibited in Alexander's paper on his polynomial.

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 symplectic 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.

<span class="mw-page-title-main">Normal surface</span>

In mathematics, a normal surface is a surface inside a triangulated 3-manifold that intersects each tetrahedron in several components called normal disks. Each normal disk is either a triangle which cuts off a vertex of the tetrahedron, or a quadrilateral which separates pairs of vertices. In a given tetrahedron there cannot be two quadrilaterals separating different pairs of vertices, since such quadrilaterals would intersect in a line, causing the surface to be self-intersecting.

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.

<span class="mw-page-title-main">Regina (program)</span>

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, R3, 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).

Smale's problems is 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.

<span class="mw-page-title-main">Greg Kuperberg</span> Polish American mathematician

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.

<span class="mw-page-title-main">Polymake</span>

polymake is a software for the algorithmic treatment of convex polyhedra.

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

In discrete mathematics and theoretical computer science, the flip distance between two triangulations of the same point set is the number of flips required to transform one triangulation into another. A flip removes an edge between two triangles in the triangulation and then adds the other diagonal in the edge's enclosing quadrilateral, forming a different triangulation of the same point set.

References

  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. ↑ Chiou, Lyndie (26 March 2024). "Topologists Tackle the Trouble With Poll Placement". Quanta Magazine. Retrieved 1 April 2024.
  4. ↑ 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.
  5. ↑ Schleimer, Saul (2011). "Sphere Recognition Lies in NP" (PDF)– via University of Warwick.
  6. ↑ 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.
  7. ↑ 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.
  8. ↑ 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.
  9. ↑ J.Manning, Algorithmic detection and description of hyperbolic structures on 3-manifolds with solvable word problem, Geometry and Topology 6 (2002) 1–26
  10. ↑ S.Matveev, Algorithmic topology and the classification of 3-manifolds, Springer-Verlag 2003
  11. ↑ 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.
  12. ↑ 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.
  13. 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
  14. ↑ 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
  15. ↑ " Main_Page ", The Knot Atlas .
  16. ↑ Maria, Clément (2019). "Parameterized complexity of quantum invariants". arXiv: 1910.00477 [math.GT].
  17. ↑ 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].
  18. ↑ Aharonov, Dorit; Jones, Vaughan; Landau, Zeph (2005). "A Polynomial Quantum Algorithm for Approximating the Jones Polynomial". arXiv: quant-ph/0511096 .
  19. ↑ Shen, Li; Liu, Jian; Wei, Guo-Wei (2024). "Evolutionary Khovanov homology". AIMS Mathematics. 9 (9): 26139–26165. arXiv: 2406.02821 . doi: 10.3934/math.20241277 .{{cite journal}}: CS1 maint: date and year (link)
  20. ↑ Brown, Edgar H. (1957), "Finite Computability of Postnikov Complexes", Annals of Mathematics (2), 65 (1): 1–20, doi:10.2307/1969664, JSTOR   1969664
  21. ↑ 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.

Books

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.