Computing homology (Q1397805)

This paper describes a computational homology based on the use of cubical complexes. The resulting algorithm is of order \(N^{3}\) in the maximum number of cubes in any dimension, but the authors claim that in many cases it will be faster than this. The basis of the algorithm lies in a collapsing technique that is used to reduce the number of cubes in each dimension while leaving the homology unchanged. More interesting is the computation of the homology of a map. Since the authors reject the use of simplices as leading to high dimensional chain groups they need to find an alternative to simplicial approximation. They do this by defining a cubical multi-valued map which maps points of the domain to subsets of the range (essentially the smallest cube with integer coordinates containing the image of the point; scaling makes this work) such that the image of each point in the domain is a cubical set. These maps permit the use of acyclic carriers and thus allow one to compute the homology of a map. Some of the algorithms, implemented in C++, are available at \url{http://www.math.gatech.edu/~chom}.