Constructive Mayer-Vietoris Algorithm: Computing the Homology of Unions of Simplicial Complexes
Dobrina Boltcheva, Sara Merino Aceitunos, Jean-Claude Léon, Franck Hétroy · HAL (Le Centre pour la Communication Scientifique Directe) · 2010
In this research report, we present an efficient method for computing the homology of a large simplicial complex from the homologies of its sub-complexes. The method uses a constructive version of the Mayer-Vietoris exact sequence which is an algebraic tool relating the homology of a topological space to the homologies of its sub-spaces and their intersection. The method starts by decomposing the input simplicial complex into smaller sub-complexes, for which the homology is computable with the Smith Normal Form reduction algorithm. Then, the method uses the Mayer-Vietoris sequence on the decomposition graph and computes the homology of the input complex by recursive unions of the homological attributes of the sub-complexes. The proposed method outputs all homological attributes (Betti numbers, torsion coefficients and generators) and may be applied to any kind of finite simplicial complexes (manifold/non-manifold, orientable or not, embeddable or not, with heterogeneous dimensionality, etc.)