Coreduction homology algorithm for regular CW-complexes

50. Pawel Dlotko, Tomasz Kaczynski, Marian Mrozek, Thomas Wanner:
    Coreduction homology algorithm for regular CW-complexes
    Discrete & Computational Geometry 46(2), pp. 361-388, 2011.

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.

Links

The published version of the paper can be found at https://doi.org/10.1007/s00454-010-9303-y.

Bibtex

@article{dlotko:etal:11a,
   Author = {Pawe\l{} D\l{}otko and Tomasz Kaczynski and
             Marian Mrozek and Thomas Wanner},
   title = {Coreduction homology algorithm for regular {C}{W}-complexes},
   year = 2011,
   journal = {Discrete \& Computational Geometry},
   volume = 46,
   number = 2,
   pages = {361--388},
   doi = {10.1007/s00454-010-9303-y}
   }