A Global Reduction Based Algorithm for Computing Homology of Chain Complexes

Abstract

In this paper, we propose a new algorithm to compute the homology of a finitely generated chain complex. Our method is based on grouping several reductions into structures that can be encoded as directed acyclic graphs. The organized reduction pairs lead to sequences of projection maps that reduce the number of generators while preserving the homology groups of the original chain complex. This sequencing of reduction pairs allows updating the boundary information in a single step for a whole set of reductions, which shows impressive gains in computational performance compared to existing methods. In addition, our method gives the homology generators for a small additional cost.