계산 위상

Computational topology

알고리즘 위상 또는 계산 위상은 컴퓨터 과학의 영역, 특히 계산 기하학 및 계산 복잡성 이론과 중복되는 위상의 하위 영역이다.

알고리즘 위상의 주요 관심사는 이름에서 알 수 있듯이 계산 가능한 위상의 방법을 사용하여 계산 기하학, 그래픽, 로봇 공학, 구조 생물학 및 화학 등의 분야에서 자연적으로 발생하는 문제를 해결하기 위한 효율적인 알고리즘을 개발하는 것이다.[1][2]

주제 영역별 주요 알고리즘

알고리즘 3-매니폴드 이론

3-매니폴드와 관련된 알고리즘의 대가족은 정상 표면이론을 중심으로 회전하는데, 이것은 3-매니폴드 이론의 문제를 정수 선형 프로그래밍 문제로 바꾸기 위한 몇 가지 기법을 포괄하는 구절이다.

  • 루빈스타인과 톰슨의 3-sphere 인식 알고리즘. 이것은 삼각형 3-매니폴드를 입력으로 하여 다지관의 3-sphere에 대한 동형 여부를 결정하는 알고리즘이다. 초기 3-manifold의 사면 단순함 수에서 지수 런타임을 가지며, 지수 메모리 프로필도 가지고 있다. 더욱이 소프트웨어 패키지 레지나에서도 구현되고 있다.[3] Saul Schleimer는 계속해서 문제가 복잡도 등급 NP에 있다는 것을 보여주었다.[4] 더욱이 라파엘 젠트너는 일반화된 리만 가설이 유지된다면 문제는 복잡도 등급 coNP에 있다는 것을 보여주었다.[5] 그는 인스턴트온 게이지 이론, 3마니폴드의 기하학적 정리, 매듭짓기 감지 복잡성에 대한 그레그 쿠퍼버그의 후속 작업을 사용한다.
  • 3-manifolds의 connect-sum 분해는 레지나에서도 구현되며, 지수 런타임을 가지며, 3-sphere 인식 알고리즘과 유사한 알고리즘을 기반으로 한다.
  • 세이퍼트-베버 3-매니폴드가 비압축성 표면을 포함하지 않는다고 판단하는 것은 버튼, 루빈스타인, 틸먼에[7] 의해 알고리즘적으로 구현되었고 정상적인 표면 이론에 기초하였다.
  • 매닝 알고리즘은 기본 그룹이 문제라는 단어에 대한 해답을 가지고 있는 3개의 매니폴드에서 쌍곡 구조를 찾는 알고리즘이다.[8]

현재 JSJ 분해는 컴퓨터 소프트웨어에서 알고리즘적으로 구현되지 않았다. 압축-신체 분해도 마찬가지야 삼각형 3마니폴드의 대략적인 쌍곡 구조를 계산하는 데 많은 성공을 거둔 SnapPea와 같은 매우 인기 있고 성공적인 경험적 발견이 있다. 3마니폴드의 완전한 분류는 알고리즘적으로 할 수 있는 것으로 알려져 있다.[9]

변환 알고리즘

  • SnapPea는 평면 매듭 또는 링크 다이어그램을 쿠스드 삼각 측량으로 변환하는 알고리즘을 구현한다. 이 알고리즘은 다이어그램의 교차 횟수에 대략적인 선형 런타임과 낮은 메모리 프로필을 가지고 있다. 알고리즘은 평면도가 제공하는 링크 보완의 기본 그룹의 프리젠테이션을 구성하기 위한 위링거 알고리즘과 유사하다. 마찬가지로 SnapPea는 3-manifold의 수술 프레젠테이션을 3-manifold의 삼각형으로 변환할 수 있다.
  • D. Thurston과 F. 코스탄티노에는 3마니폴드에서 4마니폴드를 삼각형으로 만드는 절차가 있다. 마찬가지로, 삼각형 3-매니폴드의 수술 프레젠테이션을 구성하는 데 사용할 수 있지만, 절차가 원칙적으로 알고리즘으로 명시적으로 작성되지는 않지만, 주어진 3-매니폴드 삼각형의 4-헤드라 수에 다항식 런타임을 가져야 한다.[10]
  • S. Schleimer는 표면의 매핑 클래스 그룹에 대해 주어진 단어(Dehn twist generators)를 입력하는 삼각형 3-manifold를 생성하는 알고리즘을 가지고 있다. 3매니폴드는 이 단어를 3매니폴드의 희가르드 분할을 위한 첨부 지도로 사용하는 것이다. 알고리즘은 레이어드 삼각 측량 개념에 기초한다.

알고리즘 매듭 이론

  • 매듭이 사소한지 여부를 결정하는 것은 복잡도 등급 NP에[11] 있는 것으로 알려져 있다.
  • 매듭의 속을 결정하는 문제는 복잡도 등급인 PSPACE를 가진 것으로 알려져 있다.
  • 매듭의 알렉산더 다항식 계산을 위한 다항식 시간 알고리즘이 있다.[12]

계산 호모토피

계산 호몰로지

셀 콤플렉스의 동질학 그룹의 계산은 경계 행렬을 Smith 정상 형태로 가져오는 것으로 감소한다. 알고리즘적으로 완전히 해결된 문제지만 대규모 단지의 효율적인 연산을 위해서는 다양한 기술적 장애물이 존재한다. 두 가지 중심 장애물이 있다. 첫째로, 기본 스미스 양식 알고리즘은 행과 기둥 연산을 사용하기 때문에 관련된 매트릭스 크기의 입방체 복잡성을 가지고 있어 대형 셀 콤플렉스에 적합하지 않다. 둘째, 스미스 양식 알고리즘의 적용으로 발생하는 중간 행렬은 희박한 행렬로 시작하고 끝나도 채워진다.

  • LinBox 라이브러리에서 찾을 수 있는 효율적이고 확률적인 Smith 정규 양식 알고리즘.
  • Perseus 소프트웨어 패키지와 같이 동종학 계산 전 처리를 위한 단순한 감소.
  • TDAstats R 패키지와 같이 필터링된 복합체의 지속적인 호몰로지를 계산하기 위한 알고리즘.[14]

참고 항목

참조

  1. ^ Afra J. Zomorodian, Topology for Computing, 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
  3. ^ B.~버튼. 3-매니폴드 토폴로지 소프트웨어인 실험수학 13(2004), 267–272를 소개한다.
  4. ^ Schleimer, Saul (2011). "Sphere Recognition Lies in NP" (PDF) – via University of Warwick.
  5. ^ 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.
  6. ^ 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.
  7. ^ 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). arXiv:0909.4625. doi:10.1090/S0002-9947-2011-05419-X.
  8. ^ J.Manning, 알고리즘 탐지 및 해결 가능한 단어 문제가 있는 3-manifold의 쌍곡선 구조 설명, 지오메트리 및 토폴로지 6(2002) 1-26
  9. ^ S.Matveev, 알고리즘 위상 및 3-매니폴드 분류, Springer-Verlag 2003
  10. ^ 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.
  11. ^ 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.
  12. ^ "Main_Page", The Knot Atlas.
  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 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. PMID 33381678.

외부 링크

책들