The purpose of this article is to introduce a method for computing the homology groups of cellular complexes composed of cubes. We will pay attention to issues of storage and efficiency in performing computations on large complexes which will be required in applications to the computation of the Conley index. The algorithm used in the homology computations is based on a local reduction procedure, and we give a subquadratic estimate of its computational complexity. This estimate is rigorous in two dimensions, and we conjecture its validity in higher dimensions.
@article{bwmeta1.element.bwnjournal-article-bcpv47i1p115bwm,
author = {Kalies, William and Mischaikow, Konstantin and Watson, Greg},
title = {Cubical approximation and computation of homology},
journal = {Banach Center Publications},
volume = {50},
year = {1999},
pages = {115-131},
zbl = {0938.55012},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-bcpv47i1p115bwm}
}
Kalies, William; Mischaikow, Konstantin; Watson, Greg. Cubical approximation and computation of homology. Banach Center Publications, Tome 50 (1999) pp. 115-131. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-bcpv47i1p115bwm/
[000] [1] T. J. Chou and G. E. Collins, Algorithms for the solution of systems of linear Diophantine equations, SIAM J. Comput., 11:687-708, 1982. | Zbl 0498.65022
[001] [2] T. H. Cormen, C. E. Leiserson, and R. L. Rivest, Introduction to Algorithms, McGraw-Hill, 1992. | Zbl 1187.68679
[002] [3] C. J. A. Delfinado and H. Edelsbrunner, An incremental algorithm for Betti numbers of simplicial complexes, in: Proc. 9th Ann, Symp. Comput. Geom., pages 232-239, 1993.
[003] [4] C. J. A. Delfinado and H. Edelsbrunner, An incremental algorithm for Betti numbers of simplicial complexes on the 3-sphere, Comp. Aided Geom. Design, 12:771-784, 1995. | Zbl 0873.55007
[004] [5] M. Dellnitz and A. Hohmann, The computation of unstable manifolds using subdivision and continuation, in: H. W. Broer, S. A. van Gils, I. Hoveijn, and F. Takens, editors, Nonlinear Dynamical Systems and Chaos, PNLDE 19, pages 449-459. Birkhäuser, 1996. | Zbl 0842.58064
[005] [6] M. Dellnitz and A. Hohmann, A subdivision algorithm for the computation of unstable manifolds and global attractors, Numer. Math., 75:293-317, 1997.
[006] [7] M. Dellnitz, A. Hohmann, O. Junge, and M. Rumpf, Exploring invariant sets and invariant measures, to appear in Chaos. An Interdisciplinary Journal of Nonlinear Science, 1997. | Zbl 0938.37056
[007] [8] T. K. Dey, H. Edelsbrunner, and S. Guha, Computational topology, preprint, 1997. | Zbl 0916.68202
[008] [9] H. Edelsbrunner, Algorithms in Combinatorial Geometry, Springer-Verlag, 1987. | Zbl 0634.52001
[009] [10] M. Eidenschink, Exploring Global Dynamics: A Numerical Algorithm Based on the Conley Index Theory, PhD thesis, Georgia Institute of Technology, 1995.
[010] [11] X. G. Fang and G. Havas, On the worst-case complexity of integer gaussian elimination, in: Proceedings of the 1997 International Symposium on Symbolic and Algebraic Computation ISSAC 97, pages 28-31. ACM Press, 1997. | Zbl 0916.65038
[011] [12] J. Friedman, Computing Betti numbers via combinatorial Laplacians, preprint, 1995.
[012] [13] R. Guder, M. Dellnitz, and E. Kreuzer, An adaptive method for the approximation of the generalized cell mapping, Chaos, Solitons and Fractals, 8(4):525-534, 1997. | Zbl 0935.37055
[013] [14] C. S. Iliopoulos, Worst-case complexity bounds on algorithms for computing the canonical structure of finite abelian groups and the Hermite and Smith normal forms of an integer matrix, SIAM J. Comput., 18:658-669, 1989. | Zbl 0689.68059
[014] [15] T. Kaczynski, H. Karloff, K. Mischaikow, and M. Mrozek, Introduction to algebraic topology: A computational perspective, book in progress.
[015] [16] T. Kaczynski, M. Mrozek, and M. Ślusarek, Homology computation by reduction of chain complexes, to appear in Computers & Mathematics with Appl. | Zbl 0904.55004
[016] [17] R. Kannan and A. Bachem, Polynomial algorithms for computing the Smith and Hermite normal forms of an integer matrix, SIAM J. Comput., 8:499-507, 1979. | Zbl 0446.65015
[017] [18] J. R. Munkres, Elements of Algebraic Topology, Addison-Wesley, 1984.
[018] [19] F. P. Preparata and M. I. Shamos, Computational Geometry: An Introduction, Springer-Verlag, 1985. | Zbl 0575.68059
[019] [20] H. J. S. Smith, On systems of indeterminate equations and congruences, Philos. Trans. Roy. Soc. London, 151:293-326, 1861.
[020] [21] A. Storjohann, Near optimal algorithms for computing smith normal forms of integral matrices, in: Proceedings of the 1996 International Symposium on Symbolic and Algebraic Computation ISSAC 96, pages 267-274. ACM Press, 1996. | Zbl 0914.65043