Synopses & Reviews
In recent years, there has been a growing interest in applying homology to problems involving geometric data sets, whether obtained from physical measurements or generated through numerical simulations. This book presents a novel approach to homology that emphasizes the development of efficient algorithms for computation. As well as providing a highly accessible introduction to the mathematical theory, the authors describe a variety of potential applications of homology in fields such as digital image processing and nonlinear dynamics. The material is aimed at a broad audience of engineers, computer scientists, nonlinear scientists, and applied mathematicians. Mathematical prerequisites have been kept to a minimum and there are numerous examples and exercises throughout the text. The book is complemented by a website containing software programs and projects that help to further illustrate the material described within.
Review
From the reviews: "...This is an interesting and unusual book written with the intention of serving several purposes. One of them is to demonstrate that methods of algebraic topology, in particular homology theory, that have proved remarkably successful in several areas of pure mathematics can provide powerful, and in some cases indispensable, tools in a number of areas of applied mathematics and science. The second is to provide the necessary theory and "technology" for such applications. This means on the one hand providing all the necessary mathematical foundations of the subject, including definitions and theorems, and on the other hand efficient computational techniques capable of dealing with real life situations. Thus, the book stresses algorithmic and computational approaches; and in fact includes computer code written in a programming language specially designed for this purpose. It is addressed to a varied audience of computer scientists, experimental scientists and engineers while at the same time trying to retain the interest of mathematicians. With this in mind the authors have attempted to produce a modular book, which allows a number of different reading approaches. The basic subdivision of the book is into three parts. The last part contains all the basic pre-requisites from algebra and topology: the most essential facts about Euclidean spaces, point set topology, abelian groups, vector spaces and matrix algebras. This part also contains a description of the programming language used to describe the algorithms found in the book..." --MATHEMATICAL REVIEWS "This is an interesting and unusual book with the intention of serving several purposes. One of them is to demonstrate that methods of algebraic topology, in particular homology theory ... . The second is to provide the necessary theory and 'technology' for such applications. ... the book admirably achieves all its stated purposes. In addition it will provide much needed ammunition for those algebraic topologists who have been feeling besieged by allegations of their subject's lack of 'useful' applications." (Andrzej Kozlowski, Mathematical Reviews, 2005g) "This book provides the conceptual background for computational homology - a powerful tool used to study the properties of spaces and maps that are insensitive to small perturbations. The material presented here is a unique combination of current research and classical rigor, computation and application." (Corina Mohorianu, Zentralblatt Mathematik, Vol. 1039 (8), 2004) "In addition to developing a computational homology theory which produces efficient algorithms, the authors demonstrate how these algorithms can be applied to a variety of problems ... . I certainly recommend Computational Homology to mathematicians and applied scientists who wish to learn about the potential of algebraic topological methods. ... this book is the first comprehensive effort to describe the computational aspects of homology theory ... . It is written at a level that is suitable for advanced undergraduate and early graduate courses ... ." (Thomas Wanner, SIAM Review, Vol. 48 (1). 2006) "This is the first textbook on what is necessarily a mixture of classical mathematics, computer science, and applications. ... it is a unique feature of Computational Homology that every geometric step, however conceptually simple, is broken down into elementary operations. ... The book offers a reliable yet practical introduction to (cubical homology), with a strong emphasis on computational aspects. Hands-on experience can be gained through the many problems within the book and also by means of the software packages ... ." (Arno Berger, Zeitschrift für Angewandte Mathematik und Mechanik, Vol. 86 (4). 2006)
Review
From the reviews:
"...This is an interesting and unusual book written with the intention of serving several purposes. One of them is to demonstrate that methods of algebraic topology, in particular homology theory, that have proved remarkably successful in several areas of pure mathematics can provide powerful, and in some cases indispensable, tools in a number of areas of applied mathematics and science. The second is to provide the necessary theory and "technology" for such applications. This means on the one hand providing all the necessary mathematical foundations of the subject, including definitions and theorems, and on the other hand efficient computational techniques capable of dealing with real life situations. Thus, the book stresses algorithmic and computational approaches; and in fact includes computer code written in a programming language specially designed for this purpose. It is addressed to a varied audience of computer scientists, experimental scientists and engineers while at the same time trying to retain the interest of mathematicians. With this in mind the authors have attempted to produce a modular book, which allows a number of different reading approaches. The basic subdivision of the book is into three parts. The last part contains all the basic pre-requisites from algebra and topology: the most essential facts about Euclidean spaces, point set topology, abelian groups, vector spaces and matrix algebras. This part also contains a description of the programming language used to describe the algorithms found in the book..." --MATHEMATICAL REVIEWS
"This is an interesting and unusual book with the intention of serving several purposes. One of them is to demonstrate that methods of algebraic topology, in particular homology theory ... . The second is to provide the necessary theory and 'technology' for such applications. ... the book admirably achieves all its stated purposes. In addition it will provide much needed ammunition for those algebraic topologists who have been feeling besieged by allegations of their subject's lack of 'useful' applications." (Andrzej Kozlowski, Mathematical Reviews, 2005g)
"This book provides the conceptual background for computational homology - a powerful tool used to study the properties of spaces and maps that are insensitive to small perturbations. The material presented here is a unique combination of current research and classical rigor, computation and application." (Corina Mohorianu, Zentralblatt Mathematik, Vol. 1039 (8), 2004)
"In addition to developing a computational homology theory which produces efficient algorithms, the authors demonstrate how these algorithms can be applied to a variety of problems ... . I certainly recommend Computational Homology to mathematicians and applied scientists who wish to learn about the potential of algebraic topological methods. ... this book is the first comprehensive effort to describe the computational aspects of homology theory ... . It is written at a level that is suitable for advanced undergraduate and early graduate courses ... ." (Thomas Wanner, SIAM Review, Vol. 48 (1). 2006)
"This is the first textbook on what is necessarily a mixture of classical mathematics, computer science, and applications. ... it is a unique feature of Computational Homology that every geometric step, however conceptually simple, is broken down into elementary operations. ... The book offers a reliable yet practical introduction to (cubical homology), with a strong emphasis on computational aspects. Hands-on experience can be gained through the many problems within the book and also by means of the software packages ... ." (Arno Berger, Zeitschrift für Angewandte Mathematik und Mechanik, Vol. 86 (4). 2006)
Synopsis
Homology is a powerful tool used by mathematicians to study the properties of spaces and maps that are insensitive to small perturbations. This book uses a computer to develop a combinatorial computational approach to the subject. The core of the book deals with homology theory and its computation. Following this is a section containing extensions to further developments in algebraic topology, applications to computational dynamics, and applications to image processing. Included are exercises and software that can be used to compute homology groups and maps. The book will appeal to researchers and graduate students in mathematics, computer science, engineering, and nonlinear dynamics.
Table of Contents
Preface
Part I Homology
1 Preview
1.1 Analyzing Images
1.2 Nonlinear Dynamics
1.3 Graphs
1.4 Topological and Algebraic Boundaries
1.5 Keeping Track of Directions
1.6 Mod 2 Homology of Graphs
2 Cubical Homology
2.1 Cubical Sets
2.1.1 Elementary Cubes
2.1.2 Cubical Sets
2.1.3 Elementary Cells
2.2 The Algebra of Cubical Sets
2.2.1 Cubical Chains
2.2.2 Cubical Chains in a Cubical Set
2.2.3 The Boundary Operator
2.2.4 Homology of Cubical Sets
2.3 Connected Components and H0(X)
2.4 Elementary Collapses
2.5 Acyclic Cubical Spaces
2.6 Homology of Abstract Chain Complexes
2.7 Reduced Homology
2.8 Bibliographical Remarks
3 Computing Homology Groups
3.1 Matrix Algebra over Z
3.2 Row Echelon Form
3.3 Smith Normal Form
3.4 Structure of Abelian Groups
3.5 Computing Homology Groups
3.6 Computing Homology of Cubical Sets
3.7 Preboundary of a Cycle-Algebraic Approach
3.8 Bibliographical Remarks
4 Chain Maps and Reduction Algorithms
4.1 Chain Maps
4.2 Chain Homotopy
4.3 Internal Elementary Reductions
4.3.1 Elementary Collapses Revisited
4.3.2 Generalization of Elementary Collapses
4.4 CCR Algorithm
4.5 Bibliographical Remarks
5 PreviewofMaps
5.1 Rational Functions and Interval Arithmetic
5.2 Maps on an Interval
5.3 Constructing Chain Selectors
5.4 Maps of A1
6 Homology of Maps
6.1 Representable Sets
6.2 Cubical Multivalued Maps
6.3 Chain Selectors
6.4 Homology of Continuous Maps
6.4.1 Cubical Representations
6.4.2 Rescaling
6.5 Homotopy Invariance
6.6 Bibliographical Remarks
7 Computing Homology of Maps
7.1 Producing Multivalued Representation
7.2 Chain Selector Algorithm
7.3 Computing Homology of Maps
7.4 Geometric Preboundary Algorithm (optional section)
7.5 Bibliographical Remarks
Part II Extensions
8 Prospects in Digital Image Processing
8.1 Images and Cubical Sets
8.2 Patterns from Cahn-Hilliard
8.3 Complicated Time-Dependent Patterns
8.4 Size Function
8.5 Bibliographical Remarks
9 Homological Algebra
9.1 Relative Homology
9.1.1 Relative Homology Groups
9.1.2 Maps in Relative Homology
9.2 Exact Sequences
9.3 The Connecting Homomorphism
9.4 Mayer-Vietoris Sequence
9.5 Weak Boundaries
9.6 Bibliographical Remarks
10 Nonlinear Dynamics
10.1 Maps and Symbolic Dynamics
10.2 Differential Equations and Flows
10.3 Wayzewski Principle
10.4 Fixed-Point Theorems
10.4.1 Fixed Points in the Unit Ball
10.4.2 The Lefschetz Fixed-Point Theorem
10.5 Degree Theory
10.5.1 Degree on Spheres
10.5.2 Topological Degree
10.6 Complicated Dynamics
10.6.1 Index Pairs and Index Map
10.6.2 Topological Conjugacy
10.7 Computing Chaotic Dynamics
10.8 Bibliographical Remarks
11 Homology of Topological Polyhedra
11.1 Simplicial Homology
11.2 Comparison of Cubical and Simplicial Complexes
11.3 Homology Functor
11.3.1 Category of Cubical Sets
11.3.2 Connected Simple Systems
11.4 Bibliographical Remarks
Part III Tools from Topology and Algebra
12 Topology
12.1 Norms and Metrics in Rd
12.2 Topology
12.3 Continuous Maps
12.4 Connectedness
12.5 Limits and Compactness
13 Algebra
13.1 Abelian Groups
13.1.1 Algebraic Operations
13.1.2 Groups
13.1.3 Cyclic Groups and Torsion Subgroup
13.1.4 Quotient Groups
13.1.5 Direct Sums
13.2 Fields and Vector Spaces
13.2.1 Fields
13.2.2 Vector Spaces
13.2.3 Linear Combinations and Bases
13.3 Homomorphisms
13.3.1 Homomorphisms of Groups
13.3.2 Linear Maps
13.3.3 Matrix Algebra
13.4 Free Abelian Groups
13.4.1 Bases in Groups
13.4.2 Subgroups of Free Groups
13.4.3 Homomorphisms of Free Groups
14 Syntax of Algorithms
14.1 Overview
14.2 Data Structures
14.2.1 Elementary Data Types
14.2.2 Lists
14.2.3 Arrays
14.2.4 Vectors and Matrices
14.2.5 Sets
14.2.6 Hashes
14.3 Compound Statements
14.3.1 Conditional Statements
14.3.2 Loop Statements
14.3.3 Keywords break and next
14.4 Function and Operator Overloading
14.5 Analysis of Algorithms
References
Symbol Index.
Subject Index