計算論的トポロジー

計算論的トポロジー^[1]（けいさんろんてきトポロジー、英: algorithmic topology、英: computational topology、計算トポロジー^[2]等とも）は、（数学の幾何学における）トポロジーに関連する問題について、アルゴリズムや計算量等の計算機科学的側面を研究する分野で、純粋数学から計算幾何学やグラフィックス、ロボット工学、構造生物学や化学等、幅広い分野から生じる問題を対象とする^[3]。

分野毎の結果

3次元多様体論

3次元多様体に関する多くのアルゴリズムは正則曲面（normal surface）の理論を中心としたものである。

互いに同相でない3次元多様体を全て列挙する問題は、2020年7月現在未だ解決されていないが、3次元多様体の完全な分類はアルゴリズム的に可能であることが知られている^[4]。

三角形分割された3次元多様体が3次元球面に同相か否かを判定するアルゴリズムはRegina（ソフトウェア）（英語版）に実装されている^[5]。その実行は四面体単体の数において指数関数時間的で、メモリ使用も指数的である。この問題はNPに含まれ^[6]、更に一般化されたリーマン予想を仮定すればco-NPに含まれることも証明されている^[7]。

3次元多様体の連結成分毎の分解のアルゴリズムはRegina（ソフトウェア）（英語版）に実装されている。アルゴリズムは3次元球面判定アルゴリズムに類似したもので、実行は指数関数時間である。

ザイフェイルト-ウェーバー多様体における不可縮曲面（incompressible surface）の存在を判定するアルゴリズムが知られている^[8]。

基本群が語の問題に対する解を有するような3次元多様体について双曲構造を検出するアルゴリズムが知られている^[9]。

三角形分割された3次元多様体上の近似的双曲構造の計算アルゴリズムはSnapPeaに実装されている。

転換アルゴリズム

結び目のダイアグラム表示からcusped triangulationを生成するアルゴリズムが知られており、SnapPeaに実装されている。アルゴリズムは絡み目の補空間の基本群の表示を作るWirtingerのアルゴリズムと似たものである。このアルゴリズムはダイアグラムの交点数に対して凡そ線形の計算時間である。

3次元多様体の手術表示から、当該多様体の三角形分割表示に変換するアルゴリズムがSnapPeaに実装されている。

三角形分割された3次元多様体から三角形分割された4次元多様体を構成する手順が知られている^[10]。

曲面の写像類群の元をデーンツイストを生成元とする語の形で与えたときに、三角形分割された3次元多様体を生成するアルゴリズムが知られている（S. Schleimerによる）^[要出典]。生成される3次元多様体は、当該元をヘーガード分解の貼り合わせ写像と看做したときに作られるものである。

結び目理論

結び目が自明か否かを判定する問題はNPに属する^[11]。

結び目の種数を決定する問題はPSPACEに属する^[要出典]。

結び目のアレキサンダー多項式を計算する多項式時間のアルゴリズムが存在する^[12]。

ホモトピー論

球面のホモトピー群やホモトピー接続（英語版）（homotopy continuation）の数値的方法等が研究されている^[要出典]。

有限なPostnikov複体のホモトピー群を計算するアルゴリズムが知られている^[13]。

ホモロジー論

CW複体のホモロジー群の計算は、アルゴリズム的には境界行列（boundary matrices）のスミス標準形（Smith normal form）への変形問題に帰着するが、複体が巨大な場合に効率的に計算するには種々の障碍がある^[要出典]。

位相的データ解析に関連して活溌に研究されている^[14]^[15]。

効率的な確率論的スミス標準形（Smith normal form）変形アルゴリズムが LinBoxライブラリに実装されている。

永続的ホモロジー（persistent homology）を計算するためのアルゴリズムが^[16]^[17]等に実装されている。

脚注

^ “科学研究費助成事業データベース”. 2020年7月24日閲覧。
^ 荒井迅「計算トポロジーとその応用について」第23巻第1号、2013年、doi:10.11540/bjsiam.23.1_39、NAID 110009597003、2020年8月5日閲覧。
^ Afra J. Zomorodian (2005). Topology for Computing. p. xi
^ S.Matveev, Algorithmic topology and the classification of 3-manifolds, Springer-Verlag 2003
^ B.Burton. Introducing Regina, the 3-manifold topology software, Experimental Mathematics 13 (2004), 267-272.
^ http://www.warwick.ac.uk/~masgar/Maths/np.pdf
^ 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.
^ Burton, Benjamin A.; Hyam Rubinstein, J.; Tillmann, Stephan (2009). The Weber-Seifert dodecahedral space is non-Haken. arXiv:0909.4625.
^ J.Manning, Algorithmic detection and description of hyperbolic structures on 3-manifolds with solvable word problem, Geometry and Topology 6 (2002) 1-26
^ 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.
^ 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 .
^ "Main_Page", The Knot Atlas.
^ E H Brown's "Finite Computability of Postnikov Complexes" Annals of Mathematics (2) 65 (1957) pp 1-20
^ 大林一平「位相的データ解析の現在 (統計的モデリングと予測理論のための統合的数理研究)」『数理解析研究所講究録』第2057巻、京都大学数理解析研究所、2017年10月、34-50頁、CRID 1050845763140627968、hdl:2433/237190、ISSN 1880-2818。
^ “位相的データ解析の基礎と応用” (PDF). 2020年7月24日閲覧。
^ Perseus、TDAstats（R言語のパッケージ）
^ 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.

参考文献

Tomasz Kaczynski; Konstantin Mischaikow; Marian Mrozek (2004). Computational Homology. Springer. ISBN 0-387-40853-3
Afra J. Zomorodian (2005). Topology for Computing. Cambridge. ISBN 0-521-83666-2
Computational Topology: An Introduction, Herbert Edelsbrunner, John L. Harer, AMS Bookstore, 2010, ISBN 978-0-8218-4925-5

外部リンク

[1] “科学研究費助成事業データベース”. 2020年7月24日閲覧。

[2] 荒井迅「計算トポロジーとその応用について」第23巻第1号、2013年、doi:10.11540/bjsiam.23.1_39、NAID 110009597003、2020年8月5日閲覧。

[3] Afra J. Zomorodian (2005). Topology for Computing. p. xi

[4] S.Matveev, Algorithmic topology and the classification of 3-manifolds, Springer-Verlag 2003

[5] B.Burton. Introducing Regina, the 3-manifold topology software, Experimental Mathematics 13 (2004), 267-272.

[6] ttp://www.warwick.ac.uk/~masgar/Maths/np.pdf

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

[8] Burton, Benjamin A.; Hyam Rubinstein, J.; Tillmann, Stephan (2009). The Weber-Seifert dodecahedral space is non-Haken. arXiv:0909.4625.

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

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

[12] "Main_Page", The Knot Atlas.

[13] E H Brown's "Finite Computability of Postnikov Complexes" Annals of Mathematics (2) 65 (1957) pp 1-20

[14] 大林一平「位相的データ解析の現在 (統計的モデリングと予測理論のための統合的数理研究)」『数理解析研究所講究録』第2057巻、京都大学数理解析研究所、2017年10月、34-50頁、CRID 1050845763140627968、hdl:2433/237190、ISSN 1880-2818。

[15] “位相的データ解析の基礎と応用” (PDF). 2020年7月24日閲覧。

[16] Perseus、TDAstats（R言語のパッケージ）

[17] 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.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]