Coreduction homology algorithm for regular CW-complexes (Q635750)

Let \(S\) denote the cells of a CW-complex with incidence map \(\kappa\), so that the boundary operator is \(\partial s=\sum_{t\in S}\kappa(s,t)t\). A pair of cells \((a,b)\) is said to be a reduction pair if \(\kappa(b,a)\neq 0\) and either \(a\) is the only cell in the boundary of \(b\), or \(b\) is the only cell whose boundary contains \(a\). The set \(S\setminus\{a,b\}\) is called a reduction of \(S\), and although it is not necessarily a CW-complex, it does form a chain complex with incidence map induced by \(\kappa\). In fact, the homologies of \(S\) and its reduction are isomorphic. Since the computation of the homology of \(S\) using the standard Smith normal form algorithm has time complexity that is polynomial in the number of cells, finding a sequence of reductions of \(S\) may reduce the computational time simply by reducing the number of cells. The authors of the article show that a finite regular CW-complex embedded in the plane can be reduced in linear time to a disjoint collection of 1-cells, the number of which gives the first Betti number. In particular, one does not need to know the specific values of the incidence map: knowledge of the facets of each cell suffice. In general however, one needs to compute the incidence map, which for a regular complex takes on the values \(0,\pm 1\). The authors provide a general algorithm for determining the incidence map for a regular finite CW-complex, as well as an explicit formula for the incidence map in the special case of a rectangular CW-complex -- where each cell is given in terms of a product of intervals. The article concludes with a section that summarizes the results of numerical experiments using their methods. Readers of the article are assumed to be familiar with elementary topology and homology. A knowledge of CW-complexes is useful.