Speaker: Konstantin Mischaikow, Rutgers University
Title: Computing Homology via Preprocessing by Morse Coreduction
Abstract: Over the past two decades algebraic topology, especially in the form of homology, has become a popular tool for the analysis of high dimensional data sets and the rigorous analysis of nonlinear systems. For large data sets or high dimensional systems computing homology of complexes and the maps on homology induced by continuous functions is a nontrivial task both in terms of computational cost and memory.
An essential step in the computation of homology over the integers is the use of
the Smith Normal Form. Unfortunately, the complexity estimates for the general purely algebraic algorithms are super cubical in the number of cells in the complex.
The strategy which will be discussed in this talk starts from the perspective that
we have geometric information about our complexes and maps and that we can use this information to preprocess the geometric complex making it smaller.
The preprocessing techniques that we use are based on coreduction and discrete Morse theory, which will be explained.
Time: Friday, February 25, 2011, 1:30-2:30 p.m.
Place: Science and Tech I, Room 242
Department of Mathematical Sciences
George Mason University
4400 University Drive, MS 3F2
Fairfax, VA 22030-4444
Tel. 703-993-1460, Fax. 703-993-1491