# Cubical approximation and computation of homology

William Kalies; Konstantin Mischaikow; Greg Watson

Banach Center Publications (1999)

- Volume: 47, Issue: 1, page 115-131
- ISSN: 0137-6934

## Access Full Article

top## Abstract

top## How to cite

topKalies, William, Mischaikow, Konstantin, and Watson, Greg. "Cubical approximation and computation of homology." Banach Center Publications 47.1 (1999): 115-131. <http://eudml.org/doc/208928>.

@article{Kalies1999,

abstract = {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.},

author = {Kalies, William, Mischaikow, Konstantin, Watson, Greg},

journal = {Banach Center Publications},

keywords = {homology groups of cellular complexes; cubes},

language = {eng},

number = {1},

pages = {115-131},

title = {Cubical approximation and computation of homology},

url = {http://eudml.org/doc/208928},

volume = {47},

year = {1999},

}

TY - JOUR

AU - Kalies, William

AU - Mischaikow, Konstantin

AU - Watson, Greg

TI - Cubical approximation and computation of homology

JO - Banach Center Publications

PY - 1999

VL - 47

IS - 1

SP - 115

EP - 131

AB - 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.

LA - eng

KW - homology groups of cellular complexes; cubes

UR - http://eudml.org/doc/208928

ER -

## References

top- [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. Zbl0498.65022
- [2] T. H. Cormen, C. E. Leiserson, and R. L. Rivest, Introduction to Algorithms, McGraw-Hill, 1992. Zbl1187.68679
- [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.
- [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. Zbl0873.55007
- [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. Zbl0842.58064
- [6] M. Dellnitz and A. Hohmann, A subdivision algorithm for the computation of unstable manifolds and global attractors, Numer. Math., 75:293-317, 1997.
- [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. Zbl0938.37056
- [8] T. K. Dey, H. Edelsbrunner, and S. Guha, Computational topology, preprint, 1997. Zbl0916.68202
- [9] H. Edelsbrunner, Algorithms in Combinatorial Geometry, Springer-Verlag, 1987. Zbl0634.52001
- [10] M. Eidenschink, Exploring Global Dynamics: A Numerical Algorithm Based on the Conley Index Theory, PhD thesis, Georgia Institute of Technology, 1995.
- [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. Zbl0916.65038
- [12] J. Friedman, Computing Betti numbers via combinatorial Laplacians, preprint, 1995.
- [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. Zbl0935.37055
- [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. Zbl0689.68059
- [15] T. Kaczynski, H. Karloff, K. Mischaikow, and M. Mrozek, Introduction to algebraic topology: A computational perspective, book in progress.
- [16] T. Kaczynski, M. Mrozek, and M. Ślusarek, Homology computation by reduction of chain complexes, to appear in Computers & Mathematics with Appl. Zbl0904.55004
- [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. Zbl0446.65015
- [18] J. R. Munkres, Elements of Algebraic Topology, Addison-Wesley, 1984.
- [19] F. P. Preparata and M. I. Shamos, Computational Geometry: An Introduction, Springer-Verlag, 1985. Zbl0575.68059
- [20] H. J. S. Smith, On systems of indeterminate equations and congruences, Philos. Trans. Roy. Soc. London, 151:293-326, 1861.
- [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. Zbl0914.65043

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.