×

Computing homology: A global reduction approach. (English) Zbl 1261.55009

Brlek, Srečko (ed.) et al., Discrete geometry for computer imagery. 15th IAPR international conference, DGCI 2009, Montréal, Canada, September 30 – October 2, 2009. Proceedings. Berlin: Springer (ISBN 978-3-642-04396-3/pbk). Lecture Notes in Computer Science 5810, 313-324 (2009).
Summary: A new algorithm to compute the homology of a finitely generated chain complex is proposed in this work. It is based on grouping algebraic reductions of the complex into structures that can be encoded as directed acyclic graphs. This leads to sequences of projection maps that reduce the number of generators in the complex while preserving its homology. This organization of reduction pairs allows to update the boundary information in a single step for a whole set of reductions which shows impressive gains in computational performance compared to existing methods. In addition, this method gives the homology generators for a small additional cost.
For the entire collection see [Zbl 1176.68004].

MSC:

55U15 Chain complexes in algebraic topology
05C85 Graph algorithms (graph-theoretic aspects)
52B70 Polyhedral manifolds
68P05 Data structures
68U05 Computer graphics; computational geometry (digital and algorithmic aspects)

Software:

CAPD
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Allili, M., Corriveau, D., Ziou, D.: Morse Homology Descriptor for Shape Characterization. Proceedings of the 17th ICPR 4, 27–30 (2004)
[2] Allili, M., Corriveau, D.: Topological Analysis of Shapes using Morse Theory. Computer Vision and Image Understanding 105, 188–199 (2007) · Zbl 05182804
[3] Collins, A., Zomorodian, A., Carlsson, G., Guibas, L.: A Barcode Shape Descriptor for Curve Point Cloud Data. Computers and Graphics 28, 881–894 (2004)
[4] Munkres, J.R.: Elements of Algebraic Topology. Addison-Wesley, Reading (1984) · Zbl 0673.55001
[5] Kaczynski, T., Mischaikow, K., Mrozek, M.: Computational Homology. Appl. Math. Sci. Series, vol. 157. Springer, New York (2004) · Zbl 1039.55001
[6] Storjohann, A.: Near Optimal Algorithms for Computing Smith Normal Forms of Integer Matrices. In: Proceedings of 1996 International Symposium on Symbolic and Algebraic Computation, ISSAC 1996, pp. 267–274 (1996) · Zbl 0914.65043
[7] Peltier, S., Alayrangues, S., Fuchs, L., Lachaud, J.: Computation of Homology Groups and Generators. Computers and Graphics 30, 62–69 (2006)
[8] Kaczynski, T., Mrozek, M., Slusarek, M.: Homology Computation by Reduction of Chain Complexes. Computers and Mathematics with App. 35, 59–70 (1998) · Zbl 0904.55004
[9] Mrozek, M., Pilarczyk, P., Zelazna, N.: Homology Algorithm Based on Acyclic Subspace. Computers and Mathematics with App. 55(11), 2395–2412 (2008) · Zbl 1142.15300
[10] Mrozek, M., Batko, B.: Coreduction Homology Algorithm. Discrete and Computational Geometry (in press) · Zbl 1163.68041
[11] Allili, M., Corriveau, D., Derivière, S., Kaczynski, T., Trahan, A.: Discrete Dynamical System Framework for Construction of Connections between Critical Regions in Lattice Height Data. J. Math. Imaging Vis. 28(2), 99–111 (2007) · Zbl 1523.68086
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.