Topologia computacional
La topologia computacional (en anglès "Computational topology" o "Algorithmic topology"), és una branca de la topologia amb pinzellades de ciències de la computació, en particular geometria computacional i teoria de la complexitat computacional.
Un dels principals camps de treball de la topologia algorítmica és desenvolupar algorismes eficients per a resoldre problemes que sorgeixen de manera natural en camps com la geometria computacional, els gràfics, la robòtica, la biologia estructural i la química, fent servir mètodes de la topologia computacional.[1][2]
Algorismes principals per àrea temàtica modifica
Teoria algorítmica 3-varietats modifica
Una gran família d'algorismes sobre 3-varietats giren al voltant de la teoria de superfícies normals, que és una frase que engloba diferents tècniques de transformació de problemes en teoria de 3-varietats en problemes de programació lineal entera.
- Algorisme de reconeixement d'una 3-esfera de Rubinstein i Thompson. És un algorisme que agafa com a paràmetre d'entrada una 3-varietat i determina si la varietat i la 3-esfera són homeomorfs. El seu temps d'execució és exponencial en funció del nombre de símplexs tetraèdrics en la 3-varietat inicial, el seu cost de memòria també és exponencial. Està implementat en el paquet de software Regina.[3] Saul Schleimer demostrà que el problema està contingut al conjunt NP.[4] A més, Raphael Zentner va demostrar que el problema recau en el conjunt de complexitat coNP,[5] si la hipòtesi generalitzada de Riemann és certa. Utilitza la teoria instanton gauge, el teorema de geometrització de 3-varietats i el treball posterior de Greg Kuperberg[6] sobre la complexitat de la detecció de nusos.
- La descomposició de la suma connexa d'una 3-varietat també està implementada en Regina, té un temps d'execució exponencial i està basat en un algorisme similar a l'algorisme de reconeixement d'una 3-esfera.
- Determinar que la 3-varietat de Seifert-Weber conté superfícies no incompressibles ha sigut algorítmicament implementat per Burton, Rubinstein i Tillmann,[7] basant-se en teoria de superfícies normals.
- L'algorisme de doblació és un algoritme per trobar estructures hiperbòliques en 3-varietats el grup fonamental de les quals tenen solució al world problem.[8]
Actualment, la JSJ descomposició no ha estat implementada com un algoritme en software per a computadors. Tampoc ho ha estat la descomposició cos-compressió. Existeixen heurístiques molt populars i amb bons resultats, com SnapPea que té molt èxit calculant estructures hiperbòliques aproximades en 3-varietats triangulades. Se sap que la classificació completa de 3-varietats es pot fer de manera algorítmica.[9]
Algorismes de conversió modifica
- SnapPea implementa un algorisme per convertir un nus planar en una triangulació cúspide. Aquest algoritme té aproximadament un temps d'execució lineal en funció dels encreuaments del diagrama, i un baix cost de memòria. L'algorisme és similar a l'algorisme de Wirthinger per construir representacions del grup fonamental de components connexes donades per diagrames planars. Similarment, SnapPea pot convertir presentacions quirúrgiques de 3-varietats en presentacions triangulades d'aquesta 3-varietat.
- D. Thurston i F. Costantino tenen un procediment per fer una 4-varietat triangulada des d'una 3-varietat triangulada. De la mateixa manera pot ser utilitzat per construir presentacions quirúrgiques de 3-varietats triangulades, encara que el procediment no està explícitament escrit com un algoritme en un principi hauria de tenir temps d'execució polinomial en funció dels tetraedres de les 3-varietats triangulades donades.[10]
- S. Schleimer té un algorisme que genera una 3-varietat triangulada, des d'una paraula com a input (en generadors Dehn twist) per al mapping class group d'una superfície. La 3-varietat és la que usa la paraula com el mapa d'adheriment (en anglès "gluing map" o "attaching map") per al Heegaard splitting de la 3-varietat.
Teoria algorítmica de nusos modifica
- Determinar si un nus és trivial, és un problema NP complex.[11]
- El problema de determinació del gènere de nus té complexitat PSPACE.
- Hi ha algorismes amb temps d'execució polinomial per calcular el polinomi d'Alexander d'un nus.[12]
Homotopia computacional modifica
- Mètodes computacionals per al grup homotopic d'esferes.
- Mètodes computacionals per solucionar sistemes d'equacions polinòmiques.
- Brown té un algorisme que calcula el grup homotòpic d'espais que són Postnikov complexos finits,[13] encara que no és majoritàriament considerat implementable.
Homologia computacional modifica
La computació de grups homològics de complexos cel·lulars redueix portar les matrius límit a la seva forma normal de Smith. Encara que això és un problema pel qual existeix un algoritme, hi ha força obstacles tècnics que impedeixen el càlcul eficient per grans complexos. Principalment hi ha dos obstacles. Primerament, l'algoritme bàsic de la forma normal de Smith té complexitat cúbica en funció de la mida de la matriu d'entrada, ja que utilitza operacions en files i columnes, cosa que el fa inadequat per grans complexos cel·lulars. Segonament, les matrius intermèdies que sorgeixen de l'aplicació de l'algoritme de la forma normal de Smith s'omplen molt, encara que es comenci amb matrius disperses.
- Algoritmes de forma normal de Smith eficients i probabilístics, com els trobats a la llibreria LinBox.
- Reduccions homotòpiques simples per preprocessar els càlculs homotòpics, com al paquet de software Perseus.
- Algoritmes per computar l'homologia persistent de complexos filtrats, com al paquet d'R, TDAstats.[14]
Vegeu també modifica
Referències modifica
- ↑ Afra J. Zomorodian, Topology for Computing, Cambridge, 2005, xi
- ↑ Blevins, Ann Sizemore & Bassett, Danielle S. (2020), Sriraman, Bharath, ed., Topology in Biology, Cham: Springer International Publishing, pàg. 1–23, ISBN 978-3-319-70658-0, DOI 10.1007/978-3-319-70658-0_87-1
- ↑ Burton, Benjamin A. «Introducing Regina, the 3-manifold topology software». Experimental Mathematics, vol. 13, 2004, pàg. 267—272. DOI: 10.1080/10586458.2004.10504538.
- ↑ Schleimer, Saul. «Sphere Recognition Lies in NP», 2011.
- ↑ Zentner, Raphael «Integer homology 3-spheres admit irreducible representations in SL(2,C)». Duke Mathematical Journal, vol. 167, 9, 2018, pàg. 1643–1712. arXiv: 1605.08530. DOI: 10.1215/00127094-2018-0004.
- ↑ Kuperberg, Greg «Knottedness is in NP, modulo GRH». Advances in Mathematics, vol. 256, 2014, pàg. 493–506. arXiv: 1112.0845. DOI: 10.1016/j.aim.2014.01.007.
- ↑ Burton, Benjamin A.; Hyam Rubinstein, J.; Tillmann, Stephan «The Weber-Seifert dodecahedral space is non-Haken». Transactions of the American Mathematical Society, vol. 364, 2009. arXiv: 0909.4625. DOI: 10.1090/S0002-9947-2011-05419-X.
- ↑ J.Manning, Algorithmic detection and description of hyperbolic structures on 3-manifolds with solvable word problem, Geometry and Topology 6 (2002) 1–26
- ↑ S.Matveev, Algorithmic topology and the classification of 3-manifolds, Springer-Verlag 2003
- ↑ Costantino, Francesco; Thurston, Dylan «3-manifolds efficiently bound 4-manifolds». Journal of Topology, vol. 1, 3, 2008, pàg. 703–745. arXiv: math/0506577. DOI: 10.1112/jtopol/jtn017.
- ↑ Hass, Joel; Lagarias, Jeffrey C. & Pippenger, Nicholas (1999), "The computational complexity of knot and link problems", Journal of the ACM 46 (2): 185–211, DOI 10.1145/301970.301971.
- ↑ Plantilla:Knot Atlas
- ↑ Brown, Edgar H. (1957), "Finite Computability of Postnikov Complexes", Annals of Mathematics (2) 65: 1–20, DOI 10.2307/1969664
- ↑ Wadhwa, Raoul; Williamson, Drew; Dhawan, Andrew; Scott, Jacob «TDAstats: R pipeline for computing persistent homology in topological data analysis». Journal of Open Source Software, vol. 3, 28, 2018, pàg. 860. Bibcode: 2018JOSS....3..860R. DOI: 10.21105/joss.00860. PMID: 33381678.