Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Computational topology
open-in-new
<h2 id="major-algorithms-by-subject-area">Major algorithms by subject area</h2> <h3>Algorithmic 3-manifold theory</h3> <p>A large family of algorithms concerning <a href="/facts/3-manifold/48yr0Tzx">3-manifolds</a> revolve around <a href="/facts/Normal_surface/FST577H9">normal surface</a> theory, which is a phrase that encompasses several techniques to turn problems in 3-manifold theory into integer linear programming problems. </p> <ul><li><i>Rubinstein and Thompson's 3-sphere recognition algorithm</i>. This is an algorithm that takes as input a <a href="/facts/Triangulation_(topology)/u58jNL6L">triangulated</a> <a href="/facts/3-manifold/48yr0Tzx">3-manifold</a> and determines whether or not the manifold is <a href="/facts/Homeomorphism/jMfWg3Mn">homeomorphic</a> to the <a href="/facts/3-sphere/u67nImpY">3-sphere</a>. It has exponential run-time in the number of tetrahedral simplexes in the initial 3-manifold, and also an exponential memory profile. Saul Schleimer went on to show the problem lies in the complexity class <a href="/facts/NP_(complexity)/6muUfVMI">NP</a>.<a class="footnote-ref" id="fnref:4" href="#fn:4"><sup>4</sup></a> Furthermore, Raphael Zentner showed that the problem lies in the complexity class coNP,<a class="footnote-ref" id="fnref:5" href="#fn:5"><sup>5</sup></a> provided that the generalized Riemann hypothesis holds. He uses instanton gauge theory, the geometrization theorem of 3-manifolds, and subsequent work of Greg Kuperberg <a class="footnote-ref" id="fnref:6" href="#fn:6"><sup>6</sup></a> on the complexity of knottedness detection.</li> <li>The <a href="/facts/Connected_sum/TycjIkQe">connect-sum</a> decomposition of 3-manifolds is also implemented in <a href="/facts/Regina_(program)/4zV0durp">Regina</a>, has exponential run-time and is based on a similar algorithm to the 3-sphere recognition algorithm.</li> <li>Determining that the Seifert-Weber 3-manifold contains no incompressible surface has been algorithmically implemented by Burton, Rubinstein and Tillmann<a class="footnote-ref" id="fnref:7" href="#fn:7"><sup>7</sup></a> and based on normal surface theory.</li> <li>The <i>Manning algorithm</i> is an algorithm to find hyperbolic structures on 3-manifolds whose <a href="/facts/Fundamental_group/VyYtLqSP">fundamental group</a> have a solution to the <a href="/facts/Word_problem_for_groups/eKBrkBPv">word problem</a>.<a class="footnote-ref" id="fnref:8" href="#fn:8"><sup>8</sup></a></li></ul> <p>At present the <a href="/facts/JSJ_decomposition/6y5kyIya">JSJ decomposition</a> has not been implemented algorithmically in computer software. Neither has the compression-body decomposition. There are some very popular and successful heuristics, such as <a href="/facts/SnapPea/hx3QbENv">SnapPea</a> 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,<a class="footnote-ref" id="fnref:9" href="#fn:9"><sup>9</sup></a> in fact, it is known that deciding whether two closed, oriented 3-manifolds given by <a href="/facts/Triangulation_(topology)/u58jNL6L">triangulations</a> (simplicial complexes) are equivalent (homeomorphic) is <a href="/facts/Elementary_recursive/gxGLXF4R">elementary recursive</a>.<a class="footnote-ref" id="fnref:10" href="#fn:10"><sup>10</sup></a> This generalizes the result on 3-sphere recognition. </p> <h4>Conversion algorithms</h4> <ul><li><a href="/facts/SnapPea/hx3QbENv">SnapPea</a> implements an algorithm to convert a planar <a href="/facts/Knot_(mathematics)/UMtKJ36m">knot</a> or <a href="/facts/Knot_(mathematics)/UMtKJ36m">link diagram</a> 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 <a href="/facts/Fundamental_group/VyYtLqSP">fundamental group</a> of link complements given by planar diagrams. Similarly, SnapPea can convert <a href="/facts/Surgery_theory/5Ip2RAGW">surgery</a> presentations of 3-manifolds into triangulations of the presented 3-manifold.</li> <li>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.<a class="footnote-ref" id="fnref:11" href="#fn:11"><sup>11</sup></a></li> <li>S. Schleimer has an algorithm which produces a triangulated 3-manifold, given input a word (in <a href="/facts/Dehn_twist/49IL7NhB">Dehn twist</a> generators) for the <a href="/facts/Mapping_class_group/buQm001q">mapping class group</a> of a surface. The 3-manifold is the one that uses the word as the attaching map for a <a href="/facts/Heegaard_splitting/EhLrsMVH">Heegaard splitting</a> of the 3-manifold. The algorithm is based on the concept of a <i>layered triangulation</i>.</li></ul> <h3>Algorithmic knot theory</h3> <p><a href="/facts/Unknotting_problem/NSxIY5C6">Determining whether or not a knot is trivial</a> is known to be in the complexity classes <a href="/facts/NP_(complexity)/6muUfVMI">NP</a><a class="footnote-ref" id="fnref:12" href="#fn:12"><sup>12</sup></a> as well as <a href="/facts/Co-NP/M67JgWNa">co-NP</a>.<a class="footnote-ref" id="fnref:13" href="#fn:13"><sup>13</sup></a> The problem of determining the <a href="/facts/Knot_genus/LqkqdPl8">genus of a knot in a 3-manifold</a> is <a href="/facts/NP-complete/NFPv56DU">NP-complete</a>;<a class="footnote-ref" id="fnref:14" href="#fn:14"><sup>14</sup></a> however, while <a href="/facts/NP_(complexity)/6muUfVMI"> NP</a> remains an upper bound on the complexity of determining the genus of a knot in R3 or S3, as of 2006 it was unknown whether the algorithmic problem of determining the genus of a knot in those particular 3-manifolds was still <a href="/facts/NP-hard/mQeNPv4R">NP-hard</a>.<a class="footnote-ref" id="fnref:15" href="#fn:15"><sup>15</sup></a> </p> <h3>Computational homotopy</h3> <ul><li>Computational methods for <a href="/facts/Homotopy_groups_of_spheres/YMENlGgd">homotopy groups of spheres</a>.</li> <li>Computational methods for solving <a href="/facts/Systems_of_polynomial_equations/1456MrT2">systems of polynomial equations</a>.</li> <li>Brown has an algorithm to compute the homotopy groups of spaces that are finite <a href="/facts/Postnikov_system/wdHYnz7F">Postnikov complexes</a>,<a class="footnote-ref" id="fnref:16" href="#fn:16"><sup>16</sup></a> although it is not widely considered implementable.</li></ul> <h3>Computational homology</h3> <p>Computation of <a href="/facts/Homology_group/VFJmryEW">homology groups</a> of <a href="/facts/CW_complex/rN7buLMo">cell complexes</a> reduces to bringing the boundary matrices into <a href="/facts/Smith_normal_form/pchMkW7Q">Smith normal form</a>. 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. </p> <ul><li>Efficient and probabilistic Smith normal form algorithms, as found in the <a href="http://www.linalg.org">LinBox</a> library.</li> <li>Simple homotopic reductions for pre-processing homology computations, as in the <a href="http://www.sas.upenn.edu/~vnanda/perseus/index.html">Perseus</a> software package.</li> <li>Algorithms to compute <a href="/facts/Persistent_homology/Mfmn1sIc">persistent homology</a> of <a href="/facts/Filtration_(mathematics)/qcvLvKRI">filtered</a> complexes, as in the <a href="https://CRAN.R-project.org/package=TDAstats">TDAstats</a> R package.<a class="footnote-ref" id="fnref:17" href="#fn:17"><sup>17</sup></a></li> <li>In some applications, such as in TDA, it is useful to have representatives of (co)homology classes that are as "small" as possible. This is known as the problem of (co)homology localization. On triangulated manifolds, given a chain representing a homology class, it is in general NP-hard to approximate the minimum-support homologous chain.<a class="footnote-ref" id="fnref:18" href="#fn:18"><sup>18</sup></a> However, the particular setting of approximating 1-cohomology localization on triangulated 2-manifolds is one of only three known problems whose hardness is equivalent to the <a href="/facts/Unique_Games_Conjecture/gDYzTfRG">Unique Games Conjecture</a>.<a class="footnote-ref" id="fnref:19" href="#fn:19"><sup>19</sup></a></li></ul> <h2 id="see-also">See also</h2> <ul><li><a href="/facts/Computable_topology/NWmdxnyF">Computable topology</a> (the study of the topological nature of computation)</li> <li><a href="/facts/Computational_geometry/eeaotQtl">Computational geometry</a></li> <li><a href="/facts/Digital_topology/UdhbeLPD">Digital topology</a></li> <li><a href="/facts/Topological_data_analysis/Lz5ltT7l">Topological data analysis</a></li> <li><a href="/facts/Spatial-temporal_reasoning/5P0XlqC4">Spatial-temporal reasoning</a></li> <li><a href="/facts/Experimental_mathematics/NfuxNMIz">Experimental mathematics</a></li> <li><a href="/facts/Geometric_modeling/SGyQGku9">Geometric modeling</a></li></ul> <h2 id="external-links">External links</h2> <ul><li><a href="http://www.math.uiuc.edu/~nmd/computop/">CompuTop software archive</a></li> <li><a href="http://www.msri.org/calendar/workshops/WorkshopInfo/381/show_workshop/">Workshop on Application of Topology in Science and Engineering</a></li> <li><a href="http://comptop.stanford.edu/">Computational Topology at Stanford University</a> <a href="https://web.archive.org/web/20070622154434/http://comptop.stanford.edu/">Archived</a> 2007-06-22 at the <a href="/facts/Wayback_Machine/nmQ3a6JC">Wayback Machine</a></li> <li><a href="http://chomp.rutgers.edu/">Computational Homology Software (CHomP) at Rutgers University</a>.</li> <li><a href="http://redhom.ii.uj.edu.pl/">Computational Homology Software (RedHom) at Jagellonian University</a> <a href="https://web.archive.org/web/20130715025307/http://www.redhom.ii.uj.edu.pl/">Archived</a> 2013-07-15 at the <a href="/facts/Wayback_Machine/nmQ3a6JC">Wayback Machine</a>.</li> <li><a href="https://web.archive.org/web/20131102213643/http://www.math.rutgers.edu/~vidit/perseus.html">The Perseus software project for (persistent) homology</a>.</li> <li><a href="https://code.google.com/p/javaplex/">The javaPlex Persistent Homology software at Stanford</a>.</li> <li><a href="https://code.google.com/p/phat">PHAT: persistent homology algorithms toolbox</a>.</li></ul> <h2 id="books">Books</h2> <ul><li>Tomasz Kaczynski; Konstantin Mischaikow; Marian Mrozek (2004). <a href="https://books.google.com/books?id=AShKtpi3GecC"><i>Computational Homology</i></a>. Springer. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 0-387-40853-3.</li> <li>Afra J. Zomorodian (2005). <a href="https://books.google.com/books?id=oKEGGMgnWKcC"><i>Topology for Computing</i></a>. Cambridge. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 0-521-83666-2.</li> <li><a href="https://books.google.com/books?id=MDXa6gFRZuIC">Computational Topology: An Introduction</a>, Herbert Edelsbrunner, John L. Harer, AMS Bookstore, 2010, <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-0-8218-4925-5</li></ul> <h2 id="references">References</h2> <ol> <li id="fn:1"><p>Afra J. Zomorodian, Topology for Computing, Cambridge, 2005, xi <a href="https://books.google.com/books?id=oKEGGMgnWKcC" target="_blank">https://books.google.com/books?id=oKEGGMgnWKcC</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li> <li id="fn:2"><p>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 <a href="978-3-319-70658-0" target="_blank">978-3-319-70658-0</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li> <li id="fn:3"><p>Chiou, Lyndie (26 March 2024). "Topologists Tackle the Trouble With Poll Placement". Quanta Magazine. Retrieved 1 April 2024. <a href="https://www.quantamagazine.org/topologists-tackle-the-trouble-with-poll-placement-20240326/" target="_blank">https://www.quantamagazine.org/topologists-tackle-the-trouble-with-poll-placement-20240326/</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li> <li id="fn:4"><p>Schleimer, Saul (2011). "Sphere Recognition Lies in NP" (PDF) – via University of Warwick. <a href="http://www.warwick.ac.uk/~masgar/Maths/np.pdf" target="_blank">http://www.warwick.ac.uk/~masgar/Maths/np.pdf</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></p></li> <li id="fn:5"><p>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. <a href="/wiki/Duke_Mathematical_Journal" target="_blank">/wiki/Duke_Mathematical_Journal</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></p></li> <li id="fn:6"><p>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. <a href="https://doi.org/10.1016%2Fj.aim.2014.01.007" target="_blank">https://doi.org/10.1016%2Fj.aim.2014.01.007</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></p></li> <li id="fn:7"><p>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. <a href="/wiki/Transactions_of_the_American_Mathematical_Society" target="_blank">/wiki/Transactions_of_the_American_Mathematical_Society</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></p></li> <li id="fn:8"><p>J.Manning, Algorithmic detection and description of hyperbolic structures on 3-manifolds with solvable word problem, Geometry and Topology 6 (2002) 1–26 <a href="#fnref:8" class="footnote-back-ref">↩</a></p></li> <li id="fn:9"><p>S.Matveev, Algorithmic topology and the classification of 3-manifolds, Springer-Verlag 2003 <a href="#fnref:9" class="footnote-back-ref">↩</a></p></li> <li id="fn:10"><p>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. <a href="/wiki/ArXiv_(identifier)" target="_blank">/wiki/ArXiv_(identifier)</a> <a href="#fnref:10" class="footnote-back-ref">↩</a></p></li> <li id="fn:11"><p>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. <a href="/wiki/Journal_of_Topology" target="_blank">/wiki/Journal_of_Topology</a> <a href="#fnref:11" class="footnote-back-ref">↩</a></p></li> <li id="fn:12"><p>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 <a href="/wiki/Joel_Hass" target="_blank">/wiki/Joel_Hass</a> <a href="#fnref:12" class="footnote-back-ref">↩</a></p></li> <li id="fn:13"><p>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 <a href="/wiki/Marc_Lackenby" target="_blank">/wiki/Marc_Lackenby</a> <a href="#fnref:13" class="footnote-back-ref">↩</a></p></li> <li id="fn:14"><p>Agol, Ian; Hass, Joel; Thurston, William (2006), "The computational complexity of knot genus and spanning area", Trans. Amer. Math. Soc., 358 (9): 3821–3850, arXiv:math/0205057, doi:10.1090/S0002-9947-05-03919-X <a href="/wiki/Joel_Hass" target="_blank">/wiki/Joel_Hass</a> <a href="#fnref:14" class="footnote-back-ref">↩</a></p></li> <li id="fn:15"><p>Agol, Ian; Hass, Joel; Thurston, William (2006), "The computational complexity of knot genus and spanning area", Trans. Amer. Math. Soc., 358 (9): 3821–3850, arXiv:math/0205057, doi:10.1090/S0002-9947-05-03919-X <a href="/wiki/Joel_Hass" target="_blank">/wiki/Joel_Hass</a> <a href="#fnref:15" class="footnote-back-ref">↩</a></p></li> <li id="fn:16"><p>Brown, Edgar H. (1957), "Finite Computability of Postnikov Complexes", Annals of Mathematics (2), 65 (1): 1–20, doi:10.2307/1969664, JSTOR 1969664 <a href="/wiki/Edgar_H._Brown" target="_blank">/wiki/Edgar_H._Brown</a> <a href="#fnref:16" class="footnote-back-ref">↩</a></p></li> <li id="fn:17"><p>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. <a href="https://www.ncbi.nlm.nih.gov/pmc/articles/PMC7771879" target="_blank">https://www.ncbi.nlm.nih.gov/pmc/articles/PMC7771879</a> <a href="#fnref:17" class="footnote-back-ref">↩</a></p></li> <li id="fn:18"><p>Chen, Chao; Freedman, Daniel (2011). "Hardness results for homology localization". Discrete & Computational Geometry. 45 (3): 425–448. doi:10.1007/s00454-010-9322-8. MR 2770545. Preliminary version appeared at SODA 2010. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:18" class="footnote-back-ref">↩</a></p></li> <li id="fn:19"><p>Grochow, Joshua; Tucker-Foltz, Jamie (2018). Computational Topology and the Unique Games Conjecture. 34th Internat. Symp. Comput. Geom. (SoCG) '18. p. 43:1-43:16. arXiv:1803.06800. doi:10.4230/LIPIcs.SoCG.2018.43. MR 3824287.. <a href="/wiki/ArXiv_(identifier)" target="_blank">/wiki/ArXiv_(identifier)</a> <a href="#fnref:19" class="footnote-back-ref">↩</a></p></li> </ol>