Go backward to 33 f-Vector of Simplicial Complexes
Go up to 7 Beyond Polytopes
Go forward to 35 Shellability

34 Homology

Input: Finite abstract simplicial complex D given by a list of facets, i Î N
Output: The i-th homology group of D, given by its rank and its torsion coefficients
Status (general): Open
Status (fixed dim.): Polynomial time
There exists a polynomial time algorithm if D is given by the list of all simplices, since the Smith normal form of an integer matrix can be computed efficiently (Iliopoulos [31]). For fixed i or dim(D) - i, the sizes of the boundary matrices are polynomial in the size of D and the Smith normal form can again be computed efficiently.