Homology computation by reduction of chain complexes (Q1129483)

The authors present an algorithm for computation of homology for a finitely generated free chain complex with a coefficient ring \({\mathcal R}\). The algorithm is based on successive reductions of the given chain complex to a homotopically equivalent, but much simpler complex. The method of this reduction relies on simple combinatorics. In case \({\mathcal R}\) a field, the final complex has zero differentials and therefore gives homology immediately. The method makes it also possible to compute the induced map \(f_*\) on homology, where \(f\) is a chain map. The complexity of the algorithm is also discussed. The authors are able to estimate the complexity in several special cases, obtaining linear running time for a planar polyhedron.