Title: |
Discrete Morse Theory as a Preprocessing Tool for Computing Homology |

Speaker: |
Konstantin Mischaikow (Rutgers University) |

Abstract: |
Because of its computability, homology is a powerful tool for classifying and characterizing nonlinear objects and functions. There is considerable activity at the moment towards the application of ideas from algebraic topology to the analysis of nonlinear data sets obtained either through experiments or numerical simulations. However, there are at least two fundamental difficulties in computing homology efficiently in this context. First, Smith Normal Form lies at the core of most computations of homology and the optimal worst case complexity bounds for computing Smith Normal Form are super cubic. Second, the cost of computing grows rapidly with dimension.
I will begin this talk with specific examples of data sets which are being analyzed using homology. I will discuss the use of discrete Morse theory as a preprocessing tool for homology computations. In particular, I will discuss how it can be used to produce smaller complexes with the same homological invariants and how it can be used in some special cases to avoid higher dimensional computations. |