Computational Homology

Homology is a very powerful tool in that it allows one to draw conclusions about global properties of spaces and maps from local computations. It also involves a wonderful mixture of algebra, combinatorics, computation, and topology. Each of these subjects is, of course, interesting in its own right and appears as the subject of multiple sections in this book. But our primary objective is to see how they can be combined to produce homology, how homology can be computed efficiently, and how homology provides us with information about the geometry and topology of nonlinear objects and functions. Given the amount of theory that needs to be developed, it is easy to lose sight of these objectives along the way.

In Chapter 1 we have provided a heuristic introduction to homology using graphs that are made up of vertices (zero-dimensional cubes) and edges (one-dimensional cubes). Before that we motivated the need for a computational theory of homology using examples from image processing where it was natural to think of the images as being presented in terms of pixels (two-dimensional cubes), voxels (three-dimensional cubes), and even tetrapus (four-dimensional cubes). In Section 2.1 we formalize and generalize these examples to cubical complexes.

In light of the discussion of the previous chapter, given a cubical set X we know that its homology groups H_*(X) are well defined. We have also computed H_*(X) for some simple examples and discussed the method of elementary collapse, which can be used in special cases to compute these groups. In this chapter we want to go further and argue that the homology groups of any cubical set are computable. In fact, we will derive Algorithm 3.78, which, given a cubical set X, takes as input the list of all elements of K_max(X) and as output presents the associated homology groups H_*(X). While the input is well defined, how to present the output may not be so clear at this moment. Obviously, we need to obtain a set of abelian groups. However, for this to be of use we need to know that we can present these groups in a finite and recognizable form. In particular, if X and Y are two cubical sets, it is desirable that our algorithm outputs the groups H_*(X) and H_*(Y) in such a way that it is evident whether or not they are isomorphic. With this in mind, by the end of this chapter we will prove the following result.

Consider two cubical sets X and Y. In Chapter 2 we have studied the associated homology groups H_*(X) and H_*(Y). Now assume that we are given a continuous map f: X → Y. It is natural to ask if f induces a group homomorphism f_*: H_*(X) → H_*(Y). If so, do we get useful information out of it? The answer is yes and we will spend the next three chapters explaining how to define and compute f_*. It is worth noting, even at this very preliminary stage, that since H_*(X) and H_*(Y) are abelian groups, f_* is essentially a linear map and therefore, from the algebraic point of view, easy to use.

In Chapter 5 we have provided a preview of the issues involved in defining homology of maps. In this chapter we revisit this material, but in a rigorous and dimension-independent manner. We begin with the introduction of representable sets. These are sets that can be constructed using elementary cells and represent a larger class than that of cubical sets. This extra flexibility is used in Section 6.2 to construct cubical multivalued maps. As described in Section 5.2, these multivalued maps provide representations of the continuous function for which we wish to compute the homology map. Section 6.3 describes the process by which one passes from the cubical map to a chain map from which one can define a map on homology. Section 6.4 shows that applying the above-mentioned steps (plus perhaps rescaling) to a continuous function leads to a well-defined map on homology. Finally, in the last section, we address the question of when do two different continuous maps give rise to the same map on homology.

In Chapter 6 we have provided a theoretical construction for producing a homology map f_*: H_*(X) → H_*(Y) given an arbitrary continuous function f: X → Y between cubical sets X ⊂ R ^d and Y ⊂ R ^d’ . In this chapter we provide algorithms that allow us to use the computer to obtain f_*.

In Chapter 1 we consider digital images to motivate the use of cubical complexes as the geometric building blocks of homology. As a concrete example we discuss the image of the Sea of Tranquillity (see Figure 1.5). However, such a complicated image and the discussion surrounding it can mask some of the even more elementary difficulties in the process of analog to digital conversion. Since the focus of this book is on computational homology, we will show that it is easy for pixel data to produce the wrong topological information.

We finished the previous chapter with the observation that given a space X and a subset A it would be useful to have a means of computing the number of components of X that are disjoint from A. Using this as motivation, in Section 9.1 we introduce the concept of relative homology. Though motivated by a simple problem, it turns out that relative homology is an extremely powerful tool, both as a means of extracting topology from the homological algebra and as an abstract computational technique. The language of these computational methods takes the form of exact sequences, which are discussed in Section 9.2.

This is perhaps the most challenging chapter of this book in that we attempt to show how homology can be used in nonlinear analysis and dynamical systems. As mentioned in the Preface, algebraic topology was developed to solve problems in these subjects. Thus, on one hand, some of the material (most notably Sections 10.4 and 10.5) is classical and has a rich history. On the other hand, the focus of Section 10.6, combining numerical analysis with homology via the computer to obtain mathematically rigorous results, is a cutting-edge topic. We assume that the background and interest of our readers are equally varied, ranging from an individual with no background in dynamics hoping to learn the mathematical theory to others whose primary goal is to understand how to apply these ideas to specific nonlinear systems.

We have presented in this book a theory of cubical homology. Our justification for this approach lies in the applications described in Chapters 1, 8, and 10, where we are required to work with large sets of data and for which we need a computationally effective means of computing homology. In all these examples the data itself naturally generates cubical sets. However, this cubical homology theory is unconventional, and furthermore, there is a wide variety of other homology theories available.

In this chapter we provide a brief presentation of topological preliminaries. The matters discussed here can be found in most standard topology textbooks or in topology chapters in analysis textbooks. Among recommended complementary references are Munkres [68] and Rudin [76].

We provide in this chapter a brief presentation of algebraic preliminaries. The matters discussed here can be found in most of standard textbooks on either abstract algebra or linear algebra. The book by S. Lang [47] is a recommended complementary reference.

In this chapter we describe the language we use in this book to present algorithms. The language we have chosen does not represent any particular programming language, because we do not want to delve too deeply into the technicalities involved in preparing a concrete computer program. The langauge we use is a combination of features found in present-day programming languages which we feel are most useful to keep the presentation reasonably detailed but simple. A person with some experience in programming should have no problem in rewriting our algorithms in a concrete programming language.