×

Computational homotopy of finite regular CW-spaces. (English) Zbl 1311.55008

This paper describes an approach to the computational homotopy of CW-spaces. Computational advantages are obtained by considering spaces that a tessellated in the sense that the space is the union of the closure of its \(n\)-cells and all closures of the \(n\)-cell have face posets isomorphic to that of some fixed polytope. The case where this is a permutahedral one is particularly useful. The authors describe a “zig-zag” homotopy retraction approach to reducing the number of cells of low-dimensional lattice spaces. It is important that this approach is algorithmic. Applications to feature recognition in low-dimensional images is given as an illustration of the technique. The ideas have been implemented in the HAP (homological algebra package http://www.gap-system.org/Pacjkages/hap.html) for the GAP computational system. Sessions with the package are given in the paper.

MSC:

55N99 Homology and cohomology theories in algebraic topology
55-04 Software, source code, etc. for problems pertaining to algebraic topology
Full Text: DOI

References:

[1] Carlsson, G.: Topology and data. Bull. Am. Math. Soc. 46, 255-308 (2009) · Zbl 1172.62002 · doi:10.1090/S0273-0979-09-01249-X
[2] Carlsson, G., Zomorodian, A., Collins, A., Guibas, L.: Persistence barcodes for shapes. Int. J. Shape Model. 11, 149-187 (2005) · Zbl 1092.68688 · doi:10.1142/S0218654305000761
[3] Cohen, M.: A Course in Simple Homotopy Theory. Graduate Texts in Mathematics, vol. 10, Springer, Berlin (1973) · Zbl 0261.57009
[4] de Silva, V., Ghrist, R.: Homological sensor networks. Notices Am. Math. Soc. 54(1), 10-17 (2007) · Zbl 1142.94006
[5] Dorozinski, T.E.: Image of Permutahedral Tessellation. http://en.wikipedia.org/wiki/File:HC-A4.png
[6] Edelsbrunner, H., Harer, J.: Persistent homology—a survey. In: Goodman, J.E., Pach, J., Pollack, R. (eds.) Twenty Years After. AMS, Providence (2007) · Zbl 1145.55007
[7] Edelsbrunner, H., Harer, J.L.: Computational Topology. An Introduction. American Mathematical Society, Providence (2010) · Zbl 1193.55001
[8] Ellis, G.: hap-Homological Algebra programming, Version 1.9.4 (2011), a package for the gap computational algebra system. http://www.gap-system.org/Packages/hap.html
[9] Ellis, G.: Homological algebra programming. Contemp. Math. 470, 63-74 (2008) · Zbl 1155.20051 · doi:10.1090/conm/470/09186
[10] Felsch, V.: crystcat-Crystallographic Groups Catologue, a package for the textsc gap computer algebra system. http://www.math.uni-bielefeld.de/ gaehler/gap/CrystCat/
[11] Forman, R.: A user’s guide to discrete Morse theory. In Séminaire Lotharingien de Combinatoire, vol. 48 (2001) · Zbl 1048.57015
[12] Ghrist, R.: Elementary Applied Topology. http://hans.math.upenn.edu/ ghrist/notes.html · Zbl 1239.57042
[13] graphviz-Graph Visualization Software. http://www.graphviz.org/
[14] Harker, S., Mischaikow, K., Mrozek, M., Nanda, V., Wagner, H., Juda, M., Dlotko, P.: The efficiency of a homology algorithm based on discrete morse theory and coreductions. In: Proceedings of the 3rd International Workshop on Computational Topology in Image Context, Chipiona, Spain, November 2010 (Rocio Gonzalez Diaz Pedro Real Jurado (eds.)), Image A, vol. 1, pp. 41-47 (2010)
[15] Harker, S., Mischaikow, K., Mrozek, M., Nanda, V.: Discrete Morse theoretic algorithms for computing homology of complexes and maps. Found. Comput. Math. (2013), doi:10.1007/s10208-013-9145-0 · Zbl 1387.55010
[16] Hegarty, F.: happermutahedral-Version 1.0 (2011), a package for the gap computational algebra system. http://hamilton.nuigalway.ie
[17] Jones, D.W..: A general theory of polyhedral sets and the corresponding \[T\]-complexes. Diss. Math. (Rozprawy Mat.) 266, p. 110 (1988) · Zbl 1002.57504
[18] Kaczyski, T., Mischaikow, K.M., Mrozekk, M.: Computational Homology, Springer, Berlin, p. 480 (2004) · Zbl 1039.55001
[19] Massey, W.S.: A Basic Course in Algebraic Topology. Graduate Texts in Mathematics, vol. 127. Springer, Berlin (1991) · Zbl 0725.55001
[20] Mrozek, M., et al.: Computer Assisted Proofs in Dynamics. http://capd.ii.uj.edu.pl/ · Zbl 0848.68102
[21] Mrozek, M., et al.: Reduction Homology Algorithms. http://redhom.ii.uj.edu.pl/ · Zbl 1402.57021
[22] plex, software package for persistent homology of simplicial complexes. http://comptop.stanford.edu/u/programs/jplex/
[23] Sergereart, F., et al.: KENZO System for Computational Algebraic Topology. http://www-fourier-ujf-grenoble.fr/ sergerar/Kenzo
[24] The gap Group, gap-Groups, Algorithms, and Programming, Version 4.4.9 (2006). http://www.gap-system.org
[25] Zomorodian, A., Carlsson, G.: Computing persistent homology. Discrete. Comput. Geom. 33, 249-274 (2005) · Zbl 1069.55003 · doi:10.1007/s00454-004-1146-y
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.