Computation of cubical homology, cohomology, and (co)homological operations via chain contraction

Computation of cubical homology, cohomology, and (co)homological operations via chain contraction Paweł Pilarczyk · Pedro Real Abstract We introduce algorithms for the computation of homology, cohomology, and related operations on cubical cell complexes, using the technique based on a chain contraction from the original chain complex to a reduced one that represents its homology. This work is based on previous results for simplicial complexes, and uses Serre’s diagonalization for cubical cells. An implementation in C++ of the intro-duced algorithms is available at http://www.pawelpilarczyk.com/chaincon/ together with some examples. The paper is self-contained as much as possible, and is written at a very elementary level, so that basic knowledge of algebraic topology should be sufficient to follow it. Keywords Algorithm · Software · Homology · Cohomology · Computational homology · Cup product · Alexander-Whitney coproduct · Chain homotopy · Chain contraction · Cubical complex Mathematics Subject Classification (2010) 55N35 · 52B99 · 55U15 · 55U30 · 55-04 Communicated by: D. N. Arnold P. Pilarczyk () Universidade do Minho, Centro de Matema´tica, Campus de Gualtar, 4710-057 Braga, Portugal e-mail: [email protected] URL: http://www.pawelpilarczyk.com/ P. Real Departamento de Matem´aticaAplicadaI,E.T. S.de Ingenierı´a Inform´atica, Universidad de Sevilla, Avenida Reina Mercedes s/n, 41012 Sevilla, Spain e-mail: [email protected] URL: http://investigacion.us.es/sisius/sis showpub.php?idpers=1021 Present Address: P. Pilarczyk IST Austria, Am Campus 1, 3400 Klosterneuburg, Austria 254 P. Pilarczyk, P. Real 1 Introduction Afull cubical set in Rnis a finite union of n-dimensional boxes of fixed size (called cubes for short) aligned with a uniform rectangular grid in Rn. Due to the product structure and alignment with coordinate axes, using full cubical sets for approximating bounded subsets of Rnis very natural: a cube containing a point x=(x1,...,x n)∈Rncan be instantly calculated by simply truncating the Cartesian coordinates of xdown to the nearest grid thresholds. For simplicity of notation, these thresholds can be set to the integers, so that the cubes are of unitary size. Such cubical sets naturally correspond to 2D and 3D binary images. By analogy to simplicial complexes (see e.g. [44]), sets of cubes with their vertices, edges, faces, etc., yield a natural chain complex structure, which can be used to compute their homology groups. We refer to [34] for a comprehensive study of this subject, and to the [9]andthe[10] for a representative implementation of homology computation algorithms focused specifically on cubical sets. Homology computation of cubical sets has already found some interesting applications. To mention a few of them, homology was used to extract topological information from medical images (e.g. [45]), to classify the complexity of patterns coming from numerical simulations of PDEs (e.g. [20]) or from physical experiments (e.g. [37]), and also in an automatized method for the computation of the Conley index from index pairs constructed as cubical sets in Rn[41,48], used e.g. in a method for editing vector fields and extraction of periodic orbits [8], and also very helpful in an automatic method for classification of dynamics in multi-parameter systems [4,7], which found applications e.g. in population biology [38] and in physics of plasmas [49]. Homology has also been proposed as a reliable criterion for thinning binary images of arbitrary dimension [46]. With the increasing use of data structures based upon cubical sets in various applications, which often require the determination of certain topological features of the sets under consideration, the importance of the development of efficient algorithms for the computation of comprehensive algebraic-topological invariants of such sets is undeniable. Our work is aimed at contributing to this field of research by providing effective algorithms for the computation of comprehensive homological information on cubical sets. A prototype software implementation of these algorithms which allows for experimenting with sample datasets is published at the project’s website [47]. In a typical approach to homology computation (see e.g. [1,44,60]), which we call the differential approach here, the matrices of the boundary homomorphisms ∂q(the differential of the chain complex) are reduced to the Smith Normal Form (SNF), from which the homology groups are determined. In the integral approach, on the other hand, in addition to the computation of the homology groups, one also constructs degree +1 homomorphisms φq:Cq→Cq+1, which record the information on a chain contraction of the entire chain complex Cto a reduced chain complex that represents its homology (see e.g. [17,55,57]). This contraction provides much more comprehensive homological information which may be important for various applications. In particular, it allows one to calculate a representative cycle for each homology class, to find the homology class of every cycle, and to compute Cubical (co)homology via chain contraction 255 the coboundary of every homologically trivial cycle (that is, find the chain csuch that c=∂cif [c]=[0]). Obviously, the computational cost of the integral approach is higher, especially because much more information needs to be stored. This additional information which is normally lost in the differential approach, however, may be essential in specific applications, e.g. for the computation of various homological or cohomological operations, as we show in Section 5. Intuitively speaking, the profound difference between the differential approach and the integral one is that the former aims at reducing the topological information to a minimal linear system that describes the degree of connectivity of the subdivided objects, while the latter provides a dense algebraic skeleton for representing these objects. Unfortunately, this latter approach is very under-represented in the literature; only some works of Sergeraert relating to effective homology (see e.g. [54]) and those regarding AT models and AM models (referred to below) emphasize this aspect of homological constructions. The integral approach was applied to the computation of the cohomology ring and some other cohomology operations in the context of simplicial complexes in [21– 24,26,50]. The philosophy behind this approach, as described in [23], is to deduce cohomology operation formulas at (co)chain level in terms of face operators on simplices, and to use the chain contractions to correctly transfer these operations to the cohomology level. In order to use this methodology in the cubical setting, the most straightforward idea would be to construct a simplicial representation of a cubical set and to apply the existing theory and algorithms to this simplicial complex. However, this induces a considerable overhead, especially in higher dimensions, not to mention the additional effort necessary to express the obtained simplicial chains in terms of cubical chains. A much more effective solution is thus to transfer the computational cohomology approach from simplicial to cubical setting. Therefore, the main aim of our work is to develop efficient (co)homology algorithms directly on the cubical structure, skipping the intermediate steps. As the main tool for this purpose, we are going to use an algebraic-topological model (AT model, see Definition 1) and an algebraic minimal model (AM model, see Definition 2). These notions have already proved useful in several publications (e.g. [6,21,24,25,42,53]). The worst-case complexity of homology computation, independent of the approach, is in general cubical if the ring of coefficients is a field, or a little higher yet polynomial otherwise, because of the need to compute the SNF of the boundary matrices (either explicitly or implicitly). Although this is too expensive for processing large datasets that appear in practical applications, various reduction techniques help decrease the size of the data considerably without loss of homological information (see e.g. [43]), and thus achieve much better performance in practice. These reduction techniques may come from geometric representation of the data, or be derived from other heuristics. As an interesting example, a physics inspired algorithm for the computation of the first cohomology group on three-dimensional complexes was introduced in [14] whose average running time was linear in their experiments, even though theoretically estimated worst-case complexity was cubical. Although several software packages that aim at (co)homology computation already exist, none of them, as far as we are aware, can be used to achieve the functionality of our approach. To name a few most prominent examples, Plex and 256 P. Pilarczyk, P. Real Dionysus are powerful projects aimed at simplicial persistent (co)homology computation, CHomP and CAPD/RedHom focus on the development of efficient homology algorithms for cubical sets using the differential approach. There are also some modules in large mathematical software packages, such as GAP or SAGE, but they all have limited capabilities and are using the differential approach. In particular, our contribution fills an important gap in the collection of publicly available homological software. Since the construction of a chain contraction has a considerable additional cost in comparison to using the differential approach (in which all this information is lost), it is obviously pointless to use the integral approach if one aims at the computation of (co)homology groups (possibly with their generators) of a cellular complex alone. The integral approach, however, provides a considerably more efficient solution in cases where the chain contraction is actually useful. For instance, if one needs to compare homology classes of various cycles that are not known a priori then using the differential approach might incur considerable cost of processing each cycle, while the integral approach provides an instant answer. In particular, comparison of effectiveness of software that uses the differential approach with software that is based upon the integral approach might be very tricky and will strongly depend on a particular application. Therefore, in order to avoid the introduction of misleading information, in this paper we purposely refrain from any speed comparison between our software and the other homology packages. In Section 2, we introduce the terminology and we carefully define all the notions to be used throughout the remainder of the paper; in particular, we define an AT model and an AM model for a finite cell complex. In Section 3, we provide explicit algorithms for the computation of AT models and AM models. In Section 4,weshow how to retrieve selected homological information from the AT models and AM models, such as (co)homology generators. In Section 5, we use this approach to compute the cup product based on formulas at chain level for cubical complexes. In Section 6, we discuss certain additional constructions and variants, like relative (co)homology or reduced (co)homology, which our machinery is capable of handling with very little additional effort. Finally, in Section 7, we briefly describe the prototype software and selected examples that have been made available at the project’s website [47], which concludes the paper. 2 Preliminaries Let Rbe a Euclidean domain (see e.g. [30], §2.15), that is, a principal ideal domain equipped with the function δR:R→Zthat assigns a non-negative integer to each element of the ring, such that for every a,b ∈R,b= 0, there exist q,r ∈Rfor which a=qb +rand δR(r) < δR(b). Intuitively speaking, we assume that Ris a commutative ring in which the dividing with remainder is a valid operation. Note that δR(k) =1 if and only if k∈Rhas its inverse in R,δR(0)=0, and δR(a) > 1 for all the non-invertible elements a∈R. In the case of the ring or integers Z, one can take δZ(k) := |k|.IfRis a field, such as the integers modulo a prime number p, denoted Cubical (co)homology via chain contraction 257 Zp(the field frequently used in homology computation, especially for p=2), or the rational numbers, Q,thenδR(k) =1 for all k= 0. An interesting though rarely used in this situation example of a suitable ring might be the ring of polynomials in one variable, with δRcorresponding to the degree of the polynomial increased by 1 and δR(0):= 0. Achain complex (see e.g. [44]) is a graded free abelian group {Cq}q∈Zwith a degree −1 homomorphism ∂q:Cq→Cq−1such that ∂∂ =0, called the boundary operator or the differential of the chain complex. Such a complex arises naturally from a cell complex structure, where each Cqis a free abelian group whose generators correspond to q-dimensional cells, and for each q-dimensional cell c,∂q(c) is a linear combination of (q −1)-dimensional cells in the boundary of cwith the coefficients reflecting incidence numbers and orientation. Thanks to the requirement that ∂∂ =0, the group of boundaries B:= im ∂is a subgroup of the group of cycles Z:= ker ∂, and thus the homology group H:= Z/B is well defined; since it is an invariant of the topological space (polyhedron) which is the union of all the cells in the complex, it is also called the homology of the topological space. The homology class of a chain a∈Cqis denoted by [a]. Let Kbe an n-dimensional cell complex, also called a CW complex; see e.g. [27, Ch. 0] for the definition. Denote the set of its q-dimensional cells by K(q). Throughout the entire paper, we shall assume that the number of cells in the complex is finite. The corresponding chain complex (Cq(K), ∂q)q∈Zover Rconsists of the free R-modules of q-chains Cq, whose elements are formal combinations of the cells in K(q) with coefficients in R, and a family of homomorphisms ∂q:Cq→Cq−1 such that ∂q−1◦∂q=0and∂q(σ) is a combination of (q −1)-dimensional cells that appear in the boundary of σwith coefficients corresponding to the orientation and multiplicity of these cells (we shall provide explicit formulas in the case of a simplicial complex and a cubical complex below). Note that Cq(K) =0 whenever q<0orq>n.IfR=Zthen each Cqis a free abelian group. If Ris a field then each Cqis a vector space over R. Since we assume that the number of cells in Kis finite, all the R-modules under consideration are finitely generated. On each Cq,we define a bilinear form Cq×Cq(c, c)→c, c∈Ron each pair of generators σ, τ ∈K(q) of Cqas follows: σ, τ:=1ifσ=τand σ, τ:=0 otherwise. This bilinear form is a frequently used formal construct for extracting the coefficient that appears in a chain at a given cell (see e.g. [34]). As for the actual formula for the boundary operator ∂, the case of a simplicial complex is well established (see e.g. [27]). If a simplex of dimension q>0 is identified by the (q +1)-tuple of its (pairwise different) vertices, that is, σ=(v0,...,vq),then ∂q(σ) =(−1)i(v0,...,ˆvi,...,vq), where the hat over vimeans that viis omitted in the q-tuple, and ∂q=0ifq≤0orq>n. The case of a cubical complex is less typical, so we recall some definitions in order to avoid any ambiguity. The reader is referred to [34] for a comprehensive introduction; we also follow some notation from [56]. An elementary interval is an interval of the form [k, k +1](the non-degenerate case) or a set {k}, also denoted as the interval [k,k]or even [k](the degenerate case), where k∈Z.Anelementary cube in Rnis the Cartesian product of nelementary intervals, and the number of non-degenerate intervals in this product is its dimension. 258 P. Pilarczyk, P. Real Let σ=I1×···×Inbe an elementary cube in Rn,whereIj=a0 j,a1 jpossibly a0 j=a1 j.Letk1,...,k qdenote those indices that correspond to non-degenerate intervals Ikj=[a0 kj,a1 kj]in σ(qis the dimension of σ). For a set J⊂{1,...,q}, let Jdenote the complement of Jin {1,...,q}. Define k(J) := {ki:i∈J},and for i∈{0,1}define the elementary cube λi Jσ:= I 1×···×I n,whereI j=ai jif j∈k(J) or I j=Ijotherwise. If card J=1, we shall write λi jinstead of λi {j}.Then define the boundary of σas follows (see [56], p. 440 in the context of singular cubes): ∂q(σ) := q  j=1 (−1)jλ0 jσ−λ1 jσ. The homology module of a finite cell complex is a finitely generated module over R, and the classification theorem of finitely generated modules over a p.i.d. (see e.g. [30], §3.9) implies that its description is rather simple: It is a direct sum of its torsion submodule and its free submodule, where the former is a direct sum of primary cyclic modules, and both are finitely generated. Therefore, the homology module Hq(K)q∈Zis characterized by the ranks of the free submodules for each Hq(K), each called the q-th Betti number and denoted βq(K), respectively, and the torsion coefficients, which describe the torsion submodules of each Hq(K). Intuitively speaking, homology groups provide information about different kinds of holes in the space. Namely, β0corresponds to the number of connected components (see also the note on reduced homology in Section 6), β1is the number of linearly independent holes (like the one inside a circle), β2counts the number of voids (like the one surrounded by a sphere), and in general βqcorresponds to the number of defects of the space that look like the hollow space inside the q-dimensional unitary sphere in Rq+1. See the figures and discussion in Section 7for some examples of topological spaces and their homology groups. Dual concepts lead to the definition of cohomology of a cell complex K,as follows. The cochain complex (Cq(K), δq)q∈Zof Kover Rconsists of homomorphisms from Cqto R,Cq(K) := Hom(Cq(K);R).Thecoboundary operator,as the dual to ∂, is given by the formula δq(c)(a) := c∂q+1(a)for c∈Cq(K) and a∈Cq+1(K). A cochain a∈Cq(K) is called a q-cocycle if δq(a) =0. If a=δq−1(a)for some a∈Cq−1(K) then ais called a q-coboundary.The q-th cohomology module Hq(K) of Kis the quotient module of q-cocycles and qcoboundaries. The cohomology class of a cochain a∈Cq(K) is denoted by [a]. Although the cohomology groups can be determined from the homology groups using the universal coefficient theorem for cohomology (see e.g. [44], § 53, p. 320), we prefer a direct approach here in order to efficiently use the additional structures necessary in the integral approach, as it will be clear in the sequel. Moreover, note that while chains can be perceived as column vectors containing coefficients of the combinations of cells in K, cochains correspond to row vectors containing coefficients of the dual cochains corresponding to single cells in K(cf. [13]). Cubical (co)homology via chain contraction 259 If C∗=Cq,∂ qand C ∗=C q,∂ qare two chain complexes then a chain map f∗:C∗→C ∗is a family of homomorphisms fq:Cq→C qq∈Zsuch that ∂ qfq=fq−1∂q.Achain contraction from C∗to C ∗is a triple (f,g,φ) of chain maps f:C∗→C ∗(projection), g:C ∗→C∗(inclusion)andφ:C∗→C∗+1(chain homotopy or integral operator) that satisfy the following conditions: (a) IdC−gf =∂φ +φ∂; (b) fg =IdC; (c) fφ =0; (d) φg =0; (e) φφ =0. This is a classical notion in homological algebra and algebraic topology; see e.g. [16, §12] and comments on the terminology and applications in [22, p. 86]. Note that because of the condition (a), if there exists a chain contraction from C∗to C ∗then their homology and cohomology modules are isomorphic. A homomorphism φ:C∗→C∗+1is called a homology gradient vector field if the following conditions hold: (a) φφ =0; (b) ∂φ∂ =∂; (c) φ∂φ =φ. A chain contraction in which φis a homology gradient vector field is called homology integral chain contraction. Definition 1 (AT model)Analgebraic-topological model (introduced in [25]), or an AT model for short, of a cell complex K, is a homology integral chain contraction from C∗(K) to some free chain complex M∗with null differential. Fig. 1 A sample cubical set Kin R2consisting of nine squares (indicated in gray), two additional 1- dimensional segments ([3,4]×[0]and [4]×[0,1]) and an isolated point ([4]×[3]). Its homology groups over Z2are: H0∼ =Z2⊕Z2,H1∼ =Z2⊕Z2,andHqis trivial for q/∈{0,1}. Indeed, the set consists of two connected components and has two holes 260 P. Pilarczyk, P. Real Fig. 2 An AT model (see Definition 1) of the cubical set Kshown in Fig. 1computed with Algorithm 1 (see Section 3). Representants of the four homology generators are: a1=[4]×[3],a2=[0]×[1], b1=[3,4]×[0]and b2=[0]×[0,1]. These cells correspond to a basis of M∗. Their images by the inclusion gare homology generators of C(K):g(a1)=a1,g(a2)=a2,g(b1)is the loop around the entire gray area, indicated in the figure with a thick line (red online), and g(b2)is the boundary of the missing square in the lower right corner, indicated in the figure with another thick line (green online) The complex M∗in an AT model of Kis isomorphic to the homology module of K. An AT model exists for a cell complex if and only if its homology is torsion-free (e.g. if Ris a field), and any two AT models of the same complex are isomorphic. Figures 1,2and 3show an example of a cubical complex, its AT model, and a sample application of the AT model to the computation of the coboundary of a homologically trivial cycle. This example is included in the software package available from the project’s website [47], and the results shown here were actually obtained by the software. In fact, given an integral operator φon C∗(K), that is, a homomorphism φ:C∗(K) →C∗+1(K) satisfying φφ =0, it is possible to algebraically determine the other components of the chain contraction (see e.g. [26,52,53]); however, Fig. 3 Sample computation of a coboundary of a homologically trivial cycle, using the integral operator φ computed as part of the AT model of K(shown in Figs. 1and 2). Consider the cycle c=c1+c2+c3+c4, indicated with thick lines in the figure, with c1=[1,2]×[0](green online), c2=[2]×[0,1](pink online), c3=[1,2]×[1](gray), and c4=[1]×[0,1](blue online). The integral operator applied to these cells is as follows: φ(c1)=0, not shown in the figure, φ(c2)=[2,3]×[0,1]+[2,3]×[1,2]+[3,4]×[1,2], the three squares shaded in dark gray (in print) or in dark pink (online),φ(c3)=0, not shown, and φ(c4)=[1,2]×[0,1]+[2,3]×[0,1]+[2,3]×[1,2]+[3,4]×[1,2], the four squares indicated with dashes. As a consequence, φ(c) =c,wherec=[1,2]×[0,1]. One can check that indeed ∂c=c(note the field Z2of coefficients) Cubical (co)homology via chain contraction 261 direct construction of M∗and the chain contraction of C∗(K) to M∗(provided in Algorithm 1) makes it easier to obtain explicit representations of homology and cohomology generators (as we show in Section 4). Definition 2 (AM model)Analgebraic minimal model (introduced in [22]), or an AM model for short, of a cell complex Kis a chain contraction from C∗(K) to a chain complex (M, d) such that each Mqis a free R-module and all the non-zero elements in the SNF of each dqare non-invertible in R. An AM model exists for every cell complex, and any two AM models for the same complex are isomorphic. Moreover, an AM model of a complex Kis isomorphic to an AT model of Kif the latter exists. AT models and AM models are the main tools in our approach to computing comprehensive homological information for cell complexes. 3 Algorithms for the computation of chain contractions Given a cell complex, the following algorithm constructs another complex that represents its homology and computes a homology integral chain contraction of the original cell complex to the new one. It is based on the incremental homology computation algorithm [11,12], and in its original form was introduced in [25]. Below, we provide this algorithm, rewritten in a detailed way so that the chain maps are defined with respect to the original basis in Kand an explicitly constructed set of generators of M∗, which is crucial for effective implementation and for applications. The input of the algorithm consists of the list of all the cells of a cell complex Kordered as a filter (c0,...,c m−1), that is, for each i=0,...,m −1, the set {c0,...,c i}forms a valid cell complex. In other words, all the cells that appear in the boundary of each cell must precede the cell in the list. A simple filter may be created by sorting the cells in Kby their dimension in the ascending order. We assume that a formula for the boundary of each cell is given as a combination of lower-dimensional cells. In order to be consistent with the software implementation, we choose the convention of the C++ programming language to index sequences starting from 0. In order to emphasize the meaning of the components of the chain contraction (f,g,φ)being constructed, we denote the projection fby πand the inclusion gby ιin the algorithm. The maps πand φare defined on generators of their domains, and we transparently use them as homomorphisms. The chain complex M∗with the differential d=0 is represented by means of the set of generators Mcorresponding to selected cells from K, with their dimension qcorresponding to the level qof Mq. We use the subscript index ito indicate the objects constructed at each run of the main loop, but in the software implementation only one instance of these objects exists, and is modified during the computations, so that upon completion of each loop, the previous instance is replaced with the new one. 268 P. Pilarczyk, P. Real Let (f,g,φ,M ∗,d)be an AM model of a cell complex K, or an AT model of K if d=0. Then the cup product of two cochains c:Mi→Rand c:Mj→Ris a cochain cc :Mi+j→Rgiven by the following formula: (c  c)(σi+j)=(μ ◦(c ⊗c)◦(f ⊗f)◦AW ◦g)(σi+j), where σi+j∈Mi+j,μ:R×R→Ris the multiplication in R,and⊗denotes the tensor product of homomorphisms defined as follows: (h1⊗h2)(x1⊗x2)= h1(x1)⊗h2(x2). An equivalent recursive formula for the cubical cup product (1) was also derived in [35](seealso[32]) in an explicit way in the context of cubical sets as in [34], with [44] as a theoretical basis. The key idea of that construction was to see the cup product in cohomology as a map induced by the composition of two chain maps (see [27, Chapter 3] and [39, Chapter XIII, §3]): Ck(K) ⊗Cl(K) →Ck+l(K ×K) →Ck+l(K), where the first map is the cross product of cochains, defined on the chains corresponding to elementary cubes Qk 1×Ql 2⊂Rk+lby the formula ck 1×cl 2Qk 1×Ql 2=ck 1Qk 1·cl 2Ql 2, and the second map is induced by the diagonal map Kx→ (x) =(x, x) ∈K×K. (The majority of [35]isdevoted to determining the chain map corresponding to .) This formula can also be derived by means of simplicial subdivision, using the notion of simplicial sets [40]. A simplicial set is a graded set X={Xk}k≥0endowed with two kinds of operators: face operators ∂X i:Xk→Xk−1(for i=1,...,k), and degeneracy operators sX i:Xk→Xk+1(for i=0,...,k); see [40]forthe conditions that these operators must satisfy. Elements of Xare called simplices. In case of “classical” simplices, these two operators are given by the following formulas: ∂X i(v0,...,v k)=(v0,...,v i−1,v i+1,...,v k),andsX i(v0,...,v k)= (v0,...,v i−1,v i,v i,v i+1,...,v k).Asimplexx∈Xis called degenerate if x= sX i(y) for some iand some y∈X. The graded module generated by the degenerate simplices of Xis denoted by s(C∗(X)). The normalized chain complex CN ∗(X) is the quotient CN ∗(X) =(C∗(X)/s(C∗(X)), ∂),where∂=(−1)i∂X i. Cartesian product S×Tof two simplicial sets is also a simplicial set with (S ×T) k={(x, y) :x∈ Sk,y∈Tk}, the face operators ∂S×T i(x, y) =(∂S i(x), ∂T i(y)), and the degeneracy operators sS×T i(x, y) =(sS i(x), sT i(y)). An interval I=[a,b]can be obviously considered a simplicial set SI={SI k}k≥0. An elementary cube σ=I1×···×Inin Rn,whereIj=[a0 j,a1 j](possibly a0 j=a1 j), is the Cartesian product of the intervals, each of which can also be considered a simplicial set. Therefore, the cube σcan be considered both as the simplicial set Ks and a cubical set Kc. The cubical chain complex C∗(Kc)is isomorphic to the tensor product jCN ∗(Ij). The homological equivalence of the chain complexes CN ∗(Ks) and C∗(Kc)is given by the chain contraction cez =(fez,g ez,φ ez)from the chain complex CN ∗(Ks)of the Cartesian product of Ijto the tensor product C∗(Kc).In classical algebraic topology, the chain contraction cez is called an Eilenberg-Zilber chain contraction, and an explicit formulation is given [51, p. 56] (see also [18]). The Alexander-Whitney coproduct AW:CN ∗(X) →CN ∗(X) ⊗CN ∗(X) is defined on a Cubical (co)homology via chain contraction 269 simplicial set by AW(x) =∂X 0∂X 1...∂X i−1(x)⊗∂X i+1...∂X n(x). The chain contraction cez can be used to transfer the simplicial Alexander-Whitney coproduct to the cubical context: AWc=(fez ⊗fez)◦AWs◦gez. The Alexander-Whitney coproduct can then be translated to cup product at cochain level by duality: (c  c)(σi+j)=(μ ◦(c ⊗c)◦AWc)(σi+j), where cand care cubical cochains of degree iand j, respectively, σi+jis a cubical chain of degree i+j,andμ:R×R→Ris the multiplication in R. Instead of delving into further technical details, we shall describe this construction in the case of a 2-dimensional cube. The cubical set Kc=Kc 0,Kc 1,Kc 2 corresponding to the 2-dimensional elementary cube σ=[a, b]×[c, d]is given by Kc 0={(a, c), (a, d), (b, c), (b, d)}, Kc 1={[a, b]×{c},[a,b]×{d},{a}×[c, d],{b}×[c, d]}, Kc 2={[a, b]×[c, d]}. The simplicial set Ks=Ks 0,Ks 1,Ks 2has the following non-degenerate cells: Ks 0={(a, c), (a, d), (b, c), (b, d)}, Ks 1={(aa,cd), (ab,cc), (ab,cd), (ab,dd), (bb,cd)}, Ks 2={(abb, ccd), (aab, cdd)}. The chain homotopy operator φez :CN ∗(Ks)→CN ∗+1(Ks)helps get rid of the diagonal cell, and is defined as follows: φez(x) =−(aab,cdd) if x=(ab, cd) and φez(x) =0 otherwise. The Alexander-Whitney coproduct of a 2-dimensional simplex is given by AWs(w1,w 2,w 3)=−(w1)⊗(w1,w 2,w 3)+(w1,w 2)⊗(w2,w 3)−(w1,w 2,w 3)⊗(w3). Using cez, we obtain the following: AWc([a,b]×[c, d])=({a}×{c})⊗([a,b]×[c, d])+([a,b]×{c})⊗({b}×[c, d])+ −({a}×[c, d])⊗([a,b]×{d})+([a,b]×[c, d])⊗({b}×{d}) We remark that the ring structure introduced by the cup product allows to distinguish some topological spaces which have isomorphic cohomology but different homotopy type. We discuss a few such examples in Section 7. However, the problem of verification whether two rings are isomorphic or not, by means of checking their multiplication tables, is in general a nontrivial one. Therefore, from the practical point of view it is much more efficient to use another invariant which can be derived from the cup product, for example, the homology of the so-called reduced bar construction, which is a classical algebraic invariant in algebraic topology. Since the details are beyond the scope of this paper, we refer the interested readers to [2,3,28]. A version of the invariant called HB1specific for 3D digital images and derived from this construction was introduced in [24]. 270 P. Pilarczyk, P. Real 6 Additional constructions and variants Small modifications in the computational machinery introduced above allow for easy implementation of additional useful features, which we discuss in this section. All these features are implemented in the software provided at the project’s website [47]. Relative (co)homology If Kis a cellular complex and Lis its subcomplex (that is, a subset of cells which is a complex itself) then relative (co)homology of the pair (K, L) is the (co)homology of the quotient chain complex C(K)/C(L).From the algorithmic point of view, relative (co)homology can be computed as plain (co)homology of the cellular complex K\L, in which the cells in Lare removed from the boundary of each cell c∈K\L. Reduced (co)homology If we additionally consider the empty cell eas a valid cell of dimension −1, and we put ∂0(σ ) := efor every 0-dimensional cell σ, then we obtain the augmented chain complex with C−1=R, and its (co)homology is called reduced (co)homology. The nice feature of this variant is that the geometric interpretation of reduced homology is more consistent. While the dimension of each homology vector space over a field can be interpreted as the number of “holes” in all dimensions except 0, where it corresponds to the number of connected components of the space, the same interpretation is valid for reduced homology also at level 0, where 0-dimensional “holes” can be interpreted as “gaps” between the connected components. As a consequence, the reduced (co)homology of a “trivial” space, that is, a topological space that is contractible, is zero. Periodic boundary conditions In various applications, one often imposes periodic boundary conditions in certain directions of a Euclidean space, which corresponds to taking some coordinates from the quotient space R/kZ≃S1,wherek∈Z, k>0. A modification of the definition of cubes and cubical sets for such a space is straightforward, and helps defining certain topological spaces much more easily. For instance, the torus can be viewed as the cubical set [0,k]×[0,l]in the space (R/kZ)×(R/lZ),wherek,l are arbitrary positive integers. Fig. 4 Three 2-dimensional compact manifolds with the same (co)homology groups over Z2but distinguishable using Alexander-Whitney coproduct in homology (see Table 1) or the cup product in cohomology. From left to right: the torus, the wedge of the sphere and two circles, and the Klein bottle Cubical (co)homology via chain contraction 271 Fig. 5 Cubical approximations of two different configurations of three tori, available in the Voxelo software package, http://munkres.us.es:8080/groups/catam/wiki/e33d2/ (called Toro A and Toro B). The (co)homology groups of both topological spaces are the same, but the Alexander-Whitney coproduct in homology or the cup product in cohomology can distinguish them (see Table 1) 7 Software and examples A prototype implementation of Algorithms 1 and 2 together with some illustrative examples are provided at the project’s website [47]. The core part of the software is a C++ programming library that defines templates for Algorithms 1 and 2, as well as related data structures and algorithms. The type of cells and the type of coefficients are parameters of the templates, and the algorithms are designed in such a way that they apply to arbitrary types which satisfy the necessary mathematical assumptions. The auxiliary data structures include filtered Table 1 Results of computations for selected examples Topological Homology groups Alexander-Whitney coproduct of 2D homology generators, space example over Z2restricted to 1-dimensional chains Torus (Z2,Z2⊕Z2,Z2)AW(c1)=b1⊗b2+b2⊗b1 S2∧S1∧S1(Z2,Z2⊕Z2,Z2)AW(c1)=0 Klein bottle (Z2,Z2⊕Z2,Z2)AW(c1)=b1⊗b2+b2⊗b1+b2⊗b2 Projective plane (Z2,Z2,Z2)AW(c1)=b1⊗b1 S2∧S1(Z2,Z2,Z2)AW(c1)=0 Three tori (A) (Z2,Z4 2,Z3 2)AW(c1)=b3⊗b4+b4⊗b3 AW(c2)=b3⊗b4+b4⊗b3+b1⊗b2+b2⊗b1 AW(c3)=b3⊗b4+b4⊗b3 Three tori (B) (Z2,Z4 2,Z3 2)AW(c1)=b2⊗b3+b3⊗b2+b3⊗b4+b4⊗b3 AW(c2)=b1⊗b3+b3⊗b1+b2⊗b3+b3⊗b2 AW(c3)=b3⊗b4+b4⊗b3 The torus, the wedge of the sphere and two circles, the Klein bottle, see Fig. 4(note that these three objects have isomorphic homology over Z2, but the Alexander-Whitney coproduct allows to distinguish them); the real projective plane, the wedge of the sphere and the circle (again, the same homology, but different Alexander-Whitney coproduct), and two combinations of three tori embedded in R3illustrated in Fig. 5 that can be distinguished by the Alexander-Whitney coproduct 272 P. Pilarczyk, P. Real complexes, chains, linear maps, and tensor products of chains. A special combinatorial version is provided for Z2coefficients; its advantage is that chains correspond to collections of cells, without the need for storing the coefficients. Definitions of cubical cells and simplices are included as sample types of cells, and the rings Zand Zp (where pis a prime number) are also implemented, but other types of cells or rings of coefficients can be also easily added by the users. In order to simplify using the software, several utility programs are included in the package, which read input data from text files and output the results to the screen in human-readable format. These programs are interfaces to the main features of the C++ software library, and are provided in order to make it easy to try this software; however, using the C++ library interface directly is recommended for intensive applications, as it is much more efficient. The examples include the well known Klein bottle defined as a simplicial complex, as a surface built of 2-dimensional cubical cells (squares) embedded in R4,and also as a full cubical set in R4. There is also the torus and the wedge of a sphere with two circles (see Fig. 4). Note that these three spaces have the same (co)homology groups over Z2, but can be distinguished with the Alexander-Whitney coproduct (see Table 1) or with the cup product. Another example consists of two different configurations of three tori (see Fig. 5) discussed in [5] (note the wrong result for the Alexander-Whitney coproduct provided there), which also cannot be distinguished by computing (co)homology alone. Results of computations for these and two more examples are gathered in Table 1. Acknowledgements This research was partially supported from Fundo Europeu de Desenvolvimento Regional (FEDER) through COMPETE – Programa Operacional Factores de Competitividade (POFC) and from the Portuguese national funds through Fundac¸˜aoparaaCiˆencia e a Tecnologia (FCT) in the framework of the research project FCOMP-01-0124-FEDER-010645 (ref. FCT PTDC/MAT/098871/2008), as well as from the funds distributed through the European Science Foundation (ESF) Research Networking Programme on “Applied and Computational Algebraic Topology” (ACAT). P. Real was additionally supported by the Spanish Ministry of Science and Innovation, project no. MTM2009-12716. References 1. Agoston, M.K.: Algebraic Topology, A First Course, Monographs and Textbooks in Pure and Applied Mathematics, vol. 32. Marcel Dekker, New York (1976) 2. ´ Alvarez, V., Armario, J.A., Frau, M.D., Gonz´alez-D´ıaz, R., Jim´enez, M.J., Real, P., Silva, B.: Computing “small” 1-homological models for commutative differential graded algebras. In: Ganzha, V., Mayr, E., Vorozhtsov, E. (eds.) Computer Algebra in Scientific Computing, pp. 87–100. Springer, Berlin (2000). doi:10.1007/978-3-642-57201-2 9 3. ´ Alvarez, V., Armario, J., Frau, M., Real, P.: Comparison maps for relatively free resolutions. In: Ganzha, V.G., Mayr, E.W., Vorozhtsov, E.V. (eds.) Computer Algebra in Scientific Computing, Lecture Notes in Computer Science, vol. 4194, pp. 1–22. Springer-Berlin, Heidelberg (2006). doi:10.1007/11870814 1 4. Arai, Z., Kalies, W., Kokubu, H., Mischaikow, K., Oka, H., Pilarczyk, P.: A database schema for the analysis of global dynamics of multiparameter systems. SIAM J. Appl. Dyn. Syst. 8(3), 757–789 (2009). doi:10.1137/080734935 5. Berciano, A., Molina-Abril, H., Pacheco, A., Pilarczyk, P., Real, P.: Decomposing cavities in digital volumes into products of cycles. In: Brlek, S., Reutenauer, C., Provenc¸al, X. (eds.) Discrete Geometry for Computer Imagery, Lecture Notes in Computer Science, vol. 5810, pp. 263–274. Springer-Berlin, Heidelberg (2009). doi:10.1007/978-3-642-04397-0 23 Cubical (co)homology via chain contraction 273 6. Berciano, A., Molina-Abril, H., Real, P.: Searching high order invariants in computer imagery. AAECC 23(1–2), 17–28 (2012). doi:10.1007/s00200-012-0169-5 7. Bush, J., Gameiro, M., Harker, S., Kokubu, H., Mischaikow, K., Obayashi, I., Pilarczyk, P.: Combinatorial-topological framework for the analysis of global dynamics. Chaos: An Interdisc. J. Nonlinear Sci. 22(4), 047508 (2012). doi:10.1063/1.4767672 8. Chen, G., Mischaikow, K., Laramee, R.S., Pilarczyk, P., Zhang, E.: Vector field editing and periodic orbit extraction using morse decomposition. IEEE Trans. Vis. Comput. Graph. 13(4), 769–785 (2007). doi:10.1109/TVCG.2007.1021 9. Computational Homology Project (CHomP) software: http://chomp.rutgers.edu/software/ (2013) 10. Computer Assisted Proofs in Dynamics (CAPD) group: http://capd.ii.uj.edu.pl/ (2013) 11. Delfinado C.J.A., Edelsbrunner H.: An incremental algorithm for Betti numbers of simplicial complexes. In: Proceedings of the Ninth Annual Symposium on Computational Geometry, pp. 232–239. ACM, New York, SCG ’93 (1993), doi:10.1145/160985.161140 12. Delfinado, C.J.A., Edelsbrunner, H.: An incremental algorithm for Betti numbers of simplicial complexes on the 3-sphere, grid generation, finite elements, and geometric design. Comput. Aid. Geom. Des. 12(7), 771–784 (1995). doi:10.1016/0167-8396(95)00016-Y 13. Desbrun, M., Kanso, E., Tong, Y.: Discrete differential forms for computational sciences. In: Discrete Differential Geometry, Course Notes, ACM SIGGRAPH (2006) 14. Dłotko, P., Specogna, R.: Physics inspired algorithms for (co)homology computations of threedimensional combinatorial manifolds with boundary. Comput. Phys. Commun. 184(10), 2257–2266 (2013). doi:10.1016/j.cpc.2013.05.006 15. Dumas, J.G., Saunders, B.D., Villard, G.: On efficient sparse integer matrix Smith normal form computations. J. Symb. Comput. 32(1–2), 71–99 (2001). doi:10.1006/jsco.2001.0451 16. Eilenberg, S., Mac Lane, S.: On the groups H(,n), I. Ann. Math. 58, 55–106 (1953) 17. Eilenberg, S., Mac Lane, S.: On the groups H(,n), II: Methods of computation. Ann. Math. 60, 49–139 (1954) 18. Eilenberg, S., Zilber, J.: On products of complexes. Am. J. Math. 75, 200–204 (1953) 19. Forman, R.: Morse theory for cell complexes. Adv. Math. 134(1), 90–145 (1998). doi:10.1006/aima.1997.1650 20. Gameiro, M., Mischaikow, K., Kalies, W.: Topological characterization of spatial-temporal chaos. Phys. Rev. E 70, 035,203 (2004) 21. Gonz´alez-D´ıaz, R., Real, P.: A combinatorial method for computing Steenrod squares. J. Pure Appl. Algebra 139(1–3), 89–108 (1999). doi:10.1016/S0022-4049(99)00006-7 22. Gonz´alez-D´ıaz, R., Real, P.: Computation of cohomology operations on finite simplicial complexes. Homology, Homotopy Appl. 5(2), 83–93 (2003) 23. Gonz´alez-D´ıaz, R., Real, P.: HPT and cocyclic operations. Homology, Homotopy Appl. 7(2), 95–108 (2005a) 24. Gonz´alez-D´ıaz, R., Real, P.: On the cohomology of 3D digital images. Advances in Discrete Geometry and Topology. Discret. Appl. Math. 147(2–3), 245–263 (2005b). doi:10.1016/j.dam.2004.09.014 25. Gonz´alez-D´ıaz, R., Medrano, B., S´anchez-Pel´aez, J., Real, P.: Simplicial perturbation techniques and effective homology. In: Ganzha, V., Mayr, E., Vorozhtsov, E. (eds.) Computer Algebra in Scientific Computing, Lecture Notes in Computer Science, vol. 4194, pp. 166–177. Springer, Berlin (2006). doi:10.1007/11870814 14 26. Gonz´alez-D´ıaz, R., Jim´enez, M., Medrano, B., Real, P.: Chain homotopies for object topological representations. International Conference on Discrete Geometry for Computer Imagery. Discret. Appl. Math. 157(3), 490–499 (2009). doi:10.1016/j.dam.2008.05.029 27. Hatcher, A.: Algebraic Topology. Cambridge University Press, Cambridge (2002) 28. Hurado, P.R., ´ Alvarez, V., Armario, J.A., Gonz´alez-D´ıaz, R.: Algorithms in algebraic topology and homological algebra: Problem of complexity. J. Math. Sci. 108, 1015–1033 (2002). doi:10.1023/A:1013544506151 29. Iliopoulos, C.S.: Worst-case complexity bounds on algorithms for computing the canonical structure of finite Abelian groups and the Hermite and Smith normal forms of an integer matrix. SIAM J. Comput. 18(4), 658–669 (1989). doi:10.1137/0218045 31. J¨ager, G., Wagner, C.: Efficient parallelizations of Hermite and Smith normal form algorithms. Parallel Comput. 35(6), 345–357 (2009). doi:10.1016/j.parco.2009.01.003 30. Jacobson, N., 2nd ed. Basic Algebra I. Dover Publications, Mineola (2009) 274 P. Pilarczyk, P. Real 32. Kaczynski, T., Mrozek, M.: The cubical cohomology ring: An algorithmic approach. Foundations of Computational Mathematics (2012). doi:10.1007/s10208-012-9138-4 33. Kaczynski, T., Mrozek, M., ´ Slusarek, M.: Homology computation by reduction of chain complexes. Comput. Math. Appl. 35(4), 59–70 (1998). doi:10.1016/S0898-1221(97)00289-7 34. Kaczynski, T., Mischaikow, K., Mrozek, M.: Computational homology, Applied Mathematical Sciences, vol. 157. Springer, New York (2004) 35. Kaczynski, T., Dłotko, P., Mrozek, M.: Computing the cubical cohomology ring. In: Gonz´alez D´ıaz, R., Real Jurado, P. (eds.): Proceedings of the 3rd International Workshop on Computational Topology in Image Context (CTIC), Research Group on Computational Topology and Applied Mathematics, University of Seville, Seville, Image A, vol. 3, pp. 137–142 (2010) 36. Kannan, R., Bachem, A.: Polynomial algorithms for computing the Smith and Hermite normal forms of an integer matrix. SIAM J. Comput. 8(4), 499–507 (1979). doi:10.1137/0208040 37. Krishan, K., Gameiro, M., Mischaikow, K., Schatz, M., Kurtuldu, H., Madruga, S.: Homology and symmetry breaking in Rayleigh-B´enard convection: Experiments and simulations. Phys. Fluids 19, 117–105 (2007) 38. Liz, E., Pilarczyk, P.: Global dynamics in a stage-structured discrete-time population model with harvesting. J. Theor. Biol. 297, 148–165 (2012). doi:10.1016/j.jtbi.2011.12.012 39. Massey, W.S.: A Basic Course in Algebraic Topology. Addison-Wesley, Menlo Park (1991) 40. May, J.P.: Simplicial objects in algebraic topology, p. 1982. The University of Chicago Press, Chicago (1967). midway reprint 41. Mischaikow, K., Mrozek, M., Pilarczyk, P.: Graph approach to the computation of the homology of continuous maps. Found. Comput. Math. 5, 199–229 (2005). doi:10.1007/s10208-004-0125-2 42. Molina-Abril, H., Real, P.: Homological spanning forest framework for 2D image analysis. Ann. Math. Artif. Intell. 64(4), 385–409 (2012). doi:10.1007/s10472-012-9297-7 43. Mrozek, M., Pilarczyk, P., ˙ Zelazna, N.: Homology algorithm based on acyclic subspace. Comput. Math. Appl. 55(11), 2395–2412 (2008). doi:10.1016/j.camwa.2007.08.044 44. Munkres, J.R.: Elements of Algebraic Topology. Addison-Wesley, Reading (1984) 45. Niethammer, M., Stein, A., Kalies, W.D., Pilarczyk, P., Mischaikow, K., Tannenbaum, A.: Analysis of blood vessel topology by cubical homology. In: Proceedings of the International Conference on Image Processing, ICIP 2002, vol. 2, pp. 969–972 (2002). doi:10.1109/ICIP.2002.1040114 46. Niethammer, M., Kalies, W., Mischaikow, K., Tannenbaum, A.: On the detection of simple points in higher dimensions using cubical homology. IEEE Trans. Image Process. 15(8), 2462–2469 (2006). doi:10.1109/TIP.2006.877309 47. Pilarczyk P.: Chain contractions. Software and examples. http://www.pawelpilarczyk.com/ chaincon/ (2013) 48. Pilarczyk, P., Stolot, K.: Excision-preserving cubical approach to the algorithmic computation of the discrete Conley index. Topol. Appl. 155(10), 1149–1162 (2008). doi:10.1016/j.topol.2008.02.003 49. Pilarczyk, P., Garc´ıa, L., Carreras, B.A., Llerena, I.: A dynamical model for plasma confinement transitions. J. Phys. A Math. Theor. 45(12), 125,502 (2012). doi:10.1088/1751-8113/45/12/125502 50. Real, P.: On the computability of the Steenrod squares. Ann Univ Ferrara, Nuova Ser, Sez VII Sc Mat 42, 57–63 (1996). doi:10.1007/BF02955020 51. Real, P.: Homological perturbation theory and associativity. Homol. Homotop. Appl. 2(5), 51–88 (2000). doi:10.1007/978-3-642-02478-8 52 52. Real, P.: Connectivity forests for homological analysis of digital volumes. In: Cabestany, J., Sandoval, F., Prieto, A., Corchado, J. (eds.) Bio-Inspired Systems: Computational and Ambient Intelligence, Lecture Notes in Computer Science, vol. 5517, pp. 415–423. Springer, Berlin (2009). doi:10.1007/978-3-642-02478-8 52 53. Real, P., Molina-Abril, H.: Cell AT-models for digital volumes. In: Torsello, A., Escolano, F., Brun, L. (eds.) Graph-Based Representations in Pattern Recognition, Lecture Notes in Computer Science, vol. 5534, pp. 314–323. Springer, Berlin (2009). doi:10.1007/978-3-642-02124-4 32 54. Sergeraert, F.: Effective homology, a survey. http://www-fourier.ujf-grenoble.fr/∼sergerar/ Papers/Survey.pdf (1992) 55. Sergeraert, F.: The computability problem in algebraic topology. Adv. Math. 104(1), 1–29 (1994). doi:10.1006/aima.1994.1018 56. Serre, J.P.: Homologie singuli`ere des espaces fibr´es. Appl. Ann. Math. 54(3), 425–505 (1951) 57. Shih, W.: Homologie des espaces fibr´es. Publ. Math. IHES 13, 5–87 (1962) Cubical (co)homology via chain contraction 275 58. Smith, H.J.S.: On systems of linear indeterminate equations and congruences. Philos. Trans. 151, 293–326 (1861) 59. Storjohann A.: Near optimal algorithms for computing Smith normal forms of integer matrices. In: Proceedings of the 1996 International Symposium on Symbolic and Algebraic Computation, pp. 267– 274. ACM, New York, NY, USA, ISSAC ’96 (1996). doi:10.1145/236869.237084 60. Veblen, O.: Analysis situs, 2nd ed., Amer. Math. Soc. Colloq. Publ., vol 5, Part 2. Amer. Math. Soc., New York (1931)