Introduction to Homology Bill Kalies Computational Homology and Fluid Dynamics Workshop Georgia Institute of Technology March 2007 Homology of topological spaces Computing homology Topological analysis of patterns Homology of continuous maps The plan What is homology? Homology is a tool to measure connectivity and holes in a topological space. How can we distinguish (computationally) between a cylinder, sphere, and torus? Topological space Combinatorial description = Cellular decomposition e.g. triangles or cubes (linear) Algebra From combinatorics to algebra: the (cubical) boundary operator e B A e f h g S e f h g A B C D e B A f C g D h E A boundary is a chain B for which there is a chain such that . An -chain is a sum of -dimensional cells. Chains, cycles, and boundaries A cycle is a chain whose boundary . Two cycles and are homologous if they differ by a boundary, i.e. there exists a chain such that . I J K I , J , and K are cycles. K is a boundary, but I and J are not. I and J are homologous, but K is not homologous to I or J . -homology The set of all -cycles and the set of all -boundaries are vector spaces over . Since , we have . The homology is then deﬁned by . The homology of a space is a sequence of vector spaces. A choice of basis elements for are called -generators. Homology generators Betti numbers The dimensions of the vector spaces are the Betti numbers . The Betti numbers represent the number of non-homologous cycles which are not boundaries = “ -dimensional holes”. the zeroth Betti number, , counts the number of connected components , the ﬁrst Betti number, , counts the number of tunnels , and In 3-dimensional complexes made from full 3-dimensional cubes: the second Betti number, , counts the number of enclosed cavities . Examples Euler characteristic The Euler characteristic of a cellular complex is a topological invariant which for 2-dimensional complexes is deﬁned by The Euler characteristic can be recovered from the Betti numbers by 3d - Cahn-Hilliard nodal domain The Betti numbers are: This space is connected, has no enclosed cavities, and has tunnels. 1059 Computing Homology The textbook method is to perform row and column operations on the boundary operator to obtain Smith Normal Form . For ﬁeld coefﬁcients, this algorithm has cubic complexity and higher complexity for integer coefﬁcients. In practice it is OK for complexes with hundreds cubes. Better results can be obtained from reduction algorithms . These algorithms reduce the size of the chain complexes without changing the homology. Elementary collapses Free face collapse involves an n-cube P which is the face of exactly one (n+1)-cube Q. Both P and Q can be removed without changing homology. P P Q Q Elementary collapses Q If a complex is the union of top-dimensional cubes, one can remove such a full cube Q if the complex composed of the neighboring cubes has trivial homology. These reductions are linear and the reduced complex is often much smaller! In 2 and 3 dimensions, lookup tables for all possible neighbor conﬁgurations have been computed. We are working on a 4-dimensional lookup table. Why cubes? Homology can be computed for simplicial complexes as well as other cellular decompositions. There are several advantages to regular cubical complexes. The geometry of neighboring cubes and faces is simple. This leads to very efﬁcient storage of complexes in bitmaps or binary trees and to look-up tables for geometric reductions. Often cubes are more natural for a given application. E.g. in images pixels or voxels = cubes, and numerical simulations are often done on rectangular grids. The projection of a cubical complex onto a coordinate hyperplane is a cubical complex. Reduction Algorithms and their implementations • Free face collapses algorithm (Mischaikow, Mrozek, 1993) • Algebraic elementary reductions algorithm (Kaczynski, Mrozek, Slusarek, 1998) • Geometrically controlled algebraic reductions (Kalies, Mischaikow, Watson, 1999) – [BK] W.D. Kalies (1999-2005, available from CHomP web page) • Acyclic intersection algorithm (Pilarczyk, 2001) – [PP] P. Pilarczyk (1999-2005, available from CHomP web page) • Lookup tables in dimension 3 (Szymczak, 2003) • Acyclic intersection algorithm via lookup tables and decision trees in dimension 3 (Gameiro, Kalies, Pilarczyk, 2005) – [BKLT] Gameiro, Kalies, Nanda, Szymczak 2005 • Algebraically controlled algebraic reductions (Mrozek, Slusarek 2005) – [AR] M. Mrozek, 2005 • Acyclic subspace algorithm (Mrozek, Pilarczyk, Zaremba, 2005) – [ASLT] M. Mrozek, 2005 – [ASPP] P. Pilarczyk, 2005 • Free coface collapses algorithm (Mrozek, Batko, 2005) – [CR] M. Mrozek, 2005 Slide courtesy of Marian Mrozek. Betti numbers of patterns 1. From experimental data as pixelated images or numerical data from rectangular grids, take snapshots in time. 2. Threshold each snapshot to extract some feature / pattern to obtain a sequence of cubical complexes (each pixel / grid element is a cube.) 3. Compute Betti numbers for each cubical complex to obtain a time series. 4. Does this time series provide any information about the dynamics. Numerical data: 2d-Cahn-Hilliard Time series of Betti numbers: Cahn-Hilliard Gameiro, Mischaikow, and Wanner Experimental data: Rayleigh-Benard convection Spiral defect chaos Courtesy M. Schatz, Georgia Institute of Technology Krishan, Gameiro, Mischaikow, and Schatz Time series of Betti numbers: Rayleigh-Benard Time series of Betti numbers: Rayleigh-Benard FitzHugh-Nagumo equations Numerical data: FitzHugh-Nagumo Spiral waves : spatial-temporal chaos Time series of Betti numbers: FitzHugh-Nagumo Gameiro, Kalies, and Mischaikow Lyapunov exponents for FitzHugh-Nagumo Mean of ﬁrst Betti number for FitzHugh-Nagumo Homology maps A continuous map induces a linear transformation on homology. The deﬁnition of this transformation is simple when maps cubes to cubes. Otherwise the map must ﬁrst be approximated by a cubical map. Homology maps can be useful in comparing topologies, especially inclusion, projection, and translation maps. Slide courtesy of Marian Mrozek. Slide courtesy of Marian Mrozek. Slide courtesy of Marian Mrozek. Slide courtesy of Marian Mrozek. Slide courtesy of Marian Mrozek. Slide courtesy of Marian Mrozek. Slide courtesy of Marian Mrozek. Slide courtesy of Marian Mrozek.