Computertopologie - Computational topology

Algorithmische Topologie , oder Computational Topology , ist ein Teilgebiet der Topologie mit Überschneidungen mit Bereichen der Informatik , insbesondere Computergeometrie und Computational Complexity Theory .

Ein Hauptanliegen der algorithmischen Topologie ist, wie der Name schon sagt, die Entwicklung effizienter Algorithmen zur Lösung von Problemen, die auf natürliche Weise in Bereichen wie Computergeometrie , Grafik , Robotik , Strukturbiologie und Chemie auftreten , unter Verwendung von Methoden der berechenbaren Topologie .

Hauptalgorithmen nach Fachgebiet

Algorithmische 3-Mannigfaltigkeitstheorie

Eine große Familie von Algorithmen, die 3-Mannigfaltigkeiten betreffen, dreht sich um die Normalflächentheorie , ein Begriff, der mehrere Techniken umfasst, um Probleme in der 3-Mannigfaltigkeitstheorie in ganzzahlige lineare Programmierprobleme umzuwandeln.

  • Der 3-Sphären-Erkennungsalgorithmus von Rubinstein und Thompsons . Dies ist ein Algorithmus, der als Eingabe eine triangulierte 3-Mannigfaltigkeit verwendet und bestimmt, ob die Mannigfaltigkeit zur 3-Sphäre homöomorph ist oder nicht . Es hat eine exponentielle Laufzeit in der Anzahl von tetraedrischen Simplexen in der anfänglichen 3-Mannigfaltigkeit und auch ein exponentielles Speicherprofil. Darüber hinaus ist es im Softwarepaket Regina implementiert . Saul Schleimer fuhr fort zu zeigen, dass das Problem in der Komplexitätsklasse NP liegt . Weiterhin zeigte Raphael Zentner, dass das Problem in der Komplexitätsklasse coNP liegt, sofern die verallgemeinerte Riemann-Hypothese gilt. Er verwendet die Instanton-Eichtheorie, das Geometrisierungstheorem der 3-Mannigfaltigkeiten und nachfolgende Arbeiten von Greg Kuperberg über die Komplexität der Knotendetektion.
  • Die Connect-Summen- Zerlegung von 3-Mannigfaltigkeiten ist auch in Regina implementiert , hat eine exponentielle Laufzeit und basiert auf einem ähnlichen Algorithmus wie der 3-Sphären-Erkennungsalgorithmus.
  • Die Bestimmung, dass die Seifert-Weber-3-Mannigfaltigkeit keine inkompressible Fläche enthält, wurde algorithmisch von Burton, Rubinstein und Tillmann implementiert und basiert auf der Normalflächentheorie.
  • Der Manning-Algorithmus ist ein Algorithmus, um hyperbolische Strukturen auf 3-Mannigfaltigkeiten zu finden, deren Fundamentalgruppe eine Lösung des Wortproblems hat .

Gegenwärtig ist die JSJ-Zerlegung nicht algorithmisch in Computersoftware implementiert. Auch die Kompressionskörperzerlegung hat es nicht. Es gibt einige sehr beliebte und erfolgreiche Heuristiken, wie zum Beispiel SnapPea, das viel Erfolg bei der Berechnung von ungefähren hyperbolischen Strukturen auf triangulierten 3-Mannigfaltigkeiten hat. Es ist bekannt, dass die vollständige Klassifizierung von 3-Mannigfaltigkeiten algorithmisch erfolgen kann.

Konvertierungsalgorithmen

  • SnapPea implementiert einen Algorithmus, um ein planares Knoten- oder Verbindungsdiagramm in eine spitzwinklige Triangulation umzuwandeln. Dieser Algorithmus hat eine ungefähr lineare Laufzeit in der Anzahl von Kreuzungen im Diagramm und ein niedriges Speicherprofil. Der Algorithmus ähnelt dem Wirthinger-Algorithmus zum Konstruieren von Darstellungen der fundamentalen Gruppe von Link-Komplementen, die durch planare Diagramme gegeben werden. In ähnlicher Weise kann SnapPea chirurgische Darstellungen von 3 Mannigfaltigkeiten in Triangulationen der präsentierten 3 Mannigfaltigkeiten umwandeln .
  • D. Thurston und F. Costantino haben ein Verfahren zum Konstruieren einer triangulierten 4-Mannigfaltigkeit aus einer triangulierten 3-Mannigfaltigkeit. In ähnlicher Weise kann es verwendet werden, um chirurgische Darstellungen von triangulierten 3-Mannigfaltigkeiten zu konstruieren, obwohl das Verfahren im Prinzip nicht explizit als Algorithmus geschrieben ist, sollte es jedoch eine polynomielle Laufzeit in der Anzahl der Tetraeder der gegebenen 3-Mannigfaltigkeit-Triangulation haben.
  • S. Schleimer hat einen Algorithmus, der eine triangulierte 3-Mannigfaltigkeit erzeugt, wenn ein Wort (in Dehn-Twist- Generatoren) für die Abbildungsklassengruppe einer Fläche eingegeben wird. Die 3-Mannigfaltigkeit ist diejenige, die das Wort als die anhängende Karte für eine Heegaard-Aufspaltung der 3-Mannigfaltigkeit verwendet. Der Algorithmus basiert auf dem Konzept einer geschichteten Triangulation .

Algorithmische Knotentheorie

  • Die Bestimmung, ob ein Knoten trivial ist oder nicht, gehört bekanntermaßen zur Komplexitätsklasse NP
  • Das Problem der Bestimmung der Gattung eines Knotens hat bekanntlich die Komplexitätsklasse PSPACE .
  • Es gibt Polynomial-Time-Algorithmen zur Berechnung des Alexander-Polynoms eines Knotens.

Computerhomotopie

Computerhomologie

Die Berechnung von Homologiegruppen von Zellkomplexen reduziert sich darauf, die Grenzmatrizen in die Smith-Normalform zu bringen . Obwohl dies ein algorithmisch vollständig gelöstes Problem ist, gibt es verschiedene technische Hindernisse für eine effiziente Berechnung für große Komplexe. Es gibt zwei zentrale Hindernisse. Erstens weist der grundlegende Smith-Formalgorithmus eine kubische Komplexität in der Größe der beteiligten Matrix auf, da er Zeilen- und Spaltenoperationen verwendet, was ihn für große Zellkomplexe ungeeignet macht. Zweitens werden die Zwischenmatrizen, die sich aus der Anwendung des Smith-Formalgorithmus ergeben, auch dann ausgefüllt, wenn man mit dünnbesetzten Matrizen beginnt und endet.

  • Effiziente und wahrscheinlichkeitstheoretische Smith-Normalformalgorithmen, wie sie in der LinBox- Bibliothek zu finden sind.
  • Einfache Homotopenreduktionen für die Vorverarbeitung von Homologieberechnungen, wie im Perseus- Softwarepaket.
  • Algorithmen zur Berechnung der persistenten Homologie von gefilterten Komplexen, wie im TDAstats R-Paket.

Siehe auch

Verweise

  1. ^ Afra J. Zomorodian, Topologie für Computer , Cambridge, 2005, xi
  2. ^ Blevins, Ann Sizemore; Bassett, Danielle S. (2020), Sriraman, Bharath (Hrsg.), "Topology in Biology", Handbook of the Mathematics of the Arts and Sciences , Cham: Springer International Publishing, S. 1–23, doi : 10.1007/978 -3-319-70658-0_87-1 , ISBN 978-3-319-70658-0
  3. ^ B. ~ Burton. Einführung in Regina, die 3-Mannigfaltige-Topologie-Software, Experimental Mathematics 13 (2004), 267–272.
  4. ^ Schleimer, Saul (2011). „Sphere Recognition Lies in NP“ (PDF) – über University of Warwick .
  5. ^ Zentner, Raphael (2018). "Ganzzahlige Homologie 3-Sphären zulassen irreduzible Darstellungen in SL (2, C)". Herzog Mathematische Zeitschrift . 167 (9): 1643–1712. arXiv : 1605.08530 . doi : 10.1215/00127094-2018-0004 . S2CID  119275434 .
  6. ^ Kuperberg, Greg (2014). "Knotedness is in NP, modulo GRH" . Fortschritte in der Mathematik . 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). „Der Weber-Seifert-Dodekaederraum ist nicht-Haken“. Transaktionen der American Mathematical Society . 364 (2). arXiv : 0909.4625 . doi : 10.1090/S0002-9947-2011-05419-X .
  8. ^ J. Manning, Algorithmic Detection and Description of Hyperbolic Structures on 3-Mannigfaltigkeiten mit lösbarem Wortproblem, Geometry and Topology 6 (2002) 1–26
  9. ^ S. Matveev, Algorithmische Topologie und die Klassifikation von 3-Mannigfaltigkeiten, Springer-Verlag 2003
  10. ^ Costantino, Francesco; Thurston, Dylan (2008). „3-Mannigfaltigkeiten effizient gebunden 4-Mannigfaltigkeiten“. Zeitschrift für Topologie . 1 (3): 703–745. arXiv : mathe/0506577 . doi : 10.1112/jtopol/jtn017 . S2CID  15119190 .
  11. ^ Hass, Joel ; Lagarias, Jeffrey C .; Pippenger, Nicholas (1999), "Die Berechnungskomplexität von Knoten- und Verbindungsproblemen", Journal of the ACM , 46 (2): 185–211, arXiv : math/9807016 , doi : 10.1145/301970.301971 , S2CID  125854.
  12. ^ " Main_Page ", Der Knotenatlas .
  13. ^ Brown, Edgar H. (1957), "Finite Computability of Postnikov Complexes", Annals of Mathematics (2) , 65 : 1–20, doi : 10.2307/1969664
  14. ^ Wadhwa, Raoul; Williamson, Drew; Dhawan, Andrew; Scott, Jacob (2018). "TDAstats: R-Pipeline für die Berechnung persistenter Homologie in der topologischen Datenanalyse" . Zeitschrift für Open-Source-Software . 3 (28): 860. Bibcode : 2018JOSS....3..860R . doi : 10.21105/joss.00860 .

Externe Links

Bücher