Abstract
This paper presents a new reduction algorithm for the efficient computation of the homology of cubical sets and polotypes. The algorithm—particularly strong for low-dimensional sets embedded in high dimensions—runs in linear time. The paper presents the theoretical background of the algorithm, the algorithm itself, experimental results based on an implementation for cubical sets as well as some theoretical complexity estimates.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Basu, S.: On bounding the Betti numbers and computing the Euler characteristic of semi-algebraic sets. Discrete Comput. Geom. 22, 1–18 (1999)
Bing, R.H.: Some aspects of the topology of 3-manifolds related to the Poincaré Conjecture. In: Saaty, T.L. (ed.) Lectures on Modern Mathematics, vol. II, pp. 93–128. Wiley, New York (1964)
Delfinado, C.J.A., Edelsbrunner, H.: An incremental algorithm for Betti numbers of simplicial complexes on the 3-sphere. Comput. Aided Geom. Des. 12, 771–784 (1995)
Donald, B.R., Chang, D.R.: On the complexity of computing the homology type of a triangulation. In: Proc. 32nd Ann. IEEE Sympos. Found. Comput. Sci., pp. 650–661 (1991)
Duff, I., Erisman, A., Reid, J.: Direct Methods for Sparse Matrices. Oxford University Press, London (1986)
Dumas, J.-G., Saunders, B.D., Villard, G.: On efficient sparse integer matrix Smith normal form computations. J. Symb. Comput. 32, 71–99 (2001)
Dumas, J.-G., Heckenbach, F., Saunders, D., Velker, V.: Computing simplicial homology based on efficient smith normal form algorithms. In: Algebra, Geometry and Software Systems, pp. 177–207. Springer, Berlin (2003)
Edelsbrunner, H., Letscher, D., Zomorodian, A.: Topological persistence and simplification. Discrete Comput. Geom. 28, 511–533 (2002)
Friedman, J.: Computing Betti numbers via combinatorial Laplacians. In: Proc. 28th Ann. ACM Sympos. Theory Comput., pp. 386–391 (1996)
Gameiro, M., Mischaikow, K., Wanner, Th.: Evolution of pattern complexity in the Cahn–Hilliard theory of phase separation. Acta Mater. 53, 693–704 (2005)
Kaczynski, T., Mrozek, M., Ślusarek, M.: Homology computation by reduction of chain complexes. Comput. Math. Appl. 35, 59–70 (1998)
Kaczynski, T., Mischaikow, K., Mrozek, M.: Computational Homology. Applied Mathematical Sciences, vol. 157. Springer, New York (2004)
Kalies, W.: Chom—A Cubical Homology Program (1999). http://www.math.fau.edu/kalies/chom.html
Kalies, W., Mischaikow, K., Watson, G.: Cubical approximation and computation of homology. In: Conley Index Theory, vol. 47, pp. 115–131. Banach Center Publications, Warsaw (1999)
Kirkpatrick, S., Selman, B.: Critical behaviour in the satisfiability of random Boolean expressions. Science 264, 1297 (1994)
Massey, W.S.: Homology and Cohomology Theory. Dekker, New York (1978)
Mischaikow, K., Mrozek, M., Pilarczyk, P.: Graph approach to the computation of the homology of continuous maps. Found. Comput. Math. 5, 199–229 (2005)
Mrozek, M.: Homology Software (2006). http://www.ii.uj.edu.pl/~mrozek/software/homology.html
Mrozek, M.: Index pairs algorithms. Found. Comput. Math. 6, 457–493 (2006)
Mrozek, M., Pilarczyk, P., Zelazna, N.: Homology algorithm based on acyclic subspace. Comput. Math. Appl. (2008, accepted)
Mrozek, M., Batko, B.: Homology of representable sets (2008, submitted)
Munkres, J.R.: Elements of Algebraic Topology. Addison-Wesley, Reading (1984)
Steenrod, N.E.: Regular cycles of compact metric spaces. Ann. Math. 41, 833–851 (1940)
Storjohann, A.: Near optimal algorithms for computing Smith normal form of integer matrices. In: Proceedings of the 1996 International Symposium on Symbolic and Algebraic Computation, ISAAC 1996, pp. 267–274 (1996)
Urbańska, A.: Smith normal form algorithms for sparse matrices with applications to homology computations. M. Sc. Thesis, Jagiellonian University, Kraków (2007) (in Polish, with English Abstract)
Yannakakis, M.: Computing the minimum fill-in is NP-complete. SIAM J. Matrix Anal. Appl. 2, 77–79 (1981)
Zomorodian, A., Carlsson, G.: Computing persistent homology. Discrete Comput. Geom. 33, 249–274 (2005)
Computational Homology Project: http://chomp.rutgers.edu
Computer Assisted Proofs in Dynamics: http://capd.wsb-nlu.edu.pl
Project LinBox: Exact computational linear algebra: http://www.linalg.org
Author information
Authors and Affiliations
Corresponding author
Additional information
Both authors are partially supported by Polish MNSzW, Grant N201 037 31/3151.
Rights and permissions
About this article
Cite this article
Mrozek, M., Batko, B. Coreduction Homology Algorithm. Discrete Comput Geom 41, 96–118 (2009). https://doi.org/10.1007/s00454-008-9073-y
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00454-008-9073-y