Extending the notion of AT-Model for integer homology computation

Extending the Notion of AT-Model for Integer Homology Computation Rocio Gonzalez-Diaz, Mar´ıa Jos´eJim´enez, Bel´en Medrano, and Pedro Real Applied Math Department, University of Sevilla, Seville, Spain {rogodi,majiro,belenmg,real}@us.es http://alojamientos.us.es/gtocoma Abstract. When the ground ring is a field, the notion of algebraic topological model (AT-model) is a useful tool for computing (co)homology, representative (co)cycles of (co)homology generators and the cup product on cohomology of nD digital images as well as for controlling topological information when the image suffers local changes [6,7,9]. In this paper, we formalize the notion of λ-AT-model (λbeing an integer) which extends the one of AT-model and allows the computation of homological information in the integer domain without computing the Smith Normal Form of the boundary matrices. We present an algorithm for computing such a model, obtaining Betti numbers, the prime numbers pinvolved in the invariant factors (corresponding to the torsion subgroup of the homology), the amount of invariant factors that are a power of pand a set of representative cycles of the generators of homology mod p,for such p. 1 Introduction There are many tasks in Vision and Image Processing that involve computing certain topological characteristics of objects in a given image such as, for example, connectivity and the number of holes and cavities. We focus here on homology groups (connectivity and the number of holes and cavities can be obtained from them), which are known to be computable in finite dimensions. The classical algorithm for computing integer homology is based on performing row and column operations on the boundary matrices in order to reduce them to the Smith Normal Form (SNF). The integer homology groups can be then determined from this canonical form (see, for example, [13]). However, explicit examples can be given for which this algorithm has a worst-case computational complexity which grows exponentially in both space and time [4]. Our aim is the computation of integer homology information avoiding the computation of the SNF in the integer domain. In fact, our approach allows the computation of Betti numbers, the prime numbers pinvolved in the invariant Partially supported by Junta de Andaluc´ıa (FQM-296 and TIC-02268) and Spanish Ministry for Science and Education (MTM-2006-03722).  Fellow associated to University of Seville under a Junta de Andalucia research grant. F. Escolano and M. Vento (Eds.): GbRPR 2007, LNCS 4538, pp. 330–339, 2007. c Springer-Verlag Berlin Heidelberg 2007 Extending the Notion of AT-Model for Integer Homology Computation 331 factors (corresponding to the torsion subgroup of the homology), the amount of invariant factors that are a power of pand a set of “moduli” representative cycles of the generators of homology in polynomial time. Moreover, our method is not only valid for simplicial complexes but also for other combinatorial objects such as cubical complexes or simploidal complexes since we deal with the group structures. In the first part of the paper, we recall classical definitions from Algebraic Topology. We also present previous tools for computing topological information: AT-models and AM-models, and we recall the main properties of these structures. Furthermore, we define the notion of λ-AT-model, study its properties, give an algorithm for computing it and study its complexity. Finally, we describe how to obtain homology information in the integer domain from a λ-AT-model. The last section is devoted to conclusions and future works. 2 Definitions and Prior Work This section introduces the background needed throughout the paper which is essentially extracted from Munkres’ book [13]. We also recall briefly the concepts of AT-model and AM-model and their properties. Achain complex Cis a sequence {Cq,d q}of abelian groups Cqand homomorphisms dq:Cq+1 →Cq, ··· d3 −→ C2d2 −→ C1d1 −→ C0d0 −→ 0, such that, for all q,dqdq+1 = 0. The set of all the homomorphisms dq(q≥0) is called the differential of C. The chain complex Cis free if Cqis a free abelian group for each q.Itisfinite if there exists an integer n>0 such that Cq=0for q>nand each abelian group Cqis finitely generated. In this case, if Cn=0, we say that dim of Cis n,andthen,Ccan be encoded as a pair (C, d), where C=n q=0 Bq,beingBqa basis of Cqand dthe matrix corresponding to the differential of Cwith respect to the basis C. Suppose that Bq={a1,...,a mq}. Aq-chain a∈Cis a formal sum of elements of Bq,a=mq i=0 λiai,whereλi∈Z and ai∈Cq. In this case, dim a=qand ca(ai) denotes the coefficient λi. Since our goal is the computation of homology information of “finite” objects (for example, objects explicitly represented within a computer), all chain complexes are finite and free. Example 1. Shapes are classically modelled with a cellular subdivision. Several combinatorial structures may represent such subdivision. Simplicial complexes haveproventobeausefultooltomodelageometric object. Roughly speaking, they are collections of simplices (convex hulls of a set of affinely independent points) that fit together in a natural way to form the object. For every simplicial complex K, one can define a chain complex C(K) canonically associated to it. The homology of Kis then defined as the homology of C(K) [13]. Another way to extract combinatorial information from a geometric structure arising naturally, for example, from tomography, numerical computations and graphics, 332 R. Gonzalez-Diaz et al. is by means of cubical grids, which subdivide the space into cubes with vertices in an integer lattice. This approach, that can be generalized to an arbitrary dimension, is a cubical complex. The homology of a given cubical complex is the homology of the cubical chain complex associated to it [11]. Finally, simploidal sets [1] include simplicial complexes and cubical complexes as particular cases. They can be used for representing “hybrid” grids coming from finite element methods. In [15], a free chain complex is associated to a simploidal set and the homology of the simploidal set is defined as the homology of the associated chain complex. We base all formulas and algorithms in this paper on an ordered basis of the chain complex Cwhere each prefix of the ordering contains the basis of a subcomplex. We call such an ordering a filter. In other words, given a chain complex C, C={a1,...,a m}is a filter if it is a basis of the chain complex Cand for each j(where 1 ≤j≤m), C={a1,...,a j}is a basis of a subcomplex of C.For instance, given a chain complex D=(D,d), a reordering D={c 1,...,c  m}of Dsuch that dim c i≤dim c jwhen i<j,isalwaysafilterofD. Example 2. Consider the simplicial complex Sderived from the triangulation of the Klein bottle given in Figure 1 and the chain complex C(S) associated to S. Then, C(S)={a,d,ad,f,af,df,adf,b,ab,bf,abf,c,bc,cf,bcf,g,cg,fg,cfg, ac,ag,acg,e,ae,eg,aeg,de,ef,def,h,fh,eh,efh,gh,fgh,i, gi, hi, ghi, ei, egi, di, dei, ah, aeh, bh, abh, bi,bhi, ci, bci, ai, aci, adi }, where v0···vndenotes the simplex spanned by the vertices v0,...,v n,isafilter of C(S). The chain ais a q-cycle if a∈Ker dq.Ifa∈Im dq+1 then ais called a q-boundary. Denote the groups of q–cycles and q–boundaries by Zqand Bqrespectively. Define the integer qth homology group to be the quotient group Zq/Bq, denoted Fig. 1. The Klein bottle and a triangulation of it Extending the Notion of AT-Model for Integer Homology Computation 333 by Hq(C;Z). We say that ais a representative q–cycle of the homology generator a+Bq(denoted by [a]). For each q,theintegerqth homology group Hq(C;Z)is a finitely generated abelian group. Then Hq(C;Z) is isomorphic to Fq⊕Tqwhere Fq=Z⊕···⊕Zand Tq=(Z/α(q,1))⊕···⊕(Z/α(q,s)) are the free subgroup and the torsion subgroup of Hq(C;Z), respectively. The rank of Fq, denoted by βq, is called the qth Betti number of C.Eachα(q,i)is apowerofaprime,α(q,i)=pt(q,pi) i. They are called the invariant factors of Hq(C;Z). The numbers βqand α(q,i)are uniquely determined by Hq(C;Z)(up to a rearrangement). Therefore, this representation is in some sense a “canonical form” for Hq(C;Z). The qth homology group of Cwith coefficients in Z/p for pa prime, denoted by Hq(C;Z/p), is a vector space. Its rank, denoted by β(q,p), depends on the prime p. Universal Coefficient Theorem for Homology [13, p. 332] implies that for each prime p, T(0,p)=β(0,p)−β0and T(q,p)=β(q,p)−βq−T(q−1,p)for q>0; where T(i,p)is the number of invariant factors of Hi(C;Z)thatareapowerofp. Let C={Cq,d q}and C={C q,d  q}be two chain complexes. A chain map f: C→C is a family of homomorphisms {fq:Cq→C q}such that d qfq=fq−1dq for all q≥0. A chain map f:C→C induces a homomorphism f∗:H(C;Z)→ H(C;Z)wheref∗[a]=[f(a)] for [a]∈H(C;Z). If f,g :C→C are chain maps, then a chain homotopy φ:C→C of fto gis a family of homomorphisms {φq:Cq→C q+1}such that fq−gq=d q+1φq+φq−1dq. 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and φ:C→Cis a chain homotopy of the identity map of Cto gf,thatis,φd +dφ =idC−gf. Important properties of chain contractions are: Chas fewer or the same number of generators than C;andCand Chave isomorphic homology groups. An AT-model [6,7,9] for a chain complex C=(C, d) is a chain contraction of C to a chain complex Hwith null differential. An AT-model can be stored as a set ((C, d),H,f,g,φ), where Cand Hare basis of Cand H,andf,gand φare the matrices corresponding to the homomorphisms that defines the chain contraction of Cto H. Observe that the homology of Cis isomorphic to H. If the ground ring is Z/p,beingpa prime, the following algorithm computes an AT-model for a given chain complex. This algorithm is a straightforward modification of that in [9]. Algorithm 1. Computing an AT-model for a chain complex Cover Z/p. Input: a filter C={a0,...,a m}of the chain complex C, and the matrix of the differential dfor the basis C. H:= {},f:= 0,g:= 0,φ:= 0. 334 R. Gonzalez-Diaz et al. For i=0 to mdo If fd(ai)=0, then H:= H∪{ai},f(ai):=ai,φ(ai):=0,g(ai):=ai−φd(ai). If fd(ai)=0, then: μi:= min {cfd(ai)(aj),j=0, .., i −1}, k:= max {jsuch that cfd(ai)(aj)=μi,j=0, ..., i −1}, H:= H\{ak},f(ai):=0,φ(ai):=0. For j=0 to i−1do, λaj:= cf(aj)(ak), f(aj):=f(aj)−μ−1 iλajfd(ai), φ(aj):=φ(aj)+μ−1 iλaj(ai−φd(ai)), Output: the set ((C, d),H,f,g,φ). The key idea of this algorithm is the same as in [3]: in the ith step, the element aiof the filter Cis added and then, a homology class is created or destroyed. The algorithm runs in time at most O(m3), where mis the number of elements of C. Recall that the notion of AT-model is an useful tool for computing (co)homology, representative cycles of (co)homology generators and the cup product on cohomology of nD digital images as well as for controlling topological information when the image suffers local changes [6,7,9]. The main problem of the computation of AT-models over Z/p is that if the object under study contains torsion, then the Betti numbers β(q,p)can change when pvaries. Example 3. The Betti numbers of the simplicial complex S(see Figure 1) computed over the field Z/p,forp=2,3,29. β(0,p)β(1,p)β(2,p) Z/2 1 2 2 Z/3 1 1 0 Z/29 1 1 0 An AM-model [5] for a chain complex C=(C, d) is a chain contraction (f,g,φ) of Cto M=(M,d) such that the matrix Aof the differential dcoincides with its Smith normal form and satisfies that any non-null entry of Ais greater than 1. Working with coefficients in the integer domain, an AM-model for Ccan always be computed. Moreover, the integer (co)homology of Cand representative cycles of (co)homology generators can be directly obtained from M[8]. The algorithm for computing AM-models given in [8] needs to reduce the matrix of the differential to its Smith Normal Form (SNF). Explicit examples can be given for which the computation of SNF has a worst-case computational complexity which grows exponentially in both space and time [4]. Many algorithms have been devised to improve this complexity bound [10,17,2,14]. Our aim in this paper is the computation of integer homology information avoiding the computation of the SNF in the integer domain. Extending the Notion of AT-Model for Integer Homology Computation 335 3 Extending the Notion of Algebraic Topological Model In this section we will consider that the ground ring is Z. We first define the notion of λ-AT-model which is a generalization of the one of AT-model. We study its properties, give an algorithm for computing it and study its complexity. Definition 1. Let C=(C, d)be a chain complex, λa non-null integer and H=(H, d)a chain complex with null differential (that is, d=0). Let f: C→H,g:H→Cand φ:C→Cbe three homomorphisms. Then the set ((C, d),H,f,g,φ,λ)is a λ-AT-model if fand gare chain maps, fg =λ·idH and φis a chain homotopy of λ·idCto gf, that is, λ·idC−gf =φd +dφ. Proposition 1. Given a λ-AT-model, a rational AT-model (i.e., an AT-model over Q) can directly be obtained as well as rational (co)homology and representative cycles of (co)homology generators. Concretely, if ((C, d),H,f,g,φ,λ)is a λ-AT-model for a chain complex C,then((C, d),H, 1 λf,g, 1 λφ)is an AT-model for Cover Qand {g(h):h∈H}is a set of representative cycles of the generators of H(C;Q). Corollary 1. Let ((C, d),H,f,g,φ,λ)be a λ-AT-model. Then H(the chain complex generated by Hwith null differential) is isomorphic to the free subgroup of H(C;Z). Moreover, the set {g(h):h∈H}is a set of independent non-boundary cycles of Cover Z. Proposition 2. Given a λ-AT model ((C, d),H,f,g,φ,λ)and a prime psuch that pdoes not divide λ,then((C, dp),H,f p,g p,φ p),wheredp=dmod p,fp= λ−1fmod p,gp=gmod pand φp=λ−1φmod p, is an AT-model for Cover Z/p and {gp(h):h∈H}is a set of representative cycles of the generators of H(C;Z/p). Proposition 3. Let ((C, d),H,f,g,φ,λ)be a λ-AT-model. Let a∈Csuch that d(a)=0.Ifthereexistsb∈Csuch that d(b)=αa where α∈Zand α=0,then f(a)=0. Proof. Suppose that b∈Csuch that d(b)=αa where α∈Zand α=0,and f(a)=0.Thenαf(a)= 0 (since the ground ring is Z). On the other hand, αf(a)=f(αa)=f(d(b)) = 0, a contradiction.  Corollary 2. Let ((C, d),H,f,g,φ,λ)be a λ-AT-model. Let a∈Csuch that d(a)=0.Ifthereexistsb∈Csuch that d(b)=αa where α∈Z,α=0,andfor each β,where0<β<α,βa ∈ Im d.thenαdivides λ. Proof. By Proposition 3, we have f(a) = 0. Since λa −gf(a)=φd(a)+dφ(a), then λa =dφ(a). Suppose that αdoes not divide λ.Thereexistsc, r ∈Z,such that 0 <r<αand λ=cα +r. On one hand, ra ∈ Im d; on the other hand, ra =(λ−cβ)a=d(φ(a)−cb)∈Im d, a contradiction. We conclude that alpha divides λ. 336 R. Gonzalez-Diaz et al. Corollary 3. Let ((C, d),H,f,g,φ,λ)be a λ-AT-model. If α=pt(q,p)is an invariant factor of Hq(C;Z),thenpdivides λ. Algorithm 2. Algorithm for computing a λ-AT-model for a chain complex C. Input: a filter C={a0,...,a m}of the chain complex C, and the matrix of the differential dfor the basis C. H:= {},λ:= 1,f:= 0,g:= 0,φ:= 0. For i=0 to mdo If fd(ai)=0, then H:= H∪{ai},f(ai):=ai,φ(ai):=0,g(ai):=λai−φd(ai). If fd(ai)=0, then μi:= min {|cfd(ai)(aj)|,j=0, .., i −1}, k:= max {jsuch that |cfd(ai)(aj)|=μi,j=0, ..., i −1}, λk:= cfd(ai)(ak), H:= H\{ak},f(ai):=0,φ(ai):=0. For j=0 to i−1, λaj:= cf(aj)(ak), f(aj):=λkf(aj)−λajfd(ai), φ(aj):=λkφ(aj)+λaj(λai−φd(ai)), λ:= λλk. Output: The set ((C, d),H,f,g,φ,λ). Theorem 3. The set ((C, d),H,f,g,φ,λ)obtained applying Algorithm 2 defines aλ-AT-model for the chain complex C=(C, d). Proof. Assume that ((Ci−1,d),H i−1,f i−1,g i−1,φ i−1,λ i−1)istheλi−1-AT-model obtained using the algorithm above for the filter Ci−1={a0,...,a i−1}. Assume that the annihilation properties fi−1φi−1=0,φi−1gi−1=0andφi−1φi−1=0 hold. We will prove that the set (Ci,d),f i,g i,φ i,λ i) obtained after adding aito the filter Ci−1is a λi-AT-model. More concretely, we will prove that fid= 0, dgi=0,figi=λi·id,λi·id −gifi=φid+dφi,fiφi=0,φigi=0 and φiφi= 0. We deal only with the case fi−1d(ai)= 0; the other case is left to the reader. First, fid(ai)=λkfi−1d(ai)−λkfi−1d(ai) = 0. Second, φid(ai)+dφi(ai)=λkφi−1d(ai)+λk(λi−1ai−φi−1d(ai)) = λiai=λiai− gifi(ai). Finally, it is clear that fiφi(ai)=0andφiφi(ai)=0.Now,letaj∈ Ci−1,thenfid(aj)=λkfi−1d(aj) which is null by induction; φid(ai)+dφi(ai) =λkφi−1d(aj)+λd(aj)(λi−1ai−φi−1d(ai)) + λkdφi−1(aj)+λaj(λi−1d(ai)− dφi−1d(ai)) = λk(λi−1aj−gi−1fi−1(aj)) + λajgi−1fi−1d(ai)=λiaj−gifi(aj). Moreover, fiφi(aj)=fi(λkφi−1(aj)+λaj(λi−1ai−φi−1d(ai))) = 0; φiφi(aj)= φi(λkφi−1(aj)+λaj(λi−1ai−φi−1d(ai))) = 0. If aj∈Hi,thendgi(aj)= dgi−1(aj) = 0, by induction; figi(aj)=λkfi−1gi−1(aj)−λgi−1(aj)fi−1d(aj)= λkλi−1aj=λiaj. Finally, it is easy to see that φigi(aj)=0.  To study the complexity, fix the dimension of the complex, n, and count the number of elementary operations involved in the algorithm. In the ith step, we have to evaluate fi−1d(ai). The numbers of elements of Cinvolved in d(ai) Extending the Notion of AT-Model for Integer Homology Computation 337 and fi−1(aj)for1≤j<iis at most nand m, respectively. Therefore, the evaluation of fi−1d(ai)costsO(nm)=O(m). If fi−1d(ai)=0,wehaveto update fi−1(aj)andφi−1(aj)for1≤j<i. The total cost of these operations is O(m2). Therefore, the total algorithm runs in time at most O(m3). The following proposition shows that AT-models over Z/p,pbeing any prime, can also be computed using Algorithm 2. Proposition 4. If the output of Algorithm 2, working with coefficients in Z/p, pbeing any prime, is (C, d),H,f,g,φ,λ),then((C, d),H,λ −1f,g,λ−1φ)is an AT-model over Z/p.Furthermore,{g(h):h∈H}is a set of representative cycles of the generators of H(C;Z/p). Example 4. Consider the simplicial complex Sderived from the triangulation of the Klein bottle given in Figure 1 and the chain complex C(S) associated to S. Let C(S) be the filter of C(S) given in Example 1. Running the algorithm above, we obtain a 2-AT-model of C(S), (C(S),H S,f S,g S,φ S,2), where HS={a, ac}. The value of fSon each vertex of Sis 2a.ThevalueoffSon each edge marked inredinFigure1,is2ac.ThevalueoffSon the rest of the simplices of Sis zero. For the map gS, we obtain that gS(a)=aand gS(ac)=ac −bc −ab.On each vertex of S,φSgives a path connecting this vertex with a, multiplied by 2; for example, φS(g)=2(ab +bc +cg). On the edges of S, the key idea is the same, that is, on each edge of S,φSgives a “path” connecting this edge with ac, multiplied by 2; for example, φS(gh)=2(fgh−cfg +bcf +abf). On each triangle of S,thevalueofφSis zero. Summing up, given a filter Cof a chain complex C, it is possible to compute a λ- AT-model, λAT =(C, d),H,f,g,φ,λ), in O(m3)ifChas melements. The Betti numbers and a set of independent non-boundary cycles of Cover Zcan directly be obtained from λAT . Moreover, the integer λprovides the prime numbers involved in the invariant factors of the torsion subgroup of H(C;Z). This last information will be essential in the next section for designing an algorithm for computing “moduli” representative cycles of the generators of the free and the torsion subgroups of H(C;Z). 4 Computing Integer Homology Information As we have said before, a λ-AT-model for a given chain complex Cprovides information of the free subgroup of H(C;Z) as well as the prime numbers involved in the invariant factors of H(C;Z). For obtaining “moduli” representative cycles of the generators of the free and the torsion subgroups of H(C;Z)weonlyhave to compute AT-models for Cover Z/p,foreachprimepdividing λ.Observe that for this last task, since we work with coefficients in Z/p, we can use either Algorithm 1 or Algorithm 2. Algorithm 4. Computing integer homology information and “moduli” representative cycles of homology generators of a chain complex C. 338 R. Gonzalez-Diaz et al. Input: a filter C={a0,...,a m}of the chain complex Cof dim n, and the matrix of the differential dfor the basis C. Apply Algorithm 2 with coefficients in Zfor computing a λ-AT-model for (C, d),((C, d),H,f,g,φ,λ); βq:= number of elements of Hof dim q, for q=0 to n; G:= {g(h): h∈H}. For each prime pdividing λdo Apply Algorithm 2 with coefficients in Z/p for computing an AT-model for Cover Z/p,((C, dp),H p,f p,g p,φ p); T(0,p)=β(0,p)−β0; T(q,p)=β(q,p)−βq−T(q−1,p), for q=1 to n; Gp={gp(hp): hp∈Hp}. Output: The sets G,{Gp:pbeing a prime dividing λ},{β1,...,β n}, and {T(q,p):0≤q≤nand pbeing a prime dividing λ}. Summing up, after computing a λ-AT-model and an AT-model over Z/p,for each pdividing λ, for a given chain complex C, we obtain: –the Betti numbers βqfor 0 ≤q≤n,andasetGof independent nonboundary cycles of Cover Z(in fact, Gis also a set of generators of H(C;Q)); –the prime numbers pinvolved in the invariant factors corresponding to the torsion subgroup of H(C,Z), the amount of invariant factors in each dimension qthat are a power of p,T(q,p),andasetGpof representative cycles of the generators of H(C;Z/p)foreachprimepdividing λ. Example 5. In Example 1, we applied the Algorithm 2 and computed a 2-AT- model for C(S) and the Betti numbers of C;β0=1,β1=1andβ2=0.Now,we apply Algorithm 2 for compute an AT-model for (C, d) with coefficients in Z/2 to obtain ((C, d)),H 2,f 2,g 2,φ 2)whereH2={a, ac, de, adi}. Then, β(0,2) =1, β(1,2) =2,β(2,2) =1andG2={a, ac +bc +ab, ad +de +ae, adf +abf +bcf + cfg+acg+aeg+def +efh+fgh+ghi+egi+dei+aeh+abh+bhi+bci+aci+adi}. Therefore, t(0,2) =0,t(1,2) =1andt(2,2) = 0. We conclude that H0(S)=Zand H1(S)=Z⊕Z/2. 5 Conclusions and Future Work Aλ-AT-model for a chain complex Ccan be computed in cubic time. It provides information of the free subgroup of H(C;Z)andalsotheprimespthat are candidates to be involved in an invariant factor of H(C;Z). For obtaining the amount of invariant factors that are a power of pand “moduli” representative cycles of homology generators, we compute an AT-model with coefficients in Z/p for such primes p. A future work is to study if it is possible to obtain generators with integer coefficients of the torsion subgroup of H(C;Z). Another task is to study if cohomology features can be computed over Zfrom a λ-AT-model. Concerning to the complexity, Algorithm 4 runs in time O(m3ψ(λ)) in the worst case, ψbeing the Euler function. Therefore, one important question is to