計算トポロジー

計算トポロジーという分野がある。 計算機の進歩により, 単体的複体や chain complex のホモロジーが計算機にかかるようになったため, ホモロジーなどのトポロジーの道具が, 画像認識などの分野に応用されるようになり, 急速に発展している。

1999年に開かれた研究集会の報告 [Ber+] によると, 80年代以来 computational geometry で扱われていた多角形や多面体などの discrete object を continuous object に拡張するために誕生した分野らしい。それによると, 既に 1997年に Vegter の [Veg97] が出ている。

2004年には, Minnesota 大学で conference が開かれている。 今ではなくなってしまったが, そのホームページに書いてあった参考文献には, [Ber+00] と [Ede01] が挙げてあった。2006年には, MSRI での研究プログラムがあった。 最初に見たとき, G. Carlsson や Jardine が organizer に名を連ねていたのに驚いたが, 21世紀が始まったときから (あるいはそれ以前から) Carlsson らは, 応用トポロジーに取り組んでいたということである。 その先見性は, 見習うべきだと思う。

• 応用トポロジー

計算トポロジーがどういうものかについては, Kaczynski と Mischaikow と Mrozek の本 [KMM04] を見るとよいだろう。Edelsbrunner と Harer の本 [EH10] も出た。Edelsbrunner は, ここで計算トポロジーの講義ノートを公開しているので, まずはそれを見てみるのもよいと思う。

実際に代数的トポロジーの不変量を計算するためには, 効率の良い algorithm が必要である。そのような研究を effective algebraic topology というようである。

• effective algebraic topology

多面体やグラフなどの, 組み合せ論的データからは, 様々な方法で poset が得られ, poset からは, nerve を取ることで (有限な) 単体的複体が得られる。 このように, 組み合せ論の問題を単体的複体のトポロジーの問題に帰着させるのは有効な方法のようである。 よって計算トポロジーは組み合せ論の問題にも応用できる。

多様体の minimal triangulation を計算機で見つけるという問題もある。Björner と Lutz の [BL00] を見るとよい。Spreer と Kühnel の [SK] によると, 特異点を持つ多様体も考えられるようになったようである。

多様体に関係する問題としては, 与えられた (有限) 単体的複体 が多様体と同相になるか, というものがある。より具体的に, 単体的複体が球面と同相になるか, という問題も古くから考えられてきている。

• manifold recognition
• sphere recognition

後者の問題については, Joswig らの [Jos+22] の Introduction を見るとよい。それによると, 5次元以上の場合は sphere recognition の問題は undecidable らしい。彼等は [VKF74] の Novikov による appendix と Chernavsky と Leksine の [CL06] を挙げている。 3次元の場合は NP [Sch11] かつ co-NP [Lac21] であることが示されている。4次元の場合の計算複雑性は, open らしい。

ホモロジーで誘導された写像を計算する試みとして, [MMP05; Har+14; Har+16] などがある。

冒頭にも書いたように, computational geometry は computational topology の起源となった, もう少し古い分野である。[CGP99] という conference の proceedings がある。ここには Ziegler の polytope に関する survey など, 興味深い論文が色々ある。

対象として semi-algebraic set を考え, そのBetti数や連結成分などを計算する algorithm を考えているのは, Basu と Pollack と Roy の [BPR05] である。

統計学的に, あるいは確率論的に, トポロジカルなデータを得ようという試みもある。 ある図形からランダムに点をいくつか選び, そこから得られるデータから元の図形の性質を調べようというわけである。 そのアイデアに基づいた persistent homology というものがある。

• persistent homology

具体的な応用としては, 電磁気での設計については古くから考えられているようである。 Suuriniemi の thesis [Suu04] や Dłotko と Specogna の [DS] を見てみるとよい。後者には, 1966年の文献も挙げられている。

References

[Ber+]

Marshall Bern et al. Emerging Challenges in Computational Topology. arXiv: cs/9909001.

[Ber+00]

Mark de Berg, Marc van Kreveld, Mark Overmars, and Otfried Schwarzkopf. Computational geometry. revised. Algorithms and applications. Berlin: Springer-Verlag, 2000, pp. xii+367. isbn: 3-540-65620-0.

[BL00]

Anders Björner and Frank H. Lutz. “Simplicial manifolds, bistellar flips and a 16-vertex triangulation of the Poincaré homology 3-sphere”. In: Experiment. Math. 9.2 (2000), pp. 275–289. url: http://projecteuclid.org/euclid.em/1045952351.

[BPR05]

Saugata Basu, Richard Pollack, and Marie-Francoise Roy. “Computing the first Betti number and the connected components of semi-algebraic sets”. In: STOC’05: Proceedings of the 37th Annual ACM Symposium on Theory of Computing. New York: ACM, 2005, pp. 304–312. arXiv: math/ 0603248. url: http://dx.doi.org/10.1145/1060590.1060636.

[CGP99]

Bernard Chazelle, Jacob E. Goodman, and Richard Pollack, eds. Advances in discrete and computational geometry. Vol. 223. Contemporary Mathematics. American Mathematical Society, Providence, RI, 1999, pp. xii+463. isbn: 0-8218-0674-2. url: http://dx.doi.org/10.1090/conm/223.

[CL06]

A. V. Chernavsky and V. P. Leksine. “Unrecognizability of manifolds”. In: Ann. Pure Appl. Logic 141.3 (2006), pp. 325–335. url: https://doi.org/10.1016/j.apal.2005.12.011.

[DS]

Paweł Dłotko and Ruben Specogna. Cohomology in electromagnetic modeling. arXiv: 1111.2374.

[Ede01]

Herbert Edelsbrunner. Geometry and topology for mesh generation. Vol. 7. Cambridge Monographs on Applied and Computational Mathematics. Cambridge: Cambridge University Press, 2001, p. xii 177. isbn: 0-521-79309-2.

[EH10]

Herbert Edelsbrunner and John L. Harer. Computational topology. An introduction. Providence, RI: American Mathematical Society, 2010, pp. xii+241. isbn: 978-0-8218-4925-5.

[Har+14]

Shaun Harker, Konstantin Mischaikow, Marian Mrozek, and Vidit Nanda. “Discrete Morse theoretic algorithms for computing homology of complexes and maps”. In: Found. Comput. Math. 14.1 (2014), pp. 151–184. url: https://doi.org/10.1007/s10208-013-9145-0.

[Har+16]

Shaun Harker, Hiroshi Kokubu, Konstantin Mischaikow, and Paweł Pilarczyk. “Inducing a map on homology from a correspondence”. In: Proc. Amer. Math. Soc. 144.4 (2016), pp. 1787–1801. arXiv: 1411.7563. url: https://doi.org/10.1090/proc/12812.

[Jos+22]

Michael Joswig, Davide Lofano, Frank H. Lutz, and Mimi Tsuruga. “Frontiers of sphere recognition in practice”. In: J. Appl. Comput. Topol. 6.4 (2022), pp. 503–527. arXiv: 1405.3848. url: https://doi.org/10.1007/s41468-022-00092-8.

[KMM04]

Tomasz Kaczynski, Konstantin Mischaikow, and Marian Mrozek. Computational homology. Vol. 157. Applied Mathematical Sciences. Springer-Verlag, New York, 2004, pp. xviii+480. isbn: 0-387-40853-3. url: http://dx.doi.org/10.1007/b97315.

[Lac21]

Marc Lackenby. “The efficient certification of knottedness and Thurston norm”. In: Adv. Math. 387 (2021), Paper No. 107796, 142. arXiv: 1604.00290. url: https://doi.org/10.1016/j.aim.2021.107796.

[MMP05]

Konstantin Mischaikow, Marian Mrozek, and Pawel Pilarczyk. “Graph approach to the computation of the homology of continuous maps”. In: Found. Comput. Math. 5.2 (2005), pp. 199–229. url: https://doi.org/10.1007/s10208-004-0125-2.

[Sch11]

Saul Schleimer. “Sphere recognition lies in NP”. In: Low-dimensional and symplectic topology. Vol. 82. Proc. Sympos. Pure Math. Amer. Math. Soc., Providence, RI, 2011, pp. 183–213. url: https://doi.org/10.1090/pspum/082/2768660.

[SK]

Jonathan Spreer and Wolfgang Kühnel. Combinatorial properties of the K3 surface: Simplicial blowups and slicings. arXiv: 0909.1453.

[Suu04]

Saku Suuriniemi. “Homological Computations in Electromagnetic Modeling”. PhD thesis. Tampere University of Technology, 2004. url: http://dspace.cc.tut.fi/dpub/handle/123456789/23.

[Veg97]

Gert Vegter. “Computational topology”. In: Handbook of discrete and computational geometry. CRC Press Ser. Discrete Math. Appl. CRC, Boca Raton, FL, 1997, pp. 517–536.

[VKF74]

I. A. Volodin, V. E. Kuznecov, and A. T. Fomenko. “The problem of the algorithmic discrimination of the standard three-dimensional sphere”. In: Uspehi Mat. Nauk 29.5(179) (1974). Appendix by S. P. Novikov, pp. 71–168.