Constructive Mayer-Vietoris Algorithm: Computing the Homology of Unions of Simplicial Complexes

Dobrina Boltcheva; Sara Merino; Jean-Claude Léon; Franck Hétroy

inria-00542717, version 1

Constructive Mayer-Vietoris Algorithm: Computing the Homology of Unions of Simplicial Complexes

Dobrina Boltcheva ()^a^, 1, 2, Sara Merino^b^, 1, Jean-Claude Léon ³, Franck Hétroy ^1, 2

N° RR-7471 (2010)

Abstract: 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.)

a – INRIA
b – Grenoble INP
1: EVASION (INRIA Grenoble Rhône-Alpes / LJK Laboratoire Jean Kuntzmann)
CNRS : UMR5224 – INRIA – Laboratoire Jean Kuntzmann – Institut National Polytechnique de Grenoble (INPG) – Université Joseph Fourier - Grenoble I – Université Pierre-Mendès-France - Grenoble II
2: MORPHEO (INRIA Grenoble Rhône-Alpes / LJK Laboratoire Jean Kuntzmann)
INRIA – Institut National Polytechnique de Grenoble (INPG) – Université Joseph Fourier - Grenoble I
3: Laboratoire des sciences pour la conception, l'optimisation et la production (G-SCOP)
CNRS : UMR5272 – Institut National Polytechnique de Grenoble (INPG) – Université Joseph Fourier - Grenoble I

inria-00542717, version 1
http://hal.inria.fr/inria-00542717
oai:hal.inria.fr:inria-00542717
From: Dobrina Boltcheva <>
Submitted on: Friday, 3 December 2010 12:33:29
Updated on: Thursday, 12 May 2011 11:41:04

See detailed view

Associated documents

PDF :

Export

Bibtex EndNote TEI RefWorks

%% inria-00542717, version 1
%% http://hal.inria.fr/inria-00542717
@techreport{boltcheva:inria-00542717,
    hal_id = {inria-00542717},
    url = {http://hal.inria.fr/inria-00542717},
    title = {{Constructive Mayer-Vietoris Algorithm: Computing the Homology of Unions of Simplicial Complexes}},
    author = {Boltcheva, Dobrina and Merino, Sara and L{\'e}on, Jean-Claude and H{\'e}troy, Franck},
    abstract = {{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.)}},
    keywords = {Homologie constructive ; S{\'e}quence exacte de Mayer-Vietoris ; Complexe simplicial ; Algorithme ; G{\'e}n{\'e}rateurs},
    language = {English},
    affiliation = {EVASION - INRIA Grenoble Rh{\^o}ne-Alpes / LJK Laboratoire Jean Kuntzmann , MORPHEO - INRIA Grenoble Rh{\^o}ne-Alpes / LJK Laboratoire Jean Kuntzmann , Laboratoire des sciences pour la conception, l'optimisation et la production - G-SCOP},
    type = {Research Report},
    institution = {INRIA},
    number = {RR-7471},
    year = {2010},
    month = Dec,
    pdf = {http://hal.inria.fr/inria-00542717/PDF/RR-7471.pdf},
}

%F inria-00542717, version 1
%0 Report
%U http://hal.inria.fr/inria-00542717
%2 MATH:MATH_AT;INFO:INFO_CG
%T Constructive Mayer-Vietoris Algorithm: Computing the Homology of Unions of Simplicial Complexes
%A Boltcheva, Dobrina
%A Merino, Sara
%A Léon, Jean-Claude
%A Hétroy, Franck
%+ EVASION - INRIA Grenoble Rhône-Alpes / LJK Laboratoire Jean Kuntzmann , MORPHEO - INRIA Grenoble Rhône-Alpes / LJK Laboratoire Jean Kuntzmann , Laboratoire des sciences pour la conception, l'optimisation et la production - G-SCOP
%X 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.)
%2 Dans ce rapport, nous présentons une méthode efficace pour le calcul de l'homologie d'un complexe simplicial, à partir des homologies de ses sous-complexes. La méthode est basée sur une version constructive de la séquence exacte de Mayer-Vietoris qui est un outil algébrique permettant de trouver l'homologie de l'union de deux espaces topologiques, à partir de l'homologie de leur somme directe et de leur intersection. La méthode commence par décomposer le complexe simplicial 3D en sous-complexes pour lesquels l'homologie est plus facile à calculer par la réduction de Smith. Ensuite, l'algorithme parcourt le graphe de la décomposition et utilise la séquence de Mayer-Vietoris pour calculer l'homologie du complexe initial par unions récursives des attributs homologiques de ses sous-complexes. La méthode fournit tous les attributs homologiques (nombres de Betti, coefficients de torsion et générateurs) et peut être appliquée à tout type de complexes simpliciaux fini (variété/non-variété, orientable/non-orientable, plongeable ou non, muilt-dimensionalité, etc).
%G English
%2 Research Report
%8 2010-12-03
%K Homologie constructive ; Séquence exacte de Mayer-Vietoris ; Complexe simplicial ; Algorithme ; Générateurs
%Z RR-7471

<?xml version="1.0" encoding="UTF-8"?>
<listBibl xmlns="http://www.tei-c.org/ns/1.0" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:mml="http://www.w3.org/1998/Math/MathML">
<listBibl type="report"><head>Research reports</head>
<biblStruct type="report" xml:id="inria-00542717"><monogr>
<author><persName><forename>Dobrina</forename><surname>Boltcheva</surname></persName>
<affiliation>
<orgName type="laboratory">INRIA Grenoble Rhône-Alpes / LJK Laboratoire Jean Kuntzmann</orgName>
<orgName type="team">EVASION</orgName>
<country>FR</country>
<orgName type="institution">CNRS : UMR5224</orgName>
<orgName type="institution">INRIA</orgName>
<orgName type="institution">Laboratoire Jean Kuntzmann</orgName>
<orgName type="institution">Institut National Polytechnique de Grenoble (INPG)</orgName>
<orgName type="institution">Université Joseph Fourier - Grenoble I</orgName>
<orgName type="institution">Université Pierre-Mendès-France - Grenoble II</orgName>
</affiliation>
<affiliation>
<orgName type="laboratory">INRIA Grenoble Rhône-Alpes / LJK Laboratoire Jean Kuntzmann</orgName>
<orgName type="team">MORPHEO</orgName>
<country>FR</country>
<orgName type="institution">INRIA</orgName>
<orgName type="institution">Institut National Polytechnique de Grenoble (INPG)</orgName>
<orgName type="institution">Université Joseph Fourier - Grenoble I</orgName>
</affiliation>
</author>
<author><persName><forename>Sara</forename><surname>Merino</surname></persName>
<affiliation>
<orgName type="laboratory">INRIA Grenoble Rhône-Alpes / LJK Laboratoire Jean Kuntzmann</orgName>
<orgName type="team">EVASION</orgName>
<country>FR</country>
<orgName type="institution">CNRS : UMR5224</orgName>
<orgName type="institution">INRIA</orgName>
<orgName type="institution">Laboratoire Jean Kuntzmann</orgName>
<orgName type="institution">Institut National Polytechnique de Grenoble (INPG)</orgName>
<orgName type="institution">Université Joseph Fourier - Grenoble I</orgName>
<orgName type="institution">Université Pierre-Mendès-France - Grenoble II</orgName>
</affiliation>
</author>
<author><persName><forename>Jean-Claude</forename><surname>Léon</surname></persName>
<affiliation>
<orgName type="laboratory">G-SCOP</orgName>
<orgName type="team">Laboratoire des sciences pour la conception, l'optimisation et la production</orgName>
<country>FR</country>
<orgName type="institution">CNRS : UMR5272</orgName>
<orgName type="institution">Institut National Polytechnique de Grenoble (INPG)</orgName>
<orgName type="institution">Université Joseph Fourier - Grenoble I</orgName>
</affiliation>
</author>
<author><persName><forename>Franck</forename><surname>Hétroy</surname></persName>
<affiliation>
<orgName type="laboratory">INRIA Grenoble Rhône-Alpes / LJK Laboratoire Jean Kuntzmann</orgName>
<orgName type="team">EVASION</orgName>
<country>FR</country>
<orgName type="institution">CNRS : UMR5224</orgName>
<orgName type="institution">INRIA</orgName>
<orgName type="institution">Laboratoire Jean Kuntzmann</orgName>
<orgName type="institution">Institut National Polytechnique de Grenoble (INPG)</orgName>
<orgName type="institution">Université Joseph Fourier - Grenoble I</orgName>
<orgName type="institution">Université Pierre-Mendès-France - Grenoble II</orgName>
</affiliation>
<affiliation>
<orgName type="laboratory">INRIA Grenoble Rhône-Alpes / LJK Laboratoire Jean Kuntzmann</orgName>
<orgName type="team">MORPHEO</orgName>
<country>FR</country>
<orgName type="institution">INRIA</orgName>
<orgName type="institution">Institut National Polytechnique de Grenoble (INPG)</orgName>
<orgName type="institution">Université Joseph Fourier - Grenoble I</orgName>
</affiliation>
</author>
<title type="main" level="m">Constructive Mayer-Vietoris Algorithm: Computing the Homology of Unions of Simplicial Complexes</title><title type="main" level="m">Constructive Mayer-Vietoris Algorithm: Computing the Homology of Unions of Simplicial Complexes</title><imprint><biblScope type="publicationDate">2010-12-03</biblScope></imprint></monogr><idno type="HALid">http://hal.inria.fr/inria-00542717</idno><idno type="HALFile">http://hal.inria.fr/inria-00542717/PDF/RR-7471.pdf</idno></biblStruct>
</listBibl>
</listBibl>