PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
1999 | 47 | 1 | 115-131
Tytuł artykułu

Cubical approximation and computation of homology

Treść / Zawartość
Warianty tytułu
Języki publikacji
EN
Abstrakty
EN
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.
Słowa kluczowe
Rocznik
Tom
47
Numer
1
Strony
115-131
Opis fizyczny
Daty
wydano
1999
Twórcy
  • Florida Atlantic University, Boca Raton, Florida 33431, U.S.A.
  • Georgia Institute of Technology, Atlanta, Georgia 30332, U.S.A.
autor
  • Georgia Institute of Technology, Atlanta, Georgia 30332, U.S.A.
Bibliografia
  • [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.
  • [2] T. H. Cormen, C. E. Leiserson, and R. L. Rivest, Introduction to Algorithms, McGraw-Hill, 1992.
  • [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.
  • [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.
  • [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.
  • [8] T. K. Dey, H. Edelsbrunner, and S. Guha, Computational topology, preprint, 1997.
  • [9] H. Edelsbrunner, Algorithms in Combinatorial Geometry, Springer-Verlag, 1987.
  • [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.
  • [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.
  • [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.
  • [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.
  • [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.
  • [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.
  • [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.
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.bwnjournal-article-bcpv47i1p115bwm
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.