Simplicial perturbation techniques and effective homology

Simplicial Perturbation Techniques and Effective Homology Rocio Gonzalez-D´ıaz, Bel´en Medrano, Javier S´anchez-Pel´aez, and Pedro Real Departamento de Matem´atica Aplicada I, Universidad de Sevilla, Seville (Spain) {rogodi, belenmg, fjsp, real}@us.es http://www.us.es/gtocoma Abstract. In this paper, we deal with the problem of the computation of the homology of a finite simplicial complex after an “elementary simplicial perturbation” process such as the inclusion or elimination of a maximal simplex or an edge contraction. To this aim we compute an algebraic topological model that is a special chain homotopy equivalence connecting the simplicial complex with its homology (working with a field as the ground ring). 1 Introduction Simplicial complexes are widely used in geometric modelling. In order to classify them from a topological point of view, a first algebraic invariant that can be used is homology. We can cite two relevant algorithms for computing homology groups of a simplicial complex Kin Rn: The classical matrix algorithm [8] based on reducing certain matrices to their Smith normal form. And the incremental algorithm [1] consisting of assembling the complex, simplex by simplex, and at each step the Betti numbers of the current complex are updated. Both methods runintimeatmostO(m3), where mis the number of simplices of the complex. Here, we deal with the problem of obtaining the homology Hof a finite simplicial complex Kand a chain contraction (a special chain homotopy equivalence [8]) of the chain complex C(K)toH. This notion is a special case of effective homology [10]. We call it an algebraic topological model for K(or AT-model for K). Since the emergence of the Homological Perturbation Theory [5,6], chain contractions have been widely used [10,9,5,6]. The fundamental tool in this area is the Basic Perturbation Lemma (or BPL) which can be seen as a real algorithm such that the input is a chain contraction between two chain complexes (C, d) and (C,d )andaperturbationδof d. The output is a chain contraction between the perturbed chain complexes (C, d+δ)and(C,d +dδ). Here, we are interested Partially supported by the PAICYT research project FQM–296 “Computational Topology and Applied Math” from Junta de Andaluc´ıa.  Fellow associated to University of Seville under a Junta de Andalucia research grant. V.G. Ganzha, E.W. Mayr, and E.V. Vorozhtsov (Eds.): CASC 2006, LNCS 4194, pp. 166–177, 2006. c Springer-Verlag Berlin Heidelberg 2006 Simplicial Perturbation Techniques and Effective Homology 167 in the following complementary problem: given a chain contraction between two chain complexes (C, d)and(C,d ) and a “perturbation” of C, is it possible to obtain a chain contraction between the perturbed chain complexes ( ˜ C, ˜ d)and (˜ C,˜ d)?. Being the ground ring any field, Algorithms 1, 3 and 4 of this paper are positive answers to this question in the particular case of AT-models for simplicial complexes and “elementary simplicial perturbations” such as inclusion or elimination of a maximal simplex or an edge contraction. Moreover, Algorithm 1 is a version for AT-models of the incremental algorithm developed in [1]. It is described in [2, 3,4] when the ground ring is Z/2Zand applied to Digital Images for computing digital cohomology information. 2 Algebraic Topological Models Now, we give a brief summary of concepts and notations. The terminology follows Munkres book [8]. For the sake of clarity and simplicity, we only will define the concepts that are really essential in this paper. We will consider that the ground ring is any field. Simplicial Complexes. Considering an ordering on a vertex set V,aq–simplex with q+ 1 affinely independent vertices v0<···<v qof Vis the convex hull of these points, denoted by v0,...,v q.Ifi<q,ani–face of σis an i–simplex whose vertices are in the set {v0,...,v q}.Asimplexismaximal if it does not belong to any higher dimensional simplex. A simplicial complex Kis a collection of simplices such that every face of a simplex of Kis in Kand the intersection of any two simplices of Kisafaceofeachofthemorempty.Thesetofallthe q–simplices of Kis denoted by K(q).Thedimension of Kis the dimension of the highest dimensional simplex in K. Chains and Homology. Let Kbe a simplicial complex. A q–chain ais a formal sum of simplices of K(q).Theq–chains form the qth chain group of K, denoted by Cq(K). The boundary of a q–simplex σ=v0,...,v qis the (q−1)– chain: ∂q(σ)=q i=0(−1)iv0,...,ˆvi,...,v q, where the hat means that viis omitted. By linearity, ∂qcan be extended to q–chains. The collection of boundary operators connect the chain groups Cq(K)intothechain complex C(K): ···∂2 → C1(K)∂1 →C0(K)∂0 →0. An essential property is that ∂q∂q+1 =0.Inamore general framework, a chain complex Cis a sequence ··· d2 −→ C1d1 −→ C0d0 −→ 0 of abelian groups Cqand homomorphisms dq, such that for all q,dqdq+1 =0. The set of all the homomorphisms dqis called the differential of C.Aq–chain a∈Cqis called a q–cycle if dq(a)=0.Ifa=dq+1(a)forsomea∈Cq+1 then ais called a q–boundary. Denote the groups of q–cycles and q–boundaries by Zqand Bqrespectively. We say that ais a representative q–cycle of a homology generator αif α=a+Bq. Define the qth homology group to be the quotient group Zq/Bq, denoted by Hq(C). The qth Betti number βqis the rank of Hq(C). Intuitively, β0is the number of components of connected pieces, β1is the number of independent “holes” and β2is the number of “cavities”. 168 R. Gonz´alez-D´ıaz et al. Chain Contractions [7].Achain contraction of a chain complex Cto another chain complex Cis a set of three homomorphisms (f,g,φ) such that: f:C→C  and g:C→Care chain maps; fg is the identity map of C;φ:C→Cis a chain homotopy of the identity map id of Cto gf,thatis,φ∂ +∂φ =id −gf. Moreover, the annihilation properties fφ =0,φg =0andφφ = 0 are required. Important properties of chain contractions are: Chas fewer or the same number of generators than C;Cand Chave isomorphic homology groups. AT-model. Given a field as the ground ring, an AT-model for a simplicial complex Kis the set (K, h, f, g, φ)wherehis a set of generators of a chain complex Hisomorphic to the homology of Kand (f,g,φ) is a chain contraction of C(K)toH. This implies that f∂ =0and∂g =0. First Basic Perturbation Lemma (BPL) [5,6].Let (f,g,φ) be a chain contraction of the chain complex (C, d) to the chain complex (C,d ). Let δ:C→C be a morphism of degree −1, called perturbation, such that φδ is pointwise nilpotent and (d+δ)2=0.Then(fδ,g δ,φ δ)givenbyfδ=f−fδΔφ,φδ=Δφ, gδ=Δg is a chain contraction of (C, d +δ)to(C,d +dδ)whered δ=fδΔφ and Δ=∞ i=0(−1)i(φδ)i. 3 Simplicial Perturbations on AT-Models Given a simplicial complex Kwith msimplices, an elementary simplicial perturbation of Kis one of these operations: an inclusion of a simplex, a deletion of a simplex, an edge contraction. Algorithms 1, 3 and 4 compute AT-models after elementary simplicial perturbation. Moreover, the first one is a particular application of the BPL, showing in this way that there is a relation between the simplicial perturbation (where the ground graded groups are changed) and the algebraic perturbation (the original one, where just the differential changes). Theorem 1. Given an AT-model for Kand an elementary simplicial perturbation of K, an AT-model for the perturbed complex ˜ Kcan be computed using Algorithm 1, 3 or 4 in O(m2). It is necessary to say that if we do not have an AT-model of Kas input, the computation of an AT-model of ˜ Kcan be done applying Algorithm 1 m+1 times in the worst case, so the complexity, in this case, is O(m3). 3.1 AT-Models After Adding a Simplex An incremental algorithm for computing AT-models with coefficients in Z/2Z appears in [2,3,4]. Here, we give an extension of the algorithm with coefficients in any field and prove that it is a particular application of BPL. Given a chain aand a simplex σ, define cσ(a) as the coefficient of σin a. Simplicial Perturbation Techniques and Effective Homology 169 Algorithm 1. Incremental algorithm for computing AT-models for simplicial complexes in any dimension with coefficients in any field. Input: An AT-model (K, h, f, g, φ)for Kand a q-simplex σnot in K such that K∪{σ}is a simplicial complex. If f∂(σ)=0, then h:= h∪{σ},f(σ):=σ,g(σ):=σ−φ∂(σ)and φ(σ):=0. Else let β∈hsuch that λ:= cβ(f∂(σ)) =0, then h:= h\{β},f(σ):=0,φ(σ):=0. For every μ∈K If λμ:= cβ(f(K(μ)) =0 then f(μ):=f(μ)−λμλ−1f∂(σ), φ(μ):=φ(μ)+λμλ−1(σ−φ∂(σ)). End if. End for. End if. Output: The set (K∪{σ},h,f,g,φ). Theorem 2. The output of Algorithm 1 defines an AT-model for K∪{σ}. Proof. Use BPL considering two cases. –If f∂(σ)=0,letCbe the chain complex generated by the simplices of K∪{σ}with differential dgiven by d(μ):=∂(μ)ifμ∈Kand d(σ):=0. Let Hbe the chain complex with null differential generated by h∪{σ}.Let (f,g,φ ) be the chain contraction of Cto Hdefined by f(μ):=f(μ)and φ(μ):=φ(μ)ifμ∈K;g(α):=g(α)ifα∈h;f(σ):=σ,g(σ):=σand φ(σ):=0.Letδ:C→Cbe defined by δ(μ):=0ifμ∈Kand δ(σ):=∂(σ). It is easy to see that φδis pointwise nilpotent (since δφδ=0)and(d+δ)2= 0. Apply BPL to the morphism δand the chain contraction (f,g,φ )ofC to Hto obtain the chain contraction (fδ,g δ,φ δ)ofC(K∪{σ})toH. Let us prove now that (fδ,g δ,φ δ) is the chain contraction obtained in Algorithm 1. We have that fδ(μ)=(f−fδφ)(μ)=f(μ)andφδ(μ)= (φ−φδφ)(μ)=φ(μ)ifμ∈K;fδ(σ)=(f−fδφ)(σ)=σand φδ(σ)= (φ−φδφ)(σ) = 0; Finally, gδ(α)=(g−φδg)(α)=g(α)ifα∈hand gδ(σ)=(g−φδg)(σ)=σ−φ∂(σ). –If f∂(σ)=0,letβ∈hsuch that λ:= cβ(f∂(σ)) =0.LetCbe the chain complex generated by the set K∪{σ, e}where eis an element of dimension q−1 that will be eliminated at the end. The differential dof Cis given by: d(μ):=∂(μ)ifμ∈K,d(σ):=eand d(e):=0.LetHbe the chain complex with null differential generated by h.Let(f,g,φ ):C→Hbe the chain contraction given by f(e):=0,f(σ):=0,f(μ):=f(μ)if μ∈K;g(β):=g(β)−λ−1e,g(α):=g(α)ifα∈h;φ(e):=σ,φ(σ):=0, φ(μ):=φ(μ)+λμλ−1σif μ∈Kand λμ:= cβ(f(μ)) =0andφ(μ):=φ(μ) if μ∈Kand cβ(f(μ)) = 0. Let δ:C→Cbe defined by δ(μ):=0ifμ∈K, δ(e):=0andδ(σ):=∂(σ)−e. 170 R. Gonz´alez-D´ıaz et al. It is easy to see that φδis pointwise nilpotent (since δφδ=0)and (d+δ)2= 0. Apply the BPL to the morphism δand the chain contraction (f,g,φ )ofCto Hto obtain the chain contraction (fδ,g δ,φ δ)ofCto H where Cis generated by K∪{σ}∪{e}, with differential d+δ. Let us prove now that (fδ,g δ,φ δ)ofC(K∪{σ})toH(generated by h\{β}with null differential) is the chain contraction obtained in Algorithm 1. We have that fδ(σ)=(f−fδφ)(σ)=0;fδ(μ)=f(μ)−λμλ−1f∂(σ)if μ∈Kand cβ(f∂(μ)) =0andfδ(μ)=f(μ)ifμ∈Kand cβ(f∂(μ)) = 0. On the other hand, gδ(α)=(g−φδg)(α)=g(α)ifα∈h\{β}.Finally, φδ(σ)=(φ−φδφ)(σ)=0;φδ(μ)=φ(μ)+λμλ−1(σ−φ∂(σ)) if μ∈Kand λμ=cβ(f∂(μ)) =0andφδ(μ)=φ(μ)ifμ∈Kand λμ=cβ(f∂(μ)) = 0. Fig. 1. The simplicial complexes A,Band C Using the algorithm above it is possible to design a procedure for computing AT-models for finite simplicial complexes in any dimension with coefficients in any field. Fig. 2. The simplicial complexes D,E,andF Algorithm 2. Computing an AT-model for a simplicial complex of any dimension with coefficients in any field. Input: A simplicial complex Kand an ordered-by-increasing-dimension set of all the simplices of K:{σ0,...,σ n}. Simplicial Perturbation Techniques and Effective Homology 171 Define K0:= {σ0},h:= {σ0},f(σ0):=σ0,g(σ0):=σ0,φ(σ0):=0. For i=1 to i=mdo apply Algorithm 1 to Ki−1and σi. Ki:= Ki−1∪{σi}. End for. Output: An AT-model (Km,h,f,g,φ)for K. The implementation of the algorithm described before has been made by J. S´anchez-Pel´aez and P. Real. In Figures 1, 2, 3, 4, and 5, examples of computations (using this implementation) of AT-models for three-dimensional simplicial complexes are shown. Example 1. Consider the simplicial complexes A,B,C,D,Eand Fshown in Figures 1 and 2. In Figures 3, 4, and 5, representative cycles of the homology generators of these complexes are shown. In the following table, we present the Betti numbers obtained and the running time for computing AT-models for these simplicial complexes in a Pentium 4, 3.2 GHz, 1Gb RAM. Fig. 3. The representative 1-cycles (holes) of A,B,andC Simplicial complex KNumber of simplices of KTime β0β1β2 A4586 7 seconds 114 15 B13421 12 seconds 346 39 C3286 4 seconds 117 10 D18842 30 seconds 127 5 E26308 50 seconds 2 9 3 F31113 38 seconds 138 419 13 3.2 AT-Models After Deleting a Maximal Simplex Now, an algorithm for computing an AT-model for a simplicial complex Kof any dimension with coefficients in any field after deleting a maximal simplex of Kis described. 172 R. Gonz´alez-D´ıaz et al. Fig. 4. Therepresentative2-cycles(cavities)ofA,B,andC Algorithm 3. Decremental algorithm for computing AT-models for simplicial complexes of any dimension with coefficients in any field. Input: An AT-model (K, h, f, g, φ)for Kand a maximal q-simplex σin K. If there exists β∈hsuch that λ:= cσ(g(β)) =0, then h:= h\{β}. For every μ∈K\{σ}and α∈h If λμ:= cβ(f(μ)) =0 then f(μ):=f(μ)−λμβ. End if. If λ μ:= cσ(φ(μ)) =0 then φ(μ):=φ(μ)−λ μλ−1g(β). End if. If λα:= cσ(g(α)) =0 then g(α):=g(α)−λαλ−1g(β). End if. End for. Else let γ∈Kbe a (q−1)-simplex not in hthen h:= h∪{γ}and g(γ):=∂(σ). For every μ∈K\{σ} If λ μ:= cσ(φ(μ)) =0then f(μ):=f(μ)+λ μγand φ(μ):=φ(μ)−λ μφ∂(σ). End if. End for. End if. Output: The set (K\{σ},h,f,g,φ) Observe that the simplex γalways exists since the morphism fis onto and f∂(σ)=0. Theorem 3. The set (K\{σ},h,f,g,φ)defines an AT-model for K\{σ}. Proof. Let us denote by (K, hK,f K,g K,φ K)anAT-modelforKand by (K\ {σ},h,f,g,φ)theAT-modelforK\{σ}obtained using Algorithm 3. In order to prove that the output of Algorithm 3 is an AT-model for K\{σ},wecheck the two most important properties wich are fg =id and id−gf =φ∂ +∂φ.The rest of the properties are left to the reader. Simplicial Perturbation Techniques and Effective Homology 173 Fig. 5. The holes and cavities of D,E,andF We distinguish two cases. –If there exists β∈hKsuch that λ:= cσ(g(β)) = 0 (recall that h:= hK\{β}). •If α∈hsuch that λα:= cσ(gK(α)) =0thenfg(α)=f(gK(α)− λαλ−1gK(β)) = fKgK(α)−λαλ−1(fKgK(β)−β)=α. Otherwise, fg(α)=fgK(α)=fKgK(α)=α. •If μ∈K\{σ}and λ μ:= cσ(φK(μ)) =0then(φ∂ +∂φ)(μ)=φK∂(μ)+ ∂(φK(μ)−λ μλ−1 1gK(α1)) = μ−gKfK(μ)=μ−gfK(μ)=μ−gf(μ). If cσ(φK(μ)) = 0 and λ∂μ := cσ(φK∂(μ)) =0then(φ∂ +∂φ)(μ)= φK∂(μ)−λ∂μλ−1 1gK(α1)+∂φK(μ)=μ−gKfK(μ)−λ∂μλ−1 1gK(α1)= μ−gf(μ). In other case, (φ∂ +∂φ)(μ)=φK∂(μ)+∂φK(μ)=μ−gKfK(μ)= μ−gf(μ). –Otherwise, let γ∈Kbe a (q−1)-simplex not in hK(recall that h:= hK∪{γ} and g(γ):=∂(σ)). •fg(γ)=f∂(σ)=fK∂(σ)+γ=γ. If α∈hK,fg(α)=fgK(α)=fKgK(α)=α. •If μ∈K\{σ}and λ μ:= cσ(φK(μ)) =0then(φ∂ +∂φ)(μ)=φK∂(μ)+ ∂φK(μ)−λμ∂φK∂(σ)=μ−gKfK(μ)−λμ∂(σ)=μ−gf(μ). In other case, (φ∂ +∂φ)(μ)=φK∂(μ)+∂φK(μ)=μ−gKfK(μ)= μ−gf(μ). Example 2. Let us show a simple example of the computation of an AT-model after deleting a maximal simplex. Consider a simplicial complex Kwhose set of maximal simplices is {0,1,2,1,2,3}. The data of an AT-model for Kis showed in the following table. K h f g φ 0 0 0 00 1 0 0,1 2 0 0,2 3 0 0,1+1,3 0,10 0 0,20 0 1,30 0 2,301,2,3 1,200,1,2 0,1,20 0 1,2,30 0 174 R. Gonz´alez-D´ıaz et al. After applying Algorithm 3 to the AT-model (K, h, f, g, φ)forKand the maximal simplex 1,2,3we obtain the AT-model (K\{1,2,3},h,f,g,φ)for K\{1,2,3} whose data are: K\{1,2,3} h f g φ 0 0 0 00 1 0 0,1 2 0 0,2 3 0 0,1+1,3 0,10 0 0,20 0 1,30 0 2,3 2,3 2,3 2,3−1,3+1,2−0,1,2 1,200,1,2 0,1,20 0 3.3 AT-Models After Edge Contractions Finally, we deal with the problem of obtaining an AT-model for a simplicial complex Kafter an edge contraction. An edge contraction is given by the vertex map f(0) :K(0) →L(0) =K(0) −{b} where f(0)(b)=aand f(0)(v)=vfor all v=b. Let Kbe a simplicial complex and Ba subset of K. Define B={σ∈K:σis a face of σ∈B}, StB ={σ∈K:σ∈Bis a face of σ}and Lk B =StB −StB. The following algorithm computes an AT-model for a simplicial complex K after and edge contraction in three steps. The goal of the first step is to obtain a chain contraction of C(K) to the chain complex associated to a new simplicial complex (that we also denote by K) satisfying that LkK{a} ∩ LkK{b} = LkK{a, b}. In the second step, an AT-model (K, h, f, g, φ) for the new simplicial complex Kobtained at the first step is computed. At the final step, an AT-model for the simplicial complex Kafter an edge contraction, by composing the chain contractions obtained at the previous steps is obtained. Algorithm 4. Computing AT-models after edge contractions. Input: An AT-model AT := (K, hK,f K,g K,φ K)for K, an edge a, b∈Kand an ordered-by-increasing-dimension set of all the simplices of LkK{a} ∩ LkK{b}\LkK{a, b}: {σ1=w1 0, ..., w1 m1,...,σ n=wn 0, ..., wn mn}.