Towards optimality in discrete Morse Theory through chain homotopies

Towards Optimality in Discrete Morse Theory through Chain Homotopies ∗ Pedro Real, Helena Molina-Abril University of Sevilla, Department of Applied Mathematics, Sevilla, Spain. [email protected], [email protected] Abstract Once a discrete Morse function has been defined on a finite cell complex, information about its homology can be deduced from its critical elements. The main objective of this paper is to define optimal discrete gradient vector fields on general finite cell complexes, where optimality entails having the least number of critical elements. Our approach is to consider this problem as a homology computation question for chain complexes endowed with extra algebraic nilpotent operator. Keywords: Discrete Morse Theory, cell complex, integral-chain complex, chain homotopy, graph, homology, gradient vector field. 1 Introduction Morse theory has been considered a powerful tool in its applications to computational topology, computer graphics and geometric modeling. In [5] Forman formulates a version of this theory for discrete structures such as cell complexes. The aim of Discrete Morse Theory is to find simplicial collapses that transform Kto a smaller complex. This theory relies either on admissible functions on a cell complex, called discrete Morse functions, or equivalently their gradient vector field. Forman proved that the topology of a cell complex can be partly read out of the critical cells of a discrete gradient vector field defined on it. A gradient vector field is optimal if it has the minimum possible number of critical cells. The topological information of the initial cell complex will be concise if the discrete gradient vector field has few critical cells. In [10] the authors developed a heuristic for computing optimal Morse matchings. This heuristic computes optimal gradient vector fields for combinatorial 2–manifolds. However, for general cell complexes this problem has not been solved yet. In this paper we recover all the algebraic machinery underlying in Discrete Morse Theory, establishing a new framework for dealing with special chain complexes associated to finite cell complexes. This can be done using an essentially algebraic framework in which “homological forests” (see [11]) defined on the initial cell complex are convenient tools in order to obtain the minimum number of critical cells, that is, the minimal homological expression of the initial complex. The idea here is to classify chain homotopies as gradient vector fields on a finite cell complex. The paper is organized as follows: In Section 2 some basic definitions are introduced. The theoretical fundaments of our work is detailed in Section 3. In Section 4 the relation between this algebraic machinery and the optimality in Discrete Morse Theory are stablished. We finish the paper with some conclusions. . ∗This work has been partially supported by ”Computational Topology and Applied Mathematics” PAICYT research project FQM-296, ”Andalusian research project PO6-TIC-02268 and Spanish MEC project MTM2006- 03722 33 2 Preliminaires In this section, we introduce some basic definitions in order to understand our algebraic–topological approach. First, we establish a notion of (combinatorial) cell complex in a finite–dimensional Euclidean space with the cell boundary information described in algebraic terms. This object can be identified with the chain complex canonically associated to a cell complex such that the homology of it coincides with the singular homology of the cell complex. In fact, the geometric realization of such cell complex in a finite–dimensional Euclidean space has a representation in terms of a particular type of regular cell complex (see [9] for a deep study of cell-complexes). Simplicial, cubical and polyhedral complexes are, particular cases of cell complexes. The following definitions are necessary in order to classify chain homotopies as gradient vector fields on a finite cell complex. The ring of coefficients Λis a commutative field (for example, a finite field, the rational numbers, the real numbers,...). Let {x1,x 2, ..., xn}be a finite set of symbols. We denote by Λ[x1, . . . , xn] the module of formal linear combinations λ1x1+λ2x2+. . . λnxn, with λi∈Λ. Let "be a positive integer. Let B!={x∈E!s.t. |x|≤1) be the closed unit ball in the "-dimensional Euclidean space E!. The boundary of B!is the unit ("−1)-sphere S(!−1) and the interior of B!, denoted by Int B!, is the open unit "-dimensional ball Int B!={x∈E!s.t. |x|<1}. Ap-cell in E!(with 0 <p≤") is a subset of E!which is homeomorphic to the open unit ball Int Bp(that is, to Rp). A 0–cell is a a topological space homeomorphic to a point of a finite-dimensional Euclidean space. The dimension of a p-cell σis |σ|=pand the notation σ(p)will indicate that σis a cell of dimension p. The union as pointset of a set of cells Kin E!is called the carrier of Kand it is denoted by |K|. Let us define the boundary of a p-cell σas ∂σ =σ\σ, where σis the closure of σ. To indicate relationships between cells, we write τ>σ(or σ<τ) and we say that σis a face of τif σ%=τand σ⊂¯τ, where ¯τis the closure of τ. We write τ≥σif either τ=σor τ>σ. The star of a cell σconsists of all cells having σas a face, including σitself, and the link consists of all faces of cells in the star that are disjoint from σ. St σ={τ∈K|σ<τ} Lk σ={v∈K|v<τ∈St σ,v∩σ=∅}. Acell complex K={Ki}! i=0 embedded in E!is a finite collection of cells {σ(r)i=1,...n i∈Kr}of different dimensions 0 ≤r≤"such that: (i) |K|= n ! i=1 σi=|K0|∪|K1|∪. . . ∪|K!| . The set Krconsists of all the r-cells of K, for 0 ≤r≤". It is possible that Ki=∅for some 0 <i≤". (ii) σi∩σj=∅(i%=j); (iii) If dim(σi)=p(with 0 ≤p≤"), then ∂σi⊂"p−1 i=1 Ki, The p-skeleton K(p)for Kis the set of all k-cells with 0 ≤k≤p. The dimension of the cell complex is the smallest natural number rsuch that the condition K(r)=K(r+1) is satisfied. If all the cells of Kare convex sets of E!, then Kis called convex cell complex. Simplicial, Cubical and some polyhedral complexes are special cases of convex cell complexes. A cell complex is specified by the “face poset”, the partial order determined by the cells and its boundary relations. Roughly speaking, the idea of homology is to analyze the degree of connectivity of cell complexes using formal sums of cells. A differential operator for a cell complex Kwith coefficients in 34 Λis a linear map d:Λ[K]→Λ[K], such that the image of a p-cell σis a linear combination of some (p−1)-cells of the boundary ∂(σ) and d◦d= 0. Taking into account that our cell complex Kis embedded in E!, its geometric realization |K|is a regular triangulable cell complex and there can be always defined a differerential operator ∂, called boundary operator, with coefficients in the field Λ, that completely determines the singular homology of |K|. The chain complex canonically associated to the cell complex Kis the graded differential vector space (C∗(K),∂), where Cp(K)=Λ[Kp], for all p=0,1,...r, and ∂:C∗(K)→C∗−1(K) is the previous boundary operator for the cell complex K. For instance, to find a boundary operator ∂ for a simplicial complex is straightforward, but it is not, in general, an easy task for others cell complexes. The following is one of the fundamental results in the theory of CW-complexes. Theorem 1 (Forman).Let Ka finite cell complex. There are algebraic boundary maps ∂p: Cp(K, Λ)→Cp−1(K, Λ), for each p, so that ∂p−1◦∂p=0and such that the resulting differential complex {Cp(K, Λ),∂p}r p=0 calculates the homology of K. That is, if we define Hp(C, ∂)= Ker (∂p)/∂p+1(C). In other words, Hp(C, ∂)∼ =Hp(|K|,Λ). From now on, a finite cell complex Kwill be denoted by (K, ∂), where ∂:C∗(K)→C∗−1(K) is the boundary operator for K. 3 Algebraic Discrete Morse Theory The aim of Discrete Morse Theory is to find simplicial collapses that transform a complex Kto a smaller one. This can be done using an essentially algebraic framework in which discrete Morse functions are convenient tools to keep track of the collapses, and in which order they are done. Now, we recover all the algebraic machinery underlying in Discrete Morse Theory, establishing a new framework for dealing with special chain complexes associated to finite cell complexes and we show that a convenient combinatorial tool for solving the homological computation problem in this area is that of a tree. Definition 1. An integral chain complex (C, d, φ)is a graded module C={Cp}n p=0 endowed with two linear maps: a differential operator d:C∗→C∗−1, and an integral operator (also called algebraic gradient vector field [5] or chain homotopy operator [4]) φ:C∗→C∗+1, satisfying the global nilpotency properties d◦d=0and φ◦φ=0. An integral chain complex (C, d, φ)is d-pure (resp. φ-pure) if the condition d=d◦φ◦d, called homology condition (resp. the condition φ=φ◦d◦φ, called strong deformation retract condition) is satisfied. An integral chain complex (C, d, φ)that is both, d-pure and φ-pure, is called homology integral chain complex. Definition 2. Given two integral chain complexes (C, d, φ)and (C#,d #,φ#),amap of integral chain complexes (f, g):(C, d, φ)⇒(C#,d #,φ#)is a couple of linear maps f:C→C#and g:C#→C such that f◦d=d#◦f,g◦d#=d◦g,f◦φ=φ#◦f,g◦φ#=φ◦g.(C, d, φ)and (C#,d #,φ#) are integral chain equivalent if there exists a map of integral chain complexes (f, g), such that id C−f◦g=π(d#,φ#)and idC!−g◦f=π(d, φ). The homology H∗(C, d, φ)of an integral chain complex (C, d, φ)is the graded abelian group H∗(C), such that (H∗(C),0,0) is integral chain equivalent to (C, d, φ). The differential (resp. integral) homology of an integral chain complex (C, d, φ)is the homology of (C, d, 0) (resp. the homology of (C, 0,φ)). If (C, d, φ)is a homology integral-chain complex, then H∗(C, d, φ)∼H∗(C, d, 0) ∼H∗(C, 0,φ). The set of integral chain complexes (resp. the set of pure integral chain complexes) and their corresponding maps form a category. In fact, the integral chain equivalence relation can be seen as the natural extension of the classical chain homotopy equivalence between chain complexes to the integral case (see, for example, [4]). Effective Homology [13] is a theory in which the homology computation problem is determined in terms of an explicit chain homotopy equivalence between a chain complex (C, d) and its homology. In fact, using our terminology the effective homology of the chain complex (C, d, 0) can 35 be described as an algebraic integral operator φ, such that (C, d, φ) is integral-chain equivalent to (C, d, 0). On the other hand, Discrete Morse Theory (DMT, for short) gives a positive answer to the problem of finding combinatorial chain homotopy operators φfor chain complexes (C∗(K),d) of finite cell complexes, such that the integral homology of (C∗(K), d, φ) is a “good” approximation (measured in terms of critical cells) to its differential homology. The minimum number of critical cells in each degree is determined by the Betti numbers (weak Morse inequalities). The computation of the homology of a chain complex (C, d) is specified in terms of finding an integral operator φ:C∗→C∗+1, satisfying the Strong Deformation Retract (SDR for short) and homology conditions with regards, to the differential operator d([7, 8]). The notion of pure integral chain complex (C, d, φ) is underlying in the work of Sergeraert [13], Forman [5, 6] and that of Theory of Discrete Differential Forms [2]. Proposition 1. Let (C, d, φ)an integral chain complex. Let π:C∗→C∗be the linear map, (called flow of (C, dφ)), defined by π=idC−d◦φ−φ◦dand let ∆:(C∗,d)→C∗be the linear map, called Laplacian of (C, dφ), defined by ∆=d◦φ+φ◦d. Then, the following properties holds: (a) d◦π=d−d◦φ◦d=π◦dand φ◦π=φ−φ◦d◦φ=π◦φ. In the case of a homology integral chain complex, d◦π= 0 = π◦dand φ◦π= 0 = π◦φ. (b) d◦∆=d◦φ◦d=∆◦dand φ◦∆=φ◦d◦φ=∆◦φ. In the case of a homology integral chain complex, d◦∆=d=∆◦dand φ◦∆=φ=∆◦φ. (c) Given a p-chain a, we have the following equality a=π(a)+∆(a). (d) π2=π−φ(d−d◦φ◦d)−(d−d◦φ◦d)◦φ=π−d(φ−φ◦d◦φ)−(φ−φ◦d◦φ)d. The integral chain complex π(C, d, φ) = (π(C),d|π(C),φπ(C))is the harmonic complex associated to (C, d, φ). If (C, d, φ) is a d-pure or a φ-pure integral chain complex, then π2=π◦π=π and π(C)={x∈C|x=π(x)}. In other words, the harmonic complex (π(C),d|π(C),0) associated to a pure integral chain complex (C, d, φ) is formed by the π-equivariants chains of C. If (C, d, φ) is a homology integral chain complex, its harmonic complex is of the kind (π(C),0,0) and the chain map πdescribes for each p-chain a representative cycle of the differential (resp. integral) homology class associated to this p-chain. (e) ∆2=(d+φ)∆(d+φ). The integral chain complex ∆(C, d, φ)=(∆(C),d|∆(C),φ|∆(C)) is the Laplacian complex associated to (C, d, φ). If (C, d, φ) is a d-pure or φ-pure integral chain complex, then ∆◦∆=∆and ∆(C)={x∈C|x=∆(x)}. In other words, the Laplacian complex ∆(C, d, φ) associated to a pure integral chain complex (C, d, φ) is formed by all the ∆-equivariants chains. (f) π◦∆=(d−d◦φ◦d)◦φ+φ◦(d−d◦φ◦d)=d(φ−φ◦d◦φ)+(φ−φ◦d◦φ)d=∆π. Proposition 2. If (C, d, φ)is a (differential or integral) pure integral-chain complex, we can derive the following properties: (p1) π◦∆= 0 = ∆◦π. (p2) (C, d, φ)=π(C, d, φ)⊕∆(C, d, φ)as integral-chain complexes. In particular, Ker ∆=π(C) and ∆(C) = Ker π. (p3) ∆(C)=φ(C)⊕d◦φ)(C)as graded modules. In order to emphasize the dependency of πand ∆with regards dand φ, we will denote these maps by π(d,φ)and ∆(d,φ), respectively. The following proposition will be fundamental in developing an integral-chain framework for Discrete Morse Theory. In fact, it shows that to use pure integral operators as chain homotopies decomposing a finitely generated chain complexes is a key point: 36 Proposition 3. If (C, d, φ)is a (differential or integral) pure integral-chain complex, we have that Kerφ∼ =π(C)⊕φ(C)∼ =Ker ∆(C)⊕φ(C) as graded modules. In particular, a map of integral-chain complexes (f, g) satisfy that f◦π(d,φ)=π(d!,φ!)f,g◦ π(d!,φ!)=π(d,φ)◦g,f◦∆(d,φ)=∆(d!,φ!)◦fand g◦∆(d!,φ!)=∆(d,φ)◦g. That is, fand gare compatible with regards to the respective flows and Laplacians. In spite of its simplicity, the following result is essential for developing our homological theory of integral-chain complexes: Lemma 1. [Integral-Chain Lemma] An integral chain complex (C, d, φ)is integral-chain equivalent to its harmonic complex π(C, d, φ). This last harmonic complex π(C, d, φ)is of the form (π(C),d π,φπ)where dπ(π(x)) = (d−d◦φ◦d)(x)and φπ(π(x)) = (φ−φ◦d◦φ)(x). Proof. Let f:C→π(C) be the linear map defined by f(x)=π(x), ∀x∈C∗. Let g:π(C)→C be the linear map defined by g(x)=x,∀x∈π(C). Then, it is a simple exercice to show that (f, g) is a couple of maps of integral chain complexes which induces the integral-chain equivalence. The rest of assertions can be directly deduced from Proposition 1 (a). ! Corollary 1. The harmonic complex π(C, d, φ)associated to a d-pure (resp. φ-pure) integral-chain complex (C, d, φ)is of the form (π(C),0,φπ)(resp. (π(C),d π,0)), where φπ(π(x)) = (φ−φ◦φ◦)(x) (resp. dπ(π(x)) = (d−d◦φ◦d)(x)). Now, we give some definitions related to integral-chain perturbation of complexes. Definition 3. An integral chain complex (C, d, φ)is called differential (resp. integral pointwise nilpotent) if for any a∈Cthere is some n(a)∈Nwith d(1 −d◦φ−φ◦d)n(a)=0(resp. with φ(1 −d◦φ−φ◦d)n(a)=0). The smallest value for n(a)is referred to as the degree of differential (resp. integral) nilpotency of a. Proposition 4 (Forman).Given an integral (resp. differential) pointwise nilpotent integral chain complex (C, d, φ)is integral chain equivalent to a φ-pure (resp. d-pure) integral chain complex (C, d, ˜ φ)(resp. (C, ˜ d, φ)). Proof. We only prove the existence of the φ-pure integral chain complex (C, d, ˜ φ). The other result can be derived directly from the fact that (C, φ,d) is also a pointwise nilpotent integralchain complex. Define ˜ φ:C∗→C∗+1 by ˜ φ=#k≥0φ◦(1−d◦φ)k. This is well defined due to the pointwise nilpotency of (C, d, φ), since all but finitely many terms vanish on the right hand side. The map ˜ φis 2-nilpotent (˜ φ◦˜ φ= 0) and satisfies the SDR property ˜ φ◦d◦˜ φ=˜ φ. The couple of maps (π(d, ˜ φ),idC) establish the integral chain equivalence between (C, d, φ) and (C, d, ˜ φ). ! Finally, we define the composition of an integral-chain complex. Definition 4. Given a d-pure (resp. two φ-pure) integral-chain complexes (C, d, φ)and a differential operator d#satisfying the homology condition (resp. an integral operator φ#satisfying the strong deformation retract condition) for π(d,φ)(C), a new d-pure (resp. φ-pure) integral chain complex (C, d +d#◦π(d,φ),φ)(resp. (C, d, φ+φ#◦π(d,φ))) can be constructed. This new integral chain complex is called composition of (C, d, φ)by φ#.Ad-pure integral chain complex (C, d, φ) can suffer composition with regards to the own differential operator d(resp. with regard to the own integral operator φ) restricted to π(d,φ)(C). From now on, all the integral chain complexes we consider in the paper will be integral pointwise nilpotents. Analogous results can be determined for differential pointwise nilpotent. In the next section, we define some notions in order to do the link with the algebraic work underlying in Discrete Morse Theory. 37 4 Discrete Morse Theory and optimality Discrete Morse Theory gives a positive answer to the problem of finding combinatorial chain homotopy operators φfor chain complexes (C∗(K),d) of finite cell complexes, such that its integral homology H(C, 0,φ) is a “good” approximation to its differential one H(C, d, 0). Using Persistent Homology [3] Betti numbers can be gradually determined from a filtered chain complex. We will show here that Homological Perturbation Theory can be used as a tool for reaching interesting combinatorial results in DMT (for example, about gradient paths). More precisely, the homology of a chain complex (C, d) can be specified in DMT in terms of finding a combinatorial integral operator φ:C∗→C∗+1 derived from discrete Morse functions and satisfying the SDR condition with regards, to the differential operator d. Definition 5. Let (K, ∂)a finite cell complex. An operator f:C∗(K)→C∗±r(K)is said to be combinatorial if ∀p-cell σ(p),f(σ(p))=λβ (p±r), where λ∈Zand βis a (p±r)−cell. That is, in DMT we search for a combinatorial operator φsuch that (C(K), d, φ) is a φ-pure integral-chain complex. Given a cell complex K, the integral-chain complex canonically associated to Kis (C(K),∂,)), where ∂is the boundary or differential operator for C∗(K) and ):C∗(K)→C∗+1(K) is the coboundary operator defined by )(α(p))=Σ<∂β,α>β, where the sum is taken for all the cells β(p+1), such that a∈∂(β) (i.e. aparticipates in a non-null manner in the linear combination ∂(β)). In DMT, we search for a combinatorial operator φwhich can be derived (choosing one summand in the formula of )for each cell) such that the number of critical cells in (C(K),∂,φ) is minimal. Now, we give some basic notions of DMT with some slightly modifications and without using, in principle, discrete Morse functions. Definition 6. [5, 6] A combinatorial integral operator Vdefined on a cell complex Kis a collection of disjoint pairs of (non-necesarrly incident) cells {α(p)<β(p+1)}. If the pairs are constituted by incident cells then, Vis called combinatorial vector field. We will represent a combinatorial vector field by an arrow from the cell of lower dimension to its paired cell of higher dimension. A combinatorial vector field can be seen as a partial matching in the Hasse diagram for K.AV-path or gradient path γis an alternating sequence of cells a(p) 0,b (p±1) 0,a (p) 1,b (p±1) 1,a (p) 2, . . ., such that for each pair of consecutive simplices, one is a maximal face of the other, and the following condition is satisfied: one of the couples {a(p) i<b (p±1) i}or {b(p±1) i<a (p) i+1}belongs to V,∀i≥0. If the final cell in the gradient path γabove is α(p) r, then we say that γhas length r. If it ends with β(p±1) r then we say that γhas length r1 2. If the cells biof the gradient path γare of dimension p+1 and it has length r1 2, the gradient path γis called upper V- path or upper gradient path. For any cells aand b, let Γ(a, b)denote the set of gradient paths from ato b(of any length), i.e., such that the first cell in the sequence is aand the last cell in the sequence is b.AV-path is non trivial and closed if r≥1and the first and last cells in the sequence are the same. A closed V-path is just an oriented circuit in the Hasse diagram. A cell αis a critical cell of Vif it is not paired with any other cell in V. The number of critical cell depends on the discrete gradient vector field considered. Forman proved [5, 6] that the topology of a discrete manifold is related to the critical elements of a discrete function defined on it, micmicking the results of Morse in the smooth case. In [10], the problem of the optimality (minimizing the number of critical cells for combinatorial vector fields) on a 2-manifold is analyzed using Hasse diagram and hypergraph tools. Therefore, a discrete gradient vector field is a special kind of combinatorial integral operator. First, the combinatorial integral operators derived from combinatorial vector fields are φpointwise nilpotent. Proposition 5. A combinatorial vector field Vgives rise to a φ-pointwise nilpotent integral-chain complex (C(K), d, V ). 38 Let us emphasize that two pairs {a, b}and {a#,b #}of Vhave no elements in common. The combinatorial vector fiel Vgives rise to a linear map V:C∗(K)→C∗+1(K), defined by V(a)=b if {a, b}∈Vand V(a) = 0, in the rest of cells. It is clear that V◦V= 0. The map Vis an integral operator for C∗(K). To prove that (C(K), d, V ) is φ-pointwise integral-chain complex is straightforward. ! Combining Prop. 1, Prop. 2 and Prop. 3, we assert the following result which is the key for reinterpreting DMT in integral-chain terms: Proposition 6. If (C, d, φ)is a φ-pointwise nilpotent integral-chain complex being φa combinatorial vector field, then there is an integral-chain equivalent φ-pure complex (C, d, ˜ φ), such that its harmonic complex π(C, d, ˜ φ) = ( Ker ˜ φ\˜ φ(C),d π,0). This last integral-chain complex is constituted by finite linear combinations of the different critical cells of φand dπcan be seen as the boundary operator of the corresponding cell complex determined by the critical cells, also called harmonic Morse cell complex M(C, d, φ)associated to (C, d, φ). Analogously, the Laplacian complex ∆(C, d, ˜ φ)can be seen as the acyclic chain complex of the cell complex M(C, d, φ), also called Laplacian Morse complex associated to (C, d, φ). Moreover, its boundary operator ∂Mis determined by ∂M(∆(σ(p))) = d◦˜ φ◦d(σ(p)),∀σ(p)∈C. Proof. Due to Prop. 3 and Prop. 1 and defining ˜ φ:C∗→C∗+1 by ˜ φ=#t k=0 φ◦(1 −d◦φ)k= #t k=0(1 −φ◦d)kφ, we have that (f, g) : Ker ˜ φ\˜ φ(C)∼ =π(C, d, ˜ φ) is an isomorphism of chain complexes, with f: Ker ˜ φ\˜ φ(C)→π(C, d, ˜ φ) and g:π(C, d, ˜ φ)→ Ker ˜ φ\˜ φ(C) respectively defined by f(σ)=π(d, ˜ φ)(σ)=σ−˜ φ◦d(σ), ∀σ∈: Ker ˜ φ\˜ φ(C) and g(π(d, ˜ φ))(β)) = β−d◦˜ φ(β), ∀β∈C. Now, let us prove that Ker ˜ φ= Ker φand ˜ φ(C)=φ(C). It is clear that Ker φ⊂Ker ˜ φ. Let x∈Ker ˜ φbe an element such that x/∈Ker φ. That means that #t k=0 π(d, φ)k(x)∈Ker φ. That implies that φ(1 −πt+1)(x)=φ(d◦φ+φ◦d)◦ $#t k=0 π(d, φ)k%(x) = 0 and, then φ(x)=φπt+1(x) = 0. In a similar manner, it is possible to deduce that ˜ φ(C)=φ(C) and that it also admits a combinatorial basis. Let us now prove that the chain complex (˜ φ(C)⊕(d◦˜ φ)(C),d) is acyclic. We have that d(˜ φ(C)) ⊂(d◦˜ φ)(C) and d((d◦˜ φ))(C) = 0. Now, let us suppose that there is a chain x= x#+x## ∈˜ φ(C)⊕(d◦˜ φ)(C) such that d(x) = 0. This means that d(x#) = 0. Since x#=˜ φ(z), then (d◦˜ φ)(z) = 0. Due to the fact that the integral operator satisfy the SDR condition ˜ φ◦d◦˜ φ=˜ φ, we conclude that x#= 0. Finally, the boundary operator of M(C, d, φ) is the differential operator drestricted to it and its acyclicity can be proved using Prop. 3. ! Let us note that H∗(M(C, d, φ)) ∼ =H∗(K, Λ). Moreover, the boundary operator dπof the Morse cell complex M(C, d, φ) have a clear interpretation in terms of gradient paths of ˜ φ. Proposition 7. In the conditions of Prop. 6, and given a p-cell α,˜ φ(α)is an upper gradient φ-path. In [12, 1], a homology integral operator φis determined from a filtered cell complex using an incremental technique. The homology integral operator φgives rise in a natural way to a combinatorial integral function on K. Using spanning homological forests techniques [11] and cancellation–like theorems [6] involving gradient paths, we can conclude that obtaining a combinatorial vector field on Kis straightforward. 39 5 Conclusions In this paper “homological forests” are presented as an useful tool towards the optimallity of a combinatorial gradient vector field defined over a finite cell complex. Relations between Effective Homology techniques and Discrete Morse Theory have been established, and a common dictionary of terms has been defined. This algebraic framework allows us to ensure the “reduction” of the initial complex to its minimal homological expression. The introduced structure allows a direct transition from the integral operator computed over a cell complex, to a minimal combinatorial gradient vector field. References [1] A. Berciano, H. Molina-Abril, A. Pacheco, P. Pilarczyk, and P. Real. Decomposing cavities in digital volumes into products of cycles. In Srecko Brlek, Christophe Reutenauer, and Xavier Proven¸cal, editors, DGCI, volume 5810 of Lecture Notes in Computer Science, pages 263–274. Springer, 2009. [2] M. Desbrun, E. Kanso, and Y. Tong. Discrete differential forms for computational modeling. In SIGGRAPH ’06: ACM SIGGRAPH 2006 Courses, pages 39–54, New York, NY, USA, 2006. ACM. [3] H. Edelsbrunner, D. Letscher, and A. Zomorodian. Topological persistence and simplification. Discrete Comput. Geom., 28:511–533, 2002. [4] S. Eilenberg and S. Mac Lane. On the groups h(π,n), i, ii, iii. Annals of Math, 58, 60, 60:55–106,48–139, 513–557, 1953,1954. [5] R. Forman. A Discrete Morse Theory for Cell Complexes. Topology and Physics for Raoul Bott, S.T. Yau, ed., International Press., 1995. [6] R. Forman. Morse theory for cell complexes. Adv. In Math., 134:90–145, 1998. [7] V. K. A. M. Gugenheim, L. A. Lambe, and J. D. Stasheff. Perturbation theory in differential homological algebra. Illinois J. Math, 33:357–373, 1989. [8] V. K. A. M. Gugenheim, L. A. Lambe, and J. D. Stasheff. Perturbation theory in differential homological algebra. ii. Illinois J. Math., 35(3):357–373, 1991. [9] R. Klette. Cell complexes through time. Communication and Information Technology Research Technical Report, 60, 2000. [10] T. Lewiner, H. Lopes, G. Tavares, and L. Matm´ıdia. Towards optimality in discrete Morse theory. Experimental Mathematics, 12:2003, 2003. [11] H. Molina-Abril and P. Real. Homological computation using spanning trees. In Eduardo Bayro-Corrochano and Jan-Olof Eklundh, editors, CIARP, volume 5856 of Lecture Notes in Computer Science, pages 272–278. Springer, 2009. [12] P. Real, H. Molina-Abril, and W.G. Kropatsch. Homological tree-based strategies for image analysis. In Xiaoyi Jiang and Nicolai Petkov, editors, CAIP, volume 5702 of Lecture Notes in Computer Science, pages 326–333. Springer, 2009. [13] F. Sergeraert. The computability problem in algebraic topology. Advances in Mathematics, 104:1–29, 1994. 40