Homology, Homotopy and Applications, vol.5(2), 2003, pp.233–256

COMPUTING HOMOLOGY

TOMASZ KACZYNSKI, KONSTANTIN MISCHAIKOW and MARIAN MROZEK

(communicated by Gunnar Carlsson)

Abstract The aim of this paper is to provide a short introduction to computational homology based on cubical complexes. The discussed topics include cubical complexes, a reduction algorithm for computing homology of finitely generated chain complexes, and an algorithmic construction of homology of continuous maps via multivalued acyclic representations.

1. Introduction

The aim of this paper is to provide a synthesis of research by the authors and their collaborators on the subject of computing homology of spaces and maps. Our initial motivation came from dynamical systems, a subject with a history rich in entanglements with algebraic topology. It is not a coincidence that Poincar’e was a founding figure in both disciplines. Furthermore, much of modern applied dynamics is closely tied to numerical simulations. Thus, it should not come as a surprise that attempts to understand the structure of specific dynamical systems naturally leads to problems which require homological computations of large high dimensional numerically or experimentally generated complexes and maps thereof (see [21, 20, 18, 19] and references therein). However as one can see e.g. from the expository paper by Dey, Edelsbrunner and Guha [7], we can expect considerably more applications in the future.

From our perspective, there are three fundamental issues that need to be resolved in order to have an effective tool for computing homology. The first involves the underlying combinatorial structure. Obviously, one would like to encode this information in an efficient data structure. However, especially in the setting of dynamics, it is important that this combinatorial structure have nice properties with respect to the dimension of both the objects of interest and the ambient space. Furthermore, it should be noted that in many applications the input takes the form of discrete data points. As we will describe below it is with these constraints in mind that we have

Research by Tomasz Kaczynski is supported by grants from NSERC and FCAR. Research by Konstantin Mischaikow is supported in part by NSF grant DMS-0107396. Research by Marian Mrozek is supported by KBN, grant 2 P03A 011 18. Received October 15, 2001, revised September 9, 2002; published on April 22, 2003. 2000 Mathematics Subject Classification: Primary 55-04; Secondary 52B05, 54C60, 65D17. Key words and phrases: homology computation, algorithm, cubical complex, representable set, mulitivalued map. \begin{matrix}c \\ ◯ \end{matrix} 2003, Tomasz Kaczynski, Konstantin Mischaikow and Marian Mrozek. Permission to copy for private use granted.

chosen to develop a computational homology theory based on cubical complexes, rather than the classical approach involving simplicies [24].

At first glance the simplicial theory appears more elegant than the cubical theory described in Section 2. Furthermore, triangulations are at the heart of much of computational geometry. Thus, our insistence on using the cubical structure may appear strange. Consider, however, that it is hard to think of a scientific or engineering discipline which does not generate computational simulations or make use of recording devices or sensors to produce or collect image data. For example, it is possible, using X-ray computed tomography, to visualize cardiovascular tissue with a resolution on the order of 10 μm. [4]. Because this can be done at a high speed, timed sequences of 3-dimensional images can be constructed, essentially producing a 4-dimensional object. Observe that such images involve large amounts of data since the data sets contain information on the level of tetrals (the four dimensional equivalent of pixels). Obviously, the size and complexity of this data will grow as the sophistication of the sensors or simulations increase. Of course, one can try to render these objects in terms of triangulations thereby producing images that require smaller data sets and even perhaps are more intelligible to the human eye. However, given our current capabilities such rendering is typically quite time consuming and by its very nature results in modifications to the original data. For those applications which only require topological data (for example finding defects in hearts, which unfortunately is an all too common birth defect) the cubical approach allows one in principle to work directly with the raw data. ^{1}

Another typical example involves geometric structures arising from numerical simulations of partial differential equations. If one employs finite element methods based on a regular cubical lattice, then the output once again takes the form of a cubical complex. Furthermore, such computations can very rapidly produce complexes where memory constraints become a serious issue. If as above we think in terms of structures in space and time, then we have four dimensional complexes. Simply subdividing each cube into a simplex results in a simplicial complex with 24 times as many highest dimensional cells, which we claim is an unnecessary cost. Of course, one can imaging more intelligent methods of triangulating the cubical complex, but at a higher computational cost.

Returning to dynamical systems we have two additional problems to contend with. The first is that for many applications one needs to compute not onlythe homology of a space, but also the homology of a continuous function f. The standard approach of the simplicial theory is to approximate f by a simplicial map f_{#} which then induces f_{∗} the map on homology. Unfortunately, the cost of computing f_{#} for a typical nonlinear map f appears to be excessive. To circumvent this problem we essentially compute f_{∗} by making direct use of the geometric acyclic carrier theorem. We will describe this procedure in greater detail shortly, for the moment the important point is that in our applications we need to construct geometric acyclic carriers. Of course this can be done using either simplicies or cubes. However,

1For the purpose of this discussion we are ignoring the issue of noise in the data. In applications this is a serious problem which must be dealt with regardless of whether one uses simplicial or cubical homology.

these carriers are obtained using numerical approximations of the original map f. In higher dimensional problems cubes provide a very simple method data structure for encoding the images of points along with their errors, especially if one uses the l^{∞} norm.

The second problem that is encountered in dynamical systems has to do with the difference between the dimensions of the objects of interest, e.g. a periodic orbit, and the dimension of the phase space which, in the case of a partial differential equation, can be infinite dimensional. A standard method of numerically solving such problems involves the Galerkin method, whereby one projects the infinite dimensional problem onto a finite dimensional subspace and then computes. Topological methods associated with nonlinear functional analysis provide an ideal means of using the information from the finite dimensional computations to deduce information about the infinite dimensional problem. However, to do so efficiently it is useful to have complexes which are compatible with orthogonal projections. As will become clear in Sections 2 and 3, this is an extremely nice feature of the cubical homology.

With this brief justification for using a cubical combinatorial structure we now turn to the problem of extracting algebraic information, i.e. the computation of homology of spaces. In Section 3, we present a procedure based on elementary reductions. The idea is to remove one pair of coinciding generators per time, without changing the homology of the complex, until one gets a complex which has a trivial boundary map, so it is isomorphic to its own homology. Although examples are given among cubical chain complexes, the procedure applies to any finitely generated free chain complex. An algorithm for computing homology of a chain map is a simple by-product. Results presented in this section first appeared in [14] and in somewhat refreshed form in [12]. We present the algorithm for computing homology with coefficients in a field, while we refer to [25] for coefficients in any Euclidean domain. A reduction procedure in the context of cubical complexes was presented in [15]. Homology programs based on our algorithms have been designed in C^{++} by Pilarczyk [25], Mazur and Szybowski [17], and they are currently available at the Web site http://www.math.gatech.edu/ chom/. The same idea of reducing a given complex to a minimal one with the help of the Smith normal form algorithm is explored by Gonzalez-Diez and Real [9] in the context of cohomology computation. Among algorithms of computing homology in low dimensions (simplicial complexes in R^{3} and S^{3}), probably the most efficient one is given by Delfinado and Edelsbrunner [6].

Finally, we deal in Section 4 with the most complex project of computing homology of continuous maps. This project is especially motivated by the previously mentioned applications to dynamical systems but there are also many problems in nonlinear analysis where homology of a map provides a useful information. In this context it is important to have an algorithm which will work for huge complexes coming from fine grids of the space and in arbitrarily high dimensions. The classical approach via barycentric subdivisions and simplicial approximations leads to a high complexity computation. In [2] a new approach is launched. It is proposed to inscribe the graph of a given continuous map f defined on a compact cubical domain into a graph of a finitely representable multivalued map F with acyclic cubical values. The construction of F is based on numerical approximation of f: we only need to know a Lipschitz constant of f (more generally, the modulus of uniform continuity) and to be able to compute its approximative values on fine grid points. The proof of the central Theorem 4.4 provides the construction of a chain selector φ of F whose quotient map φ_{∗} is the homology map φ_{∗} = F_{∗} = of F. In a sense, the multivalued map F is a geometric realization of so called acyclic carrier presented e.g. in [24] thus we bypass the simplicial approximation. In [13], our construction is presented as the definition of the homology map f_{∗} of f and the cubical homology theory is developed in a systematic self-contained way. In this paper, we only present the most important steps needed for understanding the explicit formula for f_{∗}. In the end of Section 4.3 we present a new approach to grid refinements: rather than discussing grid subdivisions we introduce a concept of grid rescaling which allows to avoid generalizing previously introduced algebra to many grids. The final formula for computing f_{∗} is given by Theorem 4.11. In Section 4.4 we present an algorithm for constructing so-called coboundary of a cycle z in an acyclic set, i.e. a chain c (usually not unique) which solves the equation ∂(c) = z. This was the major obstacle from making the construction of the homology map algorithmic. The problem was previously treated in [1, 3, 12, 17]. Although this was not our initial motivation, it is an interesting observation that our cobounday problem is an algebraic analogy of a geometric problem of minimal surfaces [5]. Another approach to computing homology of maps presented in [23] better utilizing the outcome of numerical algorithms for Poincaré maps in differential equations, is under development.

Many results discussed here were previously presented in several research papers [2, 3, 12, 14, 15] and in student dissertations [1, 17, 25]. A systematic presentation of the material was a subject of courses in computational algebraic topology simultaneously taught by the authors at their departments, and it constitutes a part of the book [13] which is in progress now.

2. Cubical Complexes

In numerical and graphical analysis one needs to consider very fine cubical grids. With appropriate units we may assume here that each cube is unitary i.e. it has sides of length 1 and vertices with integer coordinates. Later on in Section 4.3 we will discuss the effects of rescaling on the algebra extracted from a cubical grid.

An elementary cube Q is a finite product

Q = I_{1} × I_{2} × ⋯ × I_{d} ⊂ R^{d}

where I_{i} is an interval of the form I = [l, l + 1] or I = [l, l] for some l ∈ Z. To simplify the notation we will write [l] = [l, l] for an interval that contains only one point, such an interval is called degenerate. When Q ⊂ R^{d}, the dimension d is called the embedding number of Q and denoted by emb Q. The interval I_{i} is referred to as the i-th component of Q and written as I_{i}(Q). The number of non degenerate components in Q is the dimension of Q and denoted by dim Q. The set of all elementary cubes in R^{d} is denoted by K^{d}. The set of all elementary cubes is denoted by K, i.e.

K := ⋃_{d=1}^{∞} K^{d}.

It is easy to see that if Q ∈ K_{k}^{d} and P ∈ K_{k′}^{d′}, then

Q × P ∈ K_{k+k′}^{d+d′}.

A set X ⊂ R^{d} is cubical if X can be written as a finite union of elementary cubes. We shall adopt the following notation.

K(X) := {Q ∈ K | Q ⊂ X}

and

K_{k}(X) := {Q ∈ K(X) | dim Q = k}.

The elements of K_{0}(X) are the vertices of X and the elements of K_{1}(X) are the edges of X. More generally, the elements of K_{k}(X) are the k-cubes of X.

The group C_{k} of k-chains is the free abelian group generated by elements of K_{k}, i.e. C_{k} := Z(K_{k}). More explicitly, C_{k} is formally defined as the group of all those integer-valued functions on K_{k} which are non-zero on finitely many elements of K_{k}. This is a free abelian group generated by functions Q̂ : K_{k} → Z, called duals of Q, given by the formula

Q̂(P) = \{ \begin{matrix}1 & if P = Q \\ 0 & otherwise \end{matrix}

for any Q and P in K_{k}. The set of all duals of elementary cubes denoted by K̂ is a basis of C_{k}. In the literature, it is customary to identify the dual of Q with Q but, for a better understanding of data structures, it is important to distinguish the algebraic object Q̂ from the geometric object Q. For that reason, we shall continue using the “hat” notation for duals of elementary cubes. The elements of C_{k} called k-dimensional chains (k-chains for short) are finite sums of the form

c = α_{1}Q̂_{1} + α_{2}Q̂_{2} … α_{m}Q̂_{m},

where {Q_{1}, Q_{2}, …, Q_{m}} ⊂ K_{k}. If c ∈ C_{k} then dim c := k. Obviously, for k < 0 and k > d the set K_{k} = ∅ and C_{k} = 0.

Let c_{1}, c_{2} ∈ C_{k} and let a = ∑_{i=1}^{m} α_{i}Q̂_{i}, b = ∑_{i=1}^{m} β_{i}Q̂_{i} Given chains c and d, we use the scalar product notation

⟨c_{1}, c_{2}⟩ := ∑_{i=1}^{m} α_{i}β_{i}.

The product of two elementary cubes is again an elementary cube. This motivates the following definition. Given two elementary cubes P ∈ K_{k} and Q ∈ K_{k′} put

P̂ ⋄ Q̂ := { \atop P × Q}.

This formula extends to arbitrary chains c_{1} ∈ K̂_{k} and c_{2} ∈ K̂_{k′} by linearity:

c_{1} ⋄ c_{2} := ∑_{P ∈K_{k},Q∈K_{k′}}⟨c_{1}, P̂⟩⟨c_{2}, Q̂⟩{ \atop P_{i} × Q_{j}}.

The element c ⋄ c_{2} ∈ C_{k+k′} is called the cubical product of c_{1} and c_{2}. It it easy to show that

Proposition 2.1. Let Q be an elementary cube such that emb Q = d > 1. Then, there exist unique elementary cubes I and P with emb I = 1 and emb P = d − 1 such that

Q̂ = Î⋄ P̂.

Let X ⊂ R^{d} be a cubical set. Let K̂_{k}(X) := {Q̂ | Q ∈ K_{k}(X)}. C_{k}(X) is the finitely dimensional subgroup of C_{k} generated by the elements of K̂_{k}(X) and is referred to as the set of k-chains of X.

Let c ∈ C_{k} and let c = ∑_{i=1}^{m} a_{i}Q̂_{i} where a_{i} ≠ 0 for i = 1, …, m. The support of the chain c is the cubical set

|c| := ⋃_{i=1}^{m} Q_{i} ⊂ R^{d}.

It is clear that C_{k}(X) = {c ∈ C_{k} | |c| ⊂ X}.

Given k ∈ Z, the cubical boundary operator

∂_{k} : C_{k} → C_{k−1}

is defined on generators by induction on the embedding number. Let Q̂ ∈ K̂_{k}^{1}, then Q is an elementary interval and hence Q = [l] ∈ K_{0}^{1} or Q = [l, l + 1] ∈ K_{1}^{1} for some l ∈ Z. Define

∂Q̂ := \{ \begin{matrix}0 & if Q = [l], \\ { \atop [l + 1]} − ˆ[l] & if Q = [l, l + 1]. \end{matrix}

Now assume that Q̂ ∈ K̂_{k}^{d} where d > 1. By Proposition 2.1 there exist unique elementary cubical chains Î, P̂ with emb I = 1 and emb P = d − 1 such that

Q̂ = Î⋄ P̂.

Define

∂Q̂ := ∂Î⋄ P̂ + (−1)^{dim I} Î⋄ ∂P̂.  (1)

Finally, we extend the definition to all chains by linearity.

Proposition 2.2. Let c and c′ be cubical chains, then

∂(c ⋄ c′) = ∂c ⋄ c′ + (−1)^{dim c}c ⋄ ∂c′.  (2)

Proof. By linearity, it is sufficient to prove the proposition for elementary cubical chains, i.e. to show that

∂(Q̂ ⋄ Q̂′) = ∂Q̂ ⋄ Q̂′ + (−1)^{dim Q}Q̂ ⋄ ∂Q̂′.

The proof goes by induction on d := emb Q and the decomposition of Q given by Proposition 2.1.

Here is the explicit formula for the boundary map Corollary 2.3. If Q̂_{1}, Q̂_{2}, …, Q̂_{m} are elementary cubical chains, then

∂(Q̂_{1} ⋄ Q̂_{2} ⋄ ⋯ ⋄ Q̂_{m}) = ∑_{j=1}^{m}(−1)^{∑_{i=1}^{j−1} dim Q_{i}} Q̂_{1} ⋄ ⋯ ⋄ Q̂_{j−1} ⋄ ∂Q̂_{j} ⋄ Q̂_{j+1} ⋄ ⋯ ⋄ Q̂_{m}.

Again by induction on the embedding number and an application of Propositions 2.1 and 2.2 one proves the fundamental property ∂ ∘ ∂ = 0 for the cubical boundary operator. It is also useful to observe that |∂c| ⊂ |c|, so ∂_{k}(C_{k}(X)) ⊂ C_{k−1}(X). This implies that, given a cubical set X ⊂ R^{d}, the cubical chain complex

C(X) := {C_{k}(X), ∂_{k}^{X}},

is well defined. In the sequel we will omit the superscript X in ∂_{k}^{X}.

The subgroups of cycles and boundaries in C_{k}(X) are respectively denoted by

Z_{k}(X) := ker ∂_{k} = C_{k}(X) ∩ ker ∂_{k} ⊂ C_{k}(X).  (3)

and

B_{k}(X) := im ∂_{k+1} = ∂_{k}(C_{k+1}(X)) ⊂ C_{k}(X).  (4)

The k-th cubical homology group of X is H_{k}(X) := Z_{k}(X)/B_{k}(X). The homology of X is the graded group H_{∗}(X) := {H_{k}(X)}_{k∈Z}.

3. Computing Homology of Chain Complexes

3.1. Examples of Elementary Reductions

The aim of this section is to develop geometric intuitions behind the general reduction procedure presented next. We emphasize the importance of seeing the geometry behind the algebra since we believe that this will help to render our general reduction algorithm more efficient in particular cases of chain complexes coming from applications, as it was the case with cubical complexes in [3, 15].

We discuss two types of reductions for the cubical chain complex C := C(X) where X = [0, 1] × [0, 2]. Since elementary reductions may give complexes which are not necessarily cubical and duals of elementary cubes may be replaced by generators of a different geometric meaning, the ”hat” notation of the previous section will be cumbersome here. We denote elementary cubes by upper case letters and dual chains by lower case, e.g. v_{i} := V̂_{i} are duals of vertices, a_{i} := Â_{i} are duals of edges and b_{i} := B̂_{i} are duals of squares. We indicate on Figure 1 dual chains rather geometric cubes so to point out their orientation.

With this in mind, C_{0} is generated by E_{0} := K̂_{0}(X) = {v_{1}, v_{2}, … v_{6}}, C_{1} is generated by E_{1} := K̂_{1}(X) = {a_{1}, a_{2}, … a_{7}}, and C_{2} is generated by E_{2} := K̂_{2}(X) = {b_{1}, b_{2}}. The only nontrivial boundary maps ∂_{1} and ∂_{2}. Their definitions can be deduced from fig:collapses (i). e.g. ∂_{1}(a_{1}) = v_{2} −v_{1}, ∂_{2}(b_{1}) = a_{1} +a_{2} −a_{4} −a_{3}. Note that the edge a_{4} is an interior edge in the sense that it is a common edge of more then one elementary square of X. The remaining edges are exterior or free edges, in the sense any one of them is an edge of an exactly one square.

[figure: b_{1}; b_{2}; v_{1}; v_{2}; v_{3}; v_{4}; v_{5}; v_{6}; a_{1}; a_{4}; a_{7}; a_{3}; a_{5}; a_{2}; a_{6}; (i); b_{2}; v_{1}; v_{2}; v_{3}; v_{4}; v_{5}; v_{6}; a_{4}; a_{7}; a_{3}; a_{5}; a_{2}; a_{6}; (ii); v_{1}; v_{2}; v_{3}; v_{4}; v_{5}; v_{6}; a_{7}; a_{3}; a_{5}; a_{2}; a_{6}; (iii)]

Figure 1: Elementary collapses by exterior edges.

Example 3.1. (Exterior face collapses.) Imagine that we push A_{1} from outside so that B_{1} is projected onto the remaining part of its boundary formed of A_{2} A_{3} and A_{4}. By taking account of orientations in Figure 1 (i), a_{1} is projected onto the chain ā_{1} := a_{3}+a_{4}−a_{2} and b_{1} disappears. No new homologically nontrivial cycle is created by the fact that b_{1} disappears because the image of the cycle ∂b_{1} = a_{1} +a_{2} −a_{4} −a_{3} is (a_{3} +a_{4} −a_{2})+a_{2} −a_{4} −a_{3} = 0. This indicates that the homology of the complex C̄ obtained by projecting the generators

a_{1} ↦ ā_{1} = a_{3} + a_{4} − a_{2} , b_{1} ↦ 0,

and keeping the remaining generators fixed should be the same as that of C. The new complex C̄ illustrated in Figure 1 (ii) is a subcomplex of C with bases Ē_{0} := E_{0}, Ē_{1} := {a_{2}, a_{3}, … a_{6}} and Ē_{2} := {b_{2}}.

By repeating the same procedure with the edge a_{4} and square b_{2}, we get a onedimensional complex \overline{\overline{C}} illustrated in Figure 1 (iii). The same procedure can be repeated for the free vertex v_{2} and its unique edge a_{2} and so on. Thus \overline{\overline{C}} can be reduced in the next five elementary collapses to the single vertex v_{1}.

Example 3.2. (Interior vertex reduction.) Face reductions may also be performed starting from the lowest dimension. Imagine that we push the vertex V_{4} along the edge A_{4} so it projects to the vertex V_{3}. The edge A_{4} disappears. If we want to do that without moving interiors of B_{1} and B_{2}, we must drag the edges A_{2} and A_{6} with the vertex V_{4} along A_{4}. With some care about orientations of edges we get the projections

v_{4} ↦ v_{3}, a_{4} ↦ 0, a_{2} ↦ ā_{2} := a_{2} − a_{4}, a_{6} ↦ ā_{6} := a_{4} + a_{6} .

Figure 2 (i) shows a geometric interpretation of the new complex C̄. The topological structure realizing these reductions is the CW-complex (see [24]). Note that the new oriented edges ā_{2} and ā_{6} follow the same path in reverse directions for a

[figure: b_{1}; b_{2}; v_{1}; v_{2}; v_{3}; v_{5}; v_{6}; a_{1}; a_{7}; a_{3}; a_{5}; ā_{2}; ā_{6}; (i); ⋯; b_{1}; b_{2}; v_{3}; ā_{1}; ā_{7}; (ii); b_{1}; v_{3}; ā_{1}; (iii)]

Figure 2: Starting from interior vertex reduction.

while. The whole complex can be visualized as two leafs B_{1} and B_{2} having v_{3} as the only common vertex. By performing vertex reductions in each leaf as in the previous example we arrive at the complex \overline{\overline{C}} shown in Figure 2 (ii). Next, ā_{7} is a free face of b_{2} so an elementary collapse brings the complex to one leaf pictured in Figure 2 (iii) and another projection of ā_{1} through b_{1} brings the complex to C^{f} := C({V_{3}}).

3.2. Reduction Procedure

Let now (C, ∂) = ({C_{q}}_{q∈Z}, {∂_{q}}_{q∈Z}) be a finitely generated free chain complex. Let n_{0} and d(C) be, respectively, the least and the greatest value of q such that C_{q} ≠ 0. Most commonly, n_{0} = 0 but, for example, if we want to compute the reduced homology (see [24]), we study an augmented chain complex and then n_{0} = −1. The number d(C) is called the dimension of C. Let d_{q} := dim C_{q} := card (E_{q}) (the number of elements in E_{q}) for each q.

Assume that a fixed base E_{q} of C_{q} is given for each q such that C_{q} ≠ 0. We shall call it the canonical basis of C_{q}. Let ⟨·, ·⟩ denote the scalar product associated to that canonical basis. Given c ∈ E_{q}, the generators e ∈ E_{q−1} such that ⟨∂c, e⟩ ≠ 0 are faces of c. The number ⟨∂c, e⟩ is the incidence number of e in ∂c. It is simply the coefficient of e in the expansion of ∂c as a linear combination of elements of E_{q}.

Let m ∈ Z be a fixed number. Assume that a ∈ E_{m−1} and b ∈ E_{m} are two fixed elements such that

λ := ⟨∂b, a⟩ is invertible.  (5)

So far we have been using coefficients in Z so the condition λ invertible means λ = 1 or λ = −1. Later on, we will use coefficients in a field where λ is invertible if and only if λ ≠ 0 so this condition will be less restrictive.

Consequently, ∂b can be written as ∂b = λa + r, where ⟨a, r⟩ = 0. Let

E_{m−1} = {a_{1}, a_{2}, … a_{d_{m−1}−1}, a} ,

E_{m} = {b_{1}, b_{2}, … b_{d_{m}−1}, b} .

We shall write r as

r = ∑_{i=1}^{d_{m−1}−1} α_{i}a_{i} .

For any q ∈ Z, define a map π_{q} : C_{q} → C_{q} by the formula

π_{q}v := \{ \begin{matrix}v − λ^{−1}⟨v, a⟩∂b & if q = m − 1 , \\ v − λ^{−1}⟨∂v, a⟩b & if q = m , \\ v & otherwise, \end{matrix}  (6)

where v ∈ C_{q}. We let C̄_{q} := im π_{q} be the image of C_{q} in π_{q}.

It is easy to show that the map π_{q} is a linear projection of C_{q} onto its image C̄_{q}. More precisely, it is a linear map with the property π_{q}w = w for all w ∈ C̄_{q}. We should explicitly identify the images of the basic elements under π_{m−1} and π_{m}. For simplicity of notation we put v̄ := π_{q}v and γ_{i} := λ^{−1}⟨∂b_{i}, a⟩. It is easily seen that

ā_{i} = a_{i} , ā = −λ^{−1}r  (7)
b̄_{i} = b_{i} − γ_{i}b , b̄ = 0 .  (8)

We put

Ē_{q} = \{ \begin{matrix}\{b̄_{1}, b̄_{2}, … b̄_{d_{m}−1}\} & if q = m , \\ \{a_{1}, a_{2}, … a_{d_{m−1}−1}\} & if q = m − 1 , \\ E_{q} & otherwise. \end{matrix}  (9)

For the proof of the following proposition and theorem, we refer the reader to [12].

Proposition 3.3. Ē_{q} is a basis for C̄_{q} for all q ∈ Z and Ē_{m} ∪ {b} is a basis for C_{m}.

Theorem 3.4. The function π : C → C consisting of the sequence of projections {π_{q}}_{q∈Z} is a chain map.

Corollary 3.5. The sequence of groups (C̄, ∂) := {(C̄_{q}, ∂_{q})_{q∈Z}} is a chain subcomplex of (C, ∂) and the restriction π̄ : C → C̄ of the codomain of π to its image is a chain map.

The most important feature of the new chain complex is expressed in the following theorem. We present a part of its proof which contains the construction of maps useful in the sequel.

Theorem 3.6. H_{∗}(C̄) ≅ H_{∗}(C).

Proof. We will show that π̄ : C → C̄ is a chain equivalence with the inclusion i : C̄ ↪ C as a homotopical inverse. Indeed, as mentioned before, π̄ is a projection so π̄i = id C̄. Hence it is sufficient to find a chain homotopy between iπ̄ = π and id_{C}. Let D_{q} : C_{q} → C_{q+1} be given by

D_{q}v = \{ \begin{matrix}λ^{−1}⟨v, a⟩b & if q = m − 1 , \\ 0 & otherwise \end{matrix}

for any v ∈ C_{q}. It remains to show the identity

id_{C_{q}} − i_{q}π̄_{q} = ∂_{q+1}D_{q} + D_{q−1}∂_{q} .  (10)

We refer the reader to [12, 14] for details.

Let now

C^{0} ⟶^{π̄^{1}} C^{1} ⟶^{π̄^{2}} C^{2} ⋯  (11)

be a sequence of chain subcomplexes and projections obtained from (C, ∂) by iterating the above construction as long as it is possible to choose m ∈ {n_{0}, n_{0} + 1, …, d(C)}, a ∈ C_{m−1} and b ∈ C_{m} such that λ := ⟨∂b, a⟩ is invertible. Thus C^{0} := C, C^{k+1} := C̄^{k} and E_{q}^{k+1} := Ē_{q}^{k} for all q ∈ Z. We denote by ∂^{k} the restriction of ∂ to C^{k}.

Denote by M(k) = ∑_{q} card (E_{q}^{k}), for k = 0, 1, 2, … Since C is finitely generated, M(k) < ∞ and M(k + 1) = M(k) − 2, therefore there exists a final element of that sequence denoted by (C^{f}, ∂^{f}), beyond which the construction cannot be extended. The following corollary is deduced from Theorem 3.6 by induction.

Corollary 3.7.

H_{∗}(C) ≅ H_{∗}(C^{f}) .

It seems that H_{∗}(C^{f}) should now be easier to compute than H_{∗}(C) , because C^{f} has less generators left. In general, one should incorporate the Smith normal form reduction arguments for judicious choice of pairs (b, a) of generators to eliminate. This has been done in [25]. In many applications however we are only interested in detecting nontrivial homologies or estimating Betti numbers. In that case one can reduce a task by computing homology with coefficients in a field F, e.g. F = Z_{p} where p is prime, or F = Q, the field of rational numbers. This means in practice that C_{q} is defined as a vector space over F with the same E_{q} as the canonical basis and the chain complex C is a graded vector space with ∂ the graded linear map defined as previously on generators. The relationship between homologies for field coefficients and those for integer coefficients are described by the Universal Coefficient Theorem (see [24]).

Theorem 3.8. Suppose now that the computation is performed for coefficients in a field F. Then ∂^{f} = 0 and

H(C, F) ≅ H(C^{f}, F) = C^{f} .

Proof. The first identity is proved in Corollary 3.7. Since F is a field then λ is invertible if and only if and only if it is non-zero. Hence the construction can be iterated as long as there exist m and two elements a ∈ E_{m−1}^{k} and b ∈ E_{m} satisfying ⟨∂b, a⟩ ≠ 0 i.e. as long as ∂ ≠ 0. Therefore ∂^{f} = 0. But this means that H(C^{f}, Z_{p}) = C^{f}.

We outline below an algorithm due to Kaczynski-Mrozek-Ślusarek [14], which we call here KMS algorithm, based on the above reduction procedure. This algorithm computes homology of chain complexes with coefficients in a field but we shall restrict the analysis to mod p computation, i.e. for coefficients in the field Z_{p}, because this choice is the most efficient due to a low cost od division operation.

For simplicity we assume that n_{0} = 0, this is the case when C is a cubical complex. We put N = max{d_{q} | q = 0, 1, …, d(C)}. We assume that there is a fixed upper bound for d(C) and we shall estimate the time or complexity of calculations as a function of N.

A direct implementation of a classical homology computation by linear algebra methods ([24]) when applied to computations over the field Z_{p} yields an O(N^{3}) algorithm. This means that if the number of arithmetic operations is comparable with N^{3} for large values of N. For some special cases KMS algorithm achieves significant improvement of that bound.

For a fixed dimension the process is controlled by procedure COLLAPSE and a single reduction step is executed by procedure REDUCE.

Algorithm 3.9. (Algorithm HOMOLOGY) input: finite chain complex C with coefficients in Z_{p}. output: nonnegative integers β(0), β(1), … β(d(C)) (these are dimensions of H_{q}(C, F)). for q = d(C) downto 1 do COLLAPSE(q); β(q) = card E(q); end. procedure COLLAPSE(q); while E(q) ≠ ∅ and there exist b ∈ E(q) and a ∈ E(q − 1) such that ⟨∂b, a⟩ ≠ 0 do REDUCE(b, a); end.

Procedure REDUCE operates on the following data structures:

1. An array T_{m} of all m-generators;

2. An array T_{m−1} containing all faces of m-generators;

3. For each m-generator b a list F (b) of its faces sorted by faces with their incidence numbers in ∂b.

Algorithm 3.10. procedure REDUCE(b, a); for each b′ in T_{m} do if a appears in F (b′) then compute new list F (b′) by means of synchronous scan (i.e. merge) of F (b) and F (b′) end REDUCE.

A single execution of REDUCE costs O(N^{2}) and assuming that d(C) is fixed one shows that homology groups with coefficients in Z_{p} of a finitely generated chain complex can be computed in O(N^{3}) arithmetical operations.

As already mentioned there are special cases when the algorithm runs much faster. Observe that 0-dimensional homologies can be computed by finding the number of connected components of the graph which can be performed in linear time by classical graph scan methods like depth-first search. Next, 1-dimensional homologies can be specified by computing the number of fundamental cycles in the graph. For a connected graph this needs no computation at all because this number is d_{1} − d_{0} + 1 by the Euler characteristic. When X is a cubical set in R^{2} it can be proved that there exists an edge A which is a face of exactly one elementary square Q. The procedure REDUCE applied to (Q̂, Â) is in fact an elementary collapse, so the resulting complex is again a cubical complex and incidence numbers are 0, 1 or −1. We may iterate this procedure until we get a 1-dimensional complex. The following result is derived.

Theorem 3.11. Let X be a cubical set in the plane R^{2}. Then the homology of C(X) is be computed in linear time. Moreover this also holds true for computation in integer coefficients.

The fact that Betti numbers of polyhedra in R^{2} can be computed in linear time has already been observed by Delfinado and Edelsbrunner [6]. We refer the reader to [12, 14, 15] for further discussion of cases when the complexity of the reduction algorithm can be improved.

3.3. Computing Homology of a Chain Map

Given a triple (C, D, φ) where C, D are finite chain complexes with coefficients in a field F and φ : C → D is a chain map, a reduction performed either on C or D induces a reduction on the whole triple.

Indeed, if C̄ is obtained from C by an elementary reduction, we define φ̄ : C̄ → D̄ by φ̄ := φi, where i : C̄ ↪ C is the inclusion chain map given in the proof of Theorem 3.6. If D̄ is obtained from D, we define φ̄ : C → D̄ by φ̄ := π̄φ where π̄ : D → D̄ is the projection chain map given for D as in Corollary 3.5. Since we showed in the proof of Theorem 3.6 that i and π̄ induce isomorphisms in homology, this procedure can be iterated so that in the final stage we get a chain map φ^{f} : C^{f} → D^{f} such that the diagram

C ⟶^{φ} D
↑_{j^{f}}  ↓_{p^{f}}
C^{f} ⟶^{φ^{f}} D^{f}

commutes and the vertical arrows induce isomorphisms in homology. Thus Corollary 3.7 and the above discussion imply the following

Corollary 3.12. If field coefficients are assumed then the triple (C^{f}, D^{f}, φ^{f}) is isomorphic to the triple (H(C), H(D), φ_{∗}) in the sense that the vertical arrows in the following commuting diagram are isomorphisms:

H(C) ⟶^{φ_{∗}} H(D)
↑^{i_{∗}^{f}}  ↓^{p_{∗}^{f}}
C^{f}  ⟶^{φ^{f}} D^{f}

The above discussion permits one to obtain an algorithm of computing homology of a chain map. Assume that C, D are finite chain complexes with coefficients in a field F and φ : C → D is a chain map. For each q ∈ Z let A_{q} be the matrix of φ_{q} : C_{q} → D_{q} with respect to fixed bases E_{q} and F_{q} in C_{q} and D_{q}, respectively.

Given the reduction of elements a and b in C_{m−1} and C_{m} we define the matrix Ā_{q} of φ̄_{q} : C̄_{q} → D_{q}, for each q, by specifying its columns, using the map i discussed in Section 3.3. If q ≠ m then Ā_{q} = A_{q}. Assume then q = m. Let Col(e) be the column of A_{q} which corresponds to e ∈ E_{m}, let λ = ⟨∂b, a⟩ ≠ 0, and let c_{e} = ⟨∂e, a⟩, e ∈ Ē_{m} = E_{m} \ {b}.

If c_{e} ≠ 0, put \overline{Col}_{e} = Col_{e}, otherwise \overline{Col}_{e} = Col_{e} − c_{e}λ^{−1}Col_{b}.

Analogically, given the reduction of elements a and b in D_{m−1}, D_{m} we define the matrix Ā_{q} of φ̄_{q} : C_{q} → D̄_{q}, for each q, by specifying its rows, using the definition of the map p̄ from discussed in Section 3.3.

If q ≠ m − 1, m then Ā_{q} = A_{q}. If q = m we obtain Ā_{q} by deleting the row Row_{b} which corresponds to b in A_{q}. Assume then q = m−1 and let f ∈ F̄_{m−1} = F_{m−1}\{a}. Let Row_{f} be the row of A_{m−1} which corresponds to f. Let Row_{a} be the row which corresponds to a and let d_{f} = ⟨∂b, f⟩. It is easy to check that the row in the matrix Ā_{m−1} which corresponds to f is given by

\overline{Row}_{f} = Row_{f} − λ^{−1}d_{f}Row_{a}

For a fixed q the computation of φ̄_{q} : C̄ → D̄ consists of two iterated transformations of the matrix A_{q}, each one taking O(n^{2}) time. We can iterate the above matrix transformations until there is no possibility for a one-step reduction, finally obtaining the homomorphism φ^{∗} : H(C) → H(D) corresponding to the chain map φ : C → D. Since the dimension of the complexes is fixed we get an algorithm for computing the homology of a chain map of complexity O(n^{3}).

4. Towards Computing Homology of Maps

As it was indicated in the introduction, we shall present here the approach to computing homology of a continuous map between cubical sets via its multivalued representation. We shall present only those proofs which contain constructions important for the algorithm design. The detailed proofs of all statements will be presented in [13].

4.1. Topology of Representable Sets

Cubical sets are compact. It is often useful to have a locally finite class of sets which contains cubical sets but is closed under set-theoretical and topological operations. For this reason we present the notion of elementary cells and representable sets introduced in [22].

With any elementary cube Q = I_{1}×I_{2}×…×I_{d} ⊂ R^{d} we associate the associated elementary cell

Q^{∘} := I^{∘}_{1} × I^{∘}_{2} × … × I^{∘}_{d}.

where

I^{∘} := \{ \begin{matrix}(l, l + 1) & if I = [l, l + 1], \\ [l] & if I = [l, l]. \end{matrix}

We purposely avoided the temptation of calling Q^{∘} an open cube since it is not open in R^{d}, unless its dimension is equal to the embedding number.

A set Y ⊂ R^{d} is representable if it is a finite union of elementary cells. The family of representable sets in R^{d} is denoted by R^{d}.

The closed hull of a set A ⊂ R^{d} is

ch (A) := ⋃{Q | Q ∈ K, Q^{∘} ∩A ≠ ∅}.  (12)

Example 4.1. If x, y ∈ R, x ⩽ y are two arbitrary real numbers then

ch ([x, y]) = [p, q],

where p := max{m ∈ Z | m ⩽ x} and q := min{m ∈ Z | m ⩾ y} denote the floor of x and ceiling of y respectively. This in turn implies that given bounded intervals A_{1}, A_{2}, …, A_{d} we have

ch (A_{1} × A_{2} × … × A_{d}) = ch (A_{1}) × ch (A_{2}) × … × ch (A_{d}).

In particular, ch (A_{1} × A_{2} × … × A_{d}) is a rectangle in R^{d}.

For a more systematic presentation of properties of representable sets we refer the reader to [22].

4.2. Cubical Multivalued Maps

Let X and Y be cubical sets. A cubical multivalued map F : X\overrightarrow{→}Y from X to Y is a function from X to subsets of Y (i.e. for every x ∈ X, F (x) ⊂ Y) which has the following properties.

1. For every x ∈ X, F (x) is a cubical set.

2. For every Q ∈ K(X), F |_{Q^{∘}} is constant, i.e. if x, x′ ∈Q^{∘}, then F (x) = F (x′).

Given A ⊂ X and B ⊂ Y we let F (A) := ⋃_{x∈A} F (x). A multivalued map F is upper semicontinuous if {x ∈ X | F (x) ⊂ U} is open for any open U ⊂ Y and it is lower semicontinuous if the set {x ∈ X | F (x) ∩ U ≠ ∅} is open for any open U ⊂ Y.

Proposition 4.2. Assume F : X\overrightarrow{→}Y is a cubical map. Then F is lower semicontinuous if and only if it has the following property:

For any P, Q ∈ K(X) such that P is a face of Q, F (P^{∘}) ⊂ F (Q^{∘}).  (13)

Similarly, upper semicontinuous cubical maps are characterized by the property:

Proposition 4.3. Assume F : X\overrightarrow{→}Y is a cubical map. Then F is upper semicontinuous if and only if it has the following property:

For any P, Q ∈ K(X) such that P is a face of Q, F (Q^{∘}) ⊂ F (P^{∘}).  (14)

The above propositions show how to construct lower semicontinuous and upper

semicontinuous maps if their values on elementary cells are given. Indeed, if F (Q^{∘}) is defined for all maximal Q and we put

F (P^{∘}) = ⋂{F (Q^{∘}) | P ≺ Q and Q is maximal},  (15)

we get a lower semicontinuous map. Similarly, if we put

F (P^{∘}) = ⋃{F (Q^{∘}) | P ≺ Q and Q is maximal},

we get an upper semicontinuous map. Lower semicontiuous maps are those which we need here for computing the homology. Upper semicontinous maps, however, are those whose graphs are easier to draw since they are closed.

A cubical multivalued map F : X\overrightarrow{→}Y is called acyclic if for every x ∈ X the set F (x) is acyclic. The next theorem is the central result of this section. Although it can be found in various formulations e.g. in [1, 2] and in [24] under the name Acyclic Career Theorem, we present it here with a detailed proof since the proof directly serves for the algorithm design.

Theorem 4.4. Assume F : X\overrightarrow{→}Y is a lower semicontinuous, acyclic, cubical map. Then, there exists a chain map φ : C(X) → C(Y) with the two properties

|φ(Q̂)| ⊂ F (Q^{∘}) for all Q ∈ K(X),  (16)
φ(Q̂) ∈ K̂_{0}(F (Q)) for all Q ∈ K_{0}(X),  (17)

Proof. We will construct the homomorphisms φ_{k} : C_{k}(X) → C_{k}(Y) by induction in k. For k < 0, C_{k}(X) = 0 , therefore there is no choice but to define φ_{k} := 0.

Consider k = 0. For each Q ∈ K_{0}, choose P ∈ K_{0}(F (Q)) and set

φ_{0}(Q̂) := P̂.  (18)

Clearly, |φ_{0}Q̂| = P ∈ F (Q). Since, Q ∈ K_{0}, Q^{∘}= Q and hence F (Q) = F (Q^{∘}).

Therefore |φ_{0}Q̂| ⊂ F (Q^{∘}). Furthermore, φ_{−1}∂_{0} = 0 = ∂_{0}φ_{0}.

Suppose now that φ_{i} : C_{i}(X) → C_{i}(Y), i = 0, 1, 2, …, k − 1, are constructed in such a way that

|φ_{i}Q̂| ⊂ F (Q^{∘}) for all Q ∈ K_{i}(K),

and

φ_{i−1}∂_{i} = ∂_{i}φ_{i}.  (19)

Let Q ∈ K_{k}(X). Then ∂Q̂ = ∑_{j=1}^{m} α_{j}Q̂_{j} for some α_{j} ∈ Z and Q_{j} ∈ K_{k−1}(X). Since

F is lsc, we have by Proposition 4.2

|φ_{k−1}Q̂_{j}| ⊂ F (Q^{∘}_{j}) ⊂ F (Q^{∘})

for all j = 1, …, m. Thus |φ_{k−1}∂Q̂| ⊂ F (Q^{∘}). Since F (Q^{∘}) = F (x) for any x ∈Q^{∘}, the

set F (Q^{∘}) is acyclic. By the induction assumption (19)

∂_{k−1}φ_{k−1}∂_{k}Q̂ = φ_{k−2}∂_{k−1}∂_{k}Q̂ = 0,

i.e. φ_{k−1}∂Q̂ is a cycle.

The case k = 1 should be distinguished because all 0-chains are 0-cycles and this information is not useful. In that case, Q is an interval and ∂Q̂ = B̂ − Â where A and B are vertices of Q. We showed above that the vertices φ_{0}(A) and φ_{0}(B) are

supported in F (Q^{∘}). Since F (Q^{∘}) is acyclic, it is connected and that this implies the

existence of a chain of edges c ∈ C_{1}(F (Q^{∘})) such that ∂c = φ_{0}(B) − φ_{0}(A). We put

φ_{1}Q̂ := c.

When k > 1, the acyclicity of F (Q^{∘}) implies that there exists a chain c ∈ C_{k}(F (Q^{∘})) such that ∂c = φ_{k−1}∂Q̂. Define

φ_{k}Q̂ := c.

By definition, the homomorphism φ_{k} satisfies the property

∂_{k}φ_{k} = φ_{k−1}∂_{k}.

Also, if Q ∈ K_{k}(X), then φ_{k}Q̂ ∈ C_{k}(F (Q^{∘})), hence |φ_{k}Q̂| ⊂ F (Q^{∘}). This completes the induction step.

Observe that in the first nontrivial step (18) of the inductive construction of φ we were allowed to choose any P ∈ K_{0}(F (Q)). Thus, this procedure allows us to produce many chain maps of the type described in Theorem 4.4. Any such chain map is called a chain selector of F.

By carrying over the inclusion (16) to linear combinations of generators of a chain, one proves that, for any c ∈ C(X) w have |φ(c)| ⊂ F (|c|). The following theorem is proved by standard chain homotopy arguments and induction.

Theorem 4.5. Let φ, ψ : C(X) → C(Y) be chain selectors for the lower semicontinous, acyclic, cubical map F : X\overrightarrow{→}Y. Then, φ is chain homotopic to ψ, and hence, they induce the same homomorphism in homology.

The above theorem permits now to give the following definition. Let F : X\overrightarrow{→}Y be a lower semicontinuous, acyclic, cubical map. Let φ : C(X) → C(Y) be a chain selector of F. The homology map F_{∗} : H_{∗}(X) → H_{∗}(Y) of F is defined by

F_{∗} := φ_{∗}.

This definition coincides with a classical definition of homology of a multivalued map given via the Vietoris-Begle Theorem e.g. in [10]. Here is a conditional functoriality property of homology in the class of acyclic multivalued maps:

Theorem 4.6. Let F : X\overrightarrow{→}Y and G : Y \overrightarrow{→}Z be lower semicontinuous, acyclic, cubical maps. If G ∘ F also is acyclic then

(G ∘ F)_{∗} = G_{∗} ∘ F_{∗} ,

where G ∘ F (x) := G(F (x)).

4.3. Homology of Continuous Maps Via Cubical Representations

Let X and Y be cubical sets and let f : X → Y be a continuous function. A cubical representation to f or simply a representation to f is a lower semicontinuous multivalued cubical map F : X\overrightarrow{→}Y such that

f(x) ∈ F (x)  (20)

for every x ∈ X. The minimal cubical representation M_{f} of f is given by

M_{f}(x) := ch (f(ch (x))) .  (21)

It is easily proved that M_{f} is in fact a representation of f and that it is minimal in the sense that given any other representation F of f, M_{f} is a submap of F. If F admits an acyclic representation, the Vietoris-Begle Theorem (c.f. [10]) implies that the homomorphism f_{∗} : H_{∗}(X) → H_{∗}(Y) induced by f in homology is f_{∗} = F_{∗}. Of course, this is not the case in general as the following example shows.

Example 4.7. Let X be the boundary of the unit square Q = [0, 1]^{2}. Consider its sides K_{1} := [0] × [0, 1], K_{2} := [0, 1] × [1] K_{3} := [1] × [0, 1], and K_{4} := [0, 1] × [0]. Consider the map λ : [0, 1] → X given for any t ∈ [0, 1] by

λ(t) := \{ \begin{matrix}(0, 4t) & if t ∈ [0, 1/4] \\ (4t − 1, 1) & if t ∈ [1/4, 1/2] \\ (1, 3 − 4t) & if t ∈ [1/2, 3/4] \\ (4 − 4t, 0) & if t ∈ [3/4, 1] \end{matrix}

Let f : X → X be given at (x_{1}, x_{2}) ∈ X by

f(x_{1}, x_{2}) := \{ \begin{matrix}λ(x_{2}) & if (x_{1}, x_{2}) ∈ K_{1} ∪ K_{3} \\ λ(x_{1}) & if (x_{1}, x_{2}) ∈ K_{2} ∪ K_{4}. \end{matrix}

Then f is continuous and for (x_{1}, x_{2}) ∈K^{∘}_{i}

M_{f}(x_{1}, x_{2}) = ch (f(ch (x_{1}, x_{2}))) = ch (f(K_{i})) = ch (X) = X.

Obviously M_{f} is not acyclic.

In order to overcome the lack of acyclic representation we could introduce subdivisions of the unitary cubical grid we considered. However, that would require a generalization of all what we have done until now to fractional grids. That is not necessary. Instead we take a natural approach based on rescaling the domain of the function to a larger size by changing units.

A scaling vector is a vector of positive integers

α = (α_{1}, α_{2}, …, α_{d}) ∈ Z^{d}

The corresponding scaling is the linear coordinate preserving isomorphism Λ^{α} : R^{d} → R^{d} defined by

Λ^{α}(x) := (α_{1}x_{1}, α_{2}x_{2}, … α_{d}x_{d}).

It is easy to see that Λ^{α} maps cubical sets onto cubical sets. Let X ⊂ R^{d} be a cubical set and let α ∈ Z^{d} be a scaling vector. Define Λ_{X}^{α} := Λ^{α}|_{X}. The scaling of X by α is

X^{α} := Λ_{X}^{α}(X) = Λ^{α}(X).

The inverse of the map Λ_{X}^{α} : X → X^{α} is Ω_{X}^{α} : X^{α} → X := (Λ_{X}^{α})^{−1} given by

Ω_{X}^{α}(x) := (α_{1}^{−1}x_{1}, α_{2}^{−1}x_{2}, …, α_{d}^{−1}x_{d}).

Scalings, their compositions, and inverses are convenient maps in the sense that their minimal cubical representations are acyclic:

Proposition 4.8. Let X be a cubical set and let α be a scaling vector. The maps M_{Λ_{X}^{α}} and M_{Ω_{X}^{α}} are acyclic. Moreover let X, Y, and Z be cubical sets and let α and β be scaling vectors. If Λ^{α}(X) ⊂ Y and Λ^{β}(Y) ⊂ Z, then M_{Λ_{Y}^{β} ∘Λ_{X}^{α}} and M_{Λ_{Y}^{β}} ∘ M_{Λ_{X}^{α}} are acyclic.

Since the map Λ_{X}^{α} : X → X^{α} is isomorphism and Ω_{X}^{α} its inverse, the maps induced in homology

(Λ_{X}^{α})_{∗} : H_{∗}(X) → H_{∗}(X^{α}) and (Ω_{X}^{α})_{∗} : H_{∗}(X^{α}) → H_{∗}(X)

are also isomorphisms. What is important that, in the view of Proposition 4.8, we can compute the inverse ((Λ_{X}^{α})_{∗})^{−1} directly from M_{Ω_{X}^{α}} thus avoiding a complex algorithm of finding an inverse of a homomorphism.

Given a continuous map f : X → Y and a scaling vector α put

f^{α} := f ∘ Ω_{X}^{α}

Observe that f^{α} : X^{α} → Y. We shall head towards showing that M_{f^{α}} is acyclic for a sufficiently large α.

Example 4.9. Return to Example 4.7. Consider α = (2, 2), and let Q = [0, 1] × [2].

Let (x_{1}, x_{2}) ∈Q^{∘}. Then

M_{f^{α}}(x_{1}, x_{2}) = ch (f^{α}(Q)) = ch (λ([0, 1/2])) = [0] × [0, 1] ∪ [0, 1] × [1]

which is acyclic. Similar checks at all segments on X^{α} shows that M_{f^{α}} is acyclic.

Proposition 4.10. Let X and Y be cubical sets and f : X → Y be continuous. Then there exists a scaling vector α such that M_{f^{α}} is acyclic.

Proof. The continuity of f lets us choose δ > 0 such that for x, y ∈ X

dist (x, y) ⩽ δ ⇒ dist (f(x), f(y)) ⩽ \frac{1}{2}  (22)

Let α be a scaling vector such that min{α_{i} | i = 1, …, n} ⩾ 1/δ. Since diam ch (x) ⩽ 1, we get from (22) that

diam f^{α}(ch (x)) ⩽ \frac{1}{2}.

Let A = f^{α}(ch (x)). We need to show that ch (A) is acyclic. Let

C := {Q ∈ K(Y) |Q^{∘} ∩A ≠ ∅}.

Since Y is cubical ch (A) = ⋃_{Q∈C} Q. Observe that for any two elementary cubes P, Q ∈ C the intersection P ∩ Q is non-empty, because diam A < 1. From this it can be deduced that ⋂ C is non-empty. It follows that ch (A) is star-shaped and consequently acyclic.

We can now give the formula for the homology map of a continuous function on cubical set.

Theorem 4.11. Let f : X → Y be a continuous function where X and Y are cubical sets. Let α be a scaling vector such that M_{f^{α}} is acyclic. Then, the homology map of f_{∗} : H_{∗}(X) → H_{∗}(Y) is given by

f_{∗} = M_{(f^{α})_{∗}} ∘ M_{(Λ_{X}^{α})_{∗}}.  (23)

Proof. The map M_{(f^{α})_{∗}} is well defined by the acyclicity assumption and M_{(Λ_{X}^{α})_{∗}} is well defined by Proposition 4.8. Since Ω_{X}^{α} is the inverse of Λ_{X}^{α}, we have

f = f ∘ Ω_{X}^{α} ∘ Λ_{X}^{α} = f^{α} ∘ Λ_{X}^{α}

and formula (23) follows.

We conclude this section with the following remark. In [13] the homology theory is developed for the category Cub of cubical sets with continuous maps as morphism. The construction of homology map f_{∗} by means of the formula (23) and the chain selector provided by Theorem 4.4 is presented there as the definition of f_{∗}. It is proved there that so obtained homology is a functor from Cub to Ab, the category of abelian groups. Direct proofs of homology axioms, in particular, the homotopy property, are provided. This functor is next extended to the category Pol of topological polyhedra which is defined in [13] as the class of topological spaces which are homeomorphic to cubical sets. Since any simplex is homeomorphic to an elementary cube, this class contains, in particular all polyhedra.

4.4. Coboundary Formula

Computation of homology of a continuous map f relies on three algorithms. One computes a cubical representation F of f. The second one does rescaling. The third one computes a chain selector of a cubical acyclic map obtained by rescaling. The proof of Theorem 4.4 which provides the chain selector goes by induction which is very easy to program, it does however contain one existential quantifier:

”The acyclicity of F (Q^{∘}) implies that there exists a chain c ∈ C_{k}(F (Q^{∘})) such that ∂c = φ_{k−1}∂Q̂.” One should therefore provide an explicit algorithm for constructing that c. The problem may be formulated as follows. Let C will be an acyclic finitely generated chain complex. Let z ∈ Z_{m−1} be a (m − 1)-cycle. By the acyclicity assumption, there exists a chain c ∈ C_{m} such that

∂c = z .  (24)

In general, c is not unique. We want to provide an explicit algorithm for finding at least one such a chain which will be denoted by Cob (z). We shall provide here a summary of the algorithm presented in [12]. We refer to [12] for proofs and for a presentation of the formal algorithm. The construction of Cob (z) is derived as a by-product of the reduction algorithm presented in Section 3.2.

Lemma 4.12. Let a ∈ C_{m−1}, b ∈ C_{m} and p : C → C be as in the elementary reduction step in Section 3.2. Let z ∈ Z_{m−1} be a given cycle. Put α := ⟨z, a⟩. Then (a) z̄:= p_{m−1}z ∈ Z̄_{m−1}.

(b) ∂(αλ^{−1}b) = z − z̄.

Note that the conclusion of Lemma 4.12 holds true even if α = 0 but in that case z̄ = z. We may want to avoid repetitions of (a, b)-reductions which are not necessary for computing Cob (z). We introduce the following notation. Given any c ∈ C_{m−1} let

E_{m−1}(c) := {a ∈ E_{m−1} : ⟨c, a⟩ ≠ 0} , E_{m}(c) := {b ∈ E_{m} : ⟨∂b, c⟩ ≠ 0} .

Lemma 4.13. Let z ∈ Z_{m−1}, z ≠ 0. Then E_{m−1}(z) ≠ ∅ and, for any a ∈ E_{m−1}(z), E_{m}(a) ≠ ∅.

We shall now head towards the construction of Cob (z). We start from c = 0. Then use recursively (b, a)-reductions simultaneously adding the term αλ^{−1}b which appears in Lemma 4.12 to the previous value of c, and replacing the previous value of z by z̄. This procedure must end since, each time we repeat it, the cardinality of Ē_{m−1} and Ē_{m} decreases by one and those sets are finite. When it ends, the final value of z̄ is 0, and the final value of c satisfies ∂c = z − 0 = z.

To formalize this discussion let us go back to the sequence of projections in Equation 11. Let

C^{0} ⟶^{p̄^{1}} C^{1} ⟶^{p̄^{2}} C^{2} ⋯

be the sequence of projections and let (a^{k}, b^{k}) ∈ (E_{m−1}^{k}, E_{m}^{k}) be the reduced pairs of generators for a fixed m. Let z^{k} be defined by

z^{0} := z , z^{k} := p̄^{k}z^{k−1}, k = 1, 2, …

Since each projection is a chain map, each z^{k} is a cycle. Thus by Lemma 4.12

z^{k−1} − z^{k} = ∂(α_{k}λ_{k}^{−1}b^{k−1})  (25)

for some λ_{k} ≠ 0 and some α_{k} (possibly equal to 0 but then z^{k−1} = z^{k}). We construct a sequence of chains c^{k} ∈ C_{m}, k = 0, 1, 2, … as follows.

c^{0} := 0 , c^{k} := c^{k−1} + α_{k}λ_{k}^{−1}b^{k} , k = 1, 2, …  (26)

It follows from Equations 25 and 26 by induction that

z − z^{k} = ∂c^{k} ,  (27)

By the same argument as in discussion following Equation 11, there is a finite element C^{f_{m}} in the sequence beyond which the construction in this dimension cannot be extended and then ∂_{m}^{f_{m}} = 0 where ∂^{k} = 0 is the restriction of ∂ to C^{k}. Since C is acyclic, by the proof of Theorem 3.8, C^{f_{m}} is acyclic too. Since ∂_{m}^{f_{m}} = 0, we have ker ∂_{m−1}^{f_{m}} = im ∂_{m}^{f_{m}} = 0 hence z^{f_{m}} = 0. From Equation 27 we get the following Theorem 4.14. ∂c^{f_{m}} = z.

The algorithm based on the above construction is presented in [12]. We do not expect that our algorithm, in its most general setting, is more efficient that standard linear algebra programs applied for Equation 24. We expect however that the geometric flavor of our algorithm will help to render it more efficient in particular cases of chain complexes coming from applications. This was the case with the coboundary algorithm for cycles in a rectangular set presented in [3]. Let us briefly describe how the improvement is reached there.

Let R be a representable rectangle in R^{d}, i.e. a product of intervals with integer coordinates and C := C(R) be the cubical complex of X. The geometric algorithm of finding a coboundary of an (m − 1)-cycle z given in [3] is based on the recurrence with respect to the dimension d of R. Here is the main idea of the recurrence step. Let R′ be a (d − 1)-dimensional face of X. The orthogonal projection of R onto R′ induces, in an evident way, a projection p : C(R) → C(R′) which is orthogonal with respect to the canonical basis of C(R) consisting of unitary cubes. We let z′ := pz and compute Cob (z′). Then Cob (z) is obtained by adding to Cob (z′) all m-dimensional unitary cubes through which z is projected (we may visualize them as side-walls of the projection cylinder), with some care about signs of coefficients. It is visible that this construction may be viewed as a major shortcut of what we presented here. Instead of projecting in small steps through one elementary cube per time, we get the whole cylinder enclosed between a face e ∈ E_{m−1}(z) and a corresponding face of z′, in a single operation of replacing an endpoint by an interval in the expression of e as a product of intervals. Due to this simplification, the complexity of the algorithm in [3] is linear with respect to the number of elements of E_{m−1}(z) provided an arithmetics on elementary cubes is introduced in a way which permits a convenient presentation of the output. Cubical complexes are very particular but we believe that those type of shortcuts in our universal algorithm will be possible in many situations when a subdivision of a space to cells is chosen in a ”custom-fit” way.

We refer the reader to [12] for further discussion of cases when the efficiency of the reduction algorithm can be improved.

References

[1] M. Allili, Une approche algorithmique pour le calcul de l’homologie de fonctions continues, Ph.D. thesis, Dép. de math. et d’info., Univ. de Sherbrooke, Sherbrooke 1999.

[2] M. Allili and T. Kaczynski, An algorithmic approach to the construction of homomorphisms induced by maps in homology, Trans. Amer. Math. Soc., 352 (2000), 2261-2281.

[3] M. Allili and T. Kaczynski, Geometric construction of a coboundary of a cycle, Discrete & Comp. Geometry, 25 (2001), 125-140.

[4] A. Bovick, ed., Handbook of Image & Video Processing, Academic Press, 2000.

[5] Dao Trong Thi and A. T. Fomenko, Minimal Sufaces, Stratified Multivarifold and the Plateau Problem, Transl. of Math. Monographs Vol 84, Amer. Math. Soc. 1991.

[6] C. J. A. Delfinado and H. Edelsbrunner, An incremental algorithm for Betti numbers of simplicial complexes on the 3-sphere, Computer Aided Geometric Design 12 (1995), 771-784.

[7] T. K. Dey, H. Edelsbrunner and S. Guha, Computational topology, in Advances in Computational and Discrete Geometry (South Hadley, Ma, 1996) Contemp. Math. 223, AMS Providence 1999, 109-143.

[8] R. Ehrenborg and G. Hetyei, Generalizations of Baxter’s Theorem and Cubical Homology, J. Combinatorial Theory, Series A, 69 (1995), 233-287.

[9] R. Gonzalez-Diez and P. Real, Computation of cohomology operations on finite simplicial complexes. preprint.

[10] L. Górniewicz, Homological Methods in Fixed Point Theory of Multi-Valued Maps, Dissertationes Math. (129), PWN Warsaw 1976.

[11] C .S. Illiopoulos, Worst case complexity bounds on algorithms for computing the canonical structure of finite abelian groups and Hermite and Smith normal form of an integer matrix, SIAM J. Computing 18 (1989), 658-669.

[12] T. Kaczynski, Recursive Coboundary Formula for Cycles in Acyclic Chain Complexes, Top. Meth. Nonlin. Anal. Appl., 18 (2)(2002), 351-372.

[13] T. Kaczynski, K. Mischaikow, and M. Mrozek, Computational Homology, book in progress.

[14] T. Kaczynski, M. Mrozek, and M. Ślusarek, Homology computation by reduction of chain complexes, Computers and Math. Appl. 35 (1998), 59-70.

[15] W. Kalies, K. Mischaikow, and G. Watson, Cubical approximation and computation of homology, Conley Index Theory (eds. K. Mischaikow, M. Mrozek, and P. Zgliczyński), Banach Center Publications 47 Warsaw (1999), 115-131.

[16] W. S. Massey, A Basic Course in Algebraic Topology, Springer-Verlag, New York 1991.

[17] M. Mazur, J. Szybowski, Algorytm Allili-Kaczynskiego Konstrukcji Homomorfizmu £ańcuchowego Generowanego Przez Odwzorowanie Wielowartościowe Reprezentowalne, M.Sc. Diss. (in polish), Comp. Sci. Inst., Jagellonian Univ. Krakow 1999.

[18] K. Mischaikow, Topological techniques for efficient rigorous computation in dynamics, Acta Numerica 11 Cambridge Univ. Press (2002) 435-478.

[19] K. Mischaikow, M. Mrozek, J. Reiss and A. Szymczak, Construction of Symbolic Dynamics from Experimental Time Series, Physical Review Letters, 82(1999), 1144-1148.

[20] K. Mischaikow and M. Mrozek, Conley Index, in Handbook of Dynamical Systems, (B. Fiedler, ed.) North-Holland (2002) 393-460.

[21] M. Mrozek, Topological invariants, multivalued maps and computer assisted proofs, Computers and Math. Appl. 32(1996),83-104.

[22] M. Mrozek, An algorithmic approach to the Conley index theory, J. Dyn. Diff. Equ., 11(1999), 711-734.

[23] M. Mrozek, Čech Type Approach to Computing Homology of Maps, in preparation.

[24] J. R. Munkres, Elements of Algebraic Topology, Addison-Wesley 1984.

[25] P. Pilarczyk, Algorithmic homology computation over a Euclidean domain, preprint Comp. Sci. Inst. Jagellonian Univ. Krakow 2000.

This article may be accessed via WWW at http://www.rmi.acnet.ge/hha/ or by anonymous ftp at

ftp://ftp.rmi.acnet.ge/pub/hha/volumes/2003/n2a8/v5n2a8.(dvi,ps,pdf)

Tomasz Kaczynski kaczyn@dmi.usherb.ca

Département de mathématiques et d’informatique Université de Sherbrooke Sherbrooke, Québec, Canada J1K 2R1

Konstantin Mischaikow mischaik@math.gatech.edu

Center for Dynamical Systems and Nonlinear Studies School of Mathematics Georgia Institute of Technology Atlanta, GA 30332-0190

Marian Mrozek mrozek@ii.uj.edu.pl

Institute of Computer Science Jagiellonian University ul. Nawojki 11 PL-30-072 Kraków, Poland