close

Вход

Забыли?

вход по аккаунту

?

Introduction to Homology kalies

код для вставкиСкачать
Bill Kalies. Introduction to Homology
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 defined 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 first 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 defined 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 field coefficients, this algorithm has cubic complexity and higher complexity for integer coefficients. 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 configurations 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 efficient 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 first Betti number for FitzHugh-Nagumo
Homology maps
A continuous map induces a linear transformation on homology.
The definition of this transformation is simple when maps cubes to cubes. Otherwise the map must first 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.
Автор
iknyazeva
Документ
Категория
Наука
Просмотров
129
Размер файла
6 315 Кб
Теги
computational topology
1/--страниц
Пожаловаться на содержимое документа