Abstract
In this paper we present a new algorithm for computing the homology of regular CW-complexes. This algorithm is based on the coreduction algorithm due to Mrozek and Batko and consists essentially of a geometric preprocessing algorithm for the standard chain complex generated by a CW-complex. By employing the concept of S-complexes the original chain complex can—in all known practical cases—be reduced to a significantly smaller S-complex with isomorphic homology, which can then be computed using standard methods. Furthermore, we demonstrate that in the context of non-uniform cubical grids this method significantly improves currently available algorithms based on uniform cubical grids.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Adler, R.J., Taylor, J.E.: Random Fields and Geometry. Springer, New York (2007)
Blömker, D., Maier-Paape, S., Wanner, T.: Phase separation in stochastic Cahn-Hilliard models. In: Miranville, A. (ed.) Mathematical Methods and Models in Phase Transitions, pp. 1–41. Nova Science, New York (2005)
Bredon, G.E.: Topology and Geometry. Graduate Texts in Mathematics, vol. 139. Springer, New York (1997)
Day, S., Kalies, W.D., Mischaikow, K., Wanner, T.: Probabilistic and numerical validation of homology computations for nodal domains. Electron. Res. Announc. Am. Math. Soc. 13, 60–73 (2007)
Day, S., Kalies, W.D., Wanner, T.: Verified homology computations for nodal domains. SIAM J. Multiscale Model. Simul. 7(4), 1695–1726 (2009)
Delfinado, C.J.A., Edelsbrunner, H.: An incremental algorithm for Betti numbers of simplicial complexes. In: SCG ’93: Proceedings of the Ninth Annual Symposium on Computational Geometry, pp. 232–239. ACM, New York (1993)
Dumas, J.-G., Heckenbach, F., Saunders, D., Welker, V.: Computing simplicial homology based on efficient Smith normal form algorithms. In: Algebra, Geometry, and Software Systems, pp. 177–206. Springer, Berlin (2003)
Edelsbrunner, H., Letscher, D., Zomorodian, A.: Topological persistence and simplification. Discrete Comput. Geom. 28(4), 511–533 (2002)
Friedman, J.: Computing Betti numbers via combinatorial Laplacians. Algorithmica 21(4), 331–346 (1998)
Gameiro, M., Mischaikow, K., Wanner, T.: Evolution of pattern complexity in the Cahn-Hilliard theory of phase separation. Acta Mater. 53(3), 693–704 (2005)
Juda, M., Mrozek, M.: ℤ2-homology of weak 2-pseudomanifolds may be computed in O(n α(n)) time. Preprint, Jagiellonian University, Computer Science Department (2010). Available online at http://www.ii.uj.edu.pl/~mrozek/papers/homology-of-2-manifolds-15.pdf
Kaczynski, T., Mischaikow, K., Mrozek, M.: Computing homology. Homology Homotopy Appl. 5(2), 233–256 (2003)
Kaczynski, T., Mischaikow, K., Mrozek, M.: Computational Homology. Applied Mathematical Sciences, vol. 157. Springer, New York (2004)
Kaczynski, T., Mrozek, M., Ślusarek, M.: Homology computation by reduction of chain complexes. Comput. Math. Appl. 35(4), 59–70 (1998)
Massey, W.S.: A Basic Course in Algebraic Topology. Graduate Texts in Mathematics, vol. 127. Springer, New York (1991)
Mischaikow, K., Wanner, T.: Probabilistic validation of homology computations for nodal domains. Ann. Appl. Probab. 17(3), 980–1018 (2007)
Mischaikow, K., Wanner, T.: Topology-guided sampling of nonhomogeneous random processes. Ann. Appl. Probab. 20(3), 1068–1097 (2010)
Mrozek, M.: Cech type approach to computing homology of maps. Discrete Comput. Geom. 44(3), 546–576 (2010)
Mrozek, M., Batko, B.: Coreduction homology algorithm. Discrete Comput. Geom. 41(1), 96–118 (2009)
Mrozek, M., Pilarczyk, P., Żelazna, N.: Homology algorithm based on acyclic subspace. Comput. Math. Appl. 55(11), 2395–2412 (2008)
Mrozek, M., Wanner, T.: Coreduction homology algorithm for inclusions and persistent homology. Comput. Math. Appl. (in press)
Munkres, J.R.: Elements of Algebraic Topology. Addison-Wesley, Menlo Park (1984)
Peltier, S., Ion, A., Kropatsch, W., Damiand, G., Haxhimusa, Y.: Directly computing the generators of image homology using graph pyramids. Image Vis. Comput. 27(7), 846–853 (2009)
Storjohann, A.: Near optimal algorithms for computing smith normal forms of integer matrices. In: Proceedings of the 1996 International Symposium on Symbolic and Algebraic Computation, ISSAC ’96, pp. 267–274. ACM, New York (1996)
Wanner, T., Fuller Jr., E.R., Saylor, D.M.: Homological characterization of microstructure response fields in polycrystals. Acta Mater. 58(1), 102–110 (2010)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
Open Access This is an open access article distributed under the terms of the Creative Commons Attribution Noncommercial License (https://creativecommons.org/licenses/by-nc/2.0), which permits any noncommercial use, distribution, and reproduction in any medium, provided the original author(s) and source are credited.
About this article
Cite this article
Dłotko, P., Kaczynski, T., Mrozek, M. et al. Coreduction Homology Algorithm for Regular CW-Complexes. Discrete Comput Geom 46, 361–388 (2011). https://doi.org/10.1007/s00454-010-9303-y
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00454-010-9303-y