Computational discrete Morse theory
Jan Reininghaus · Universitätsbibliothek der FU Berlin Hochschulschriftenstelle u. Dokumentenserver · 2012
I propose a purely combinatorial framework that allows to extract the extremal structure of scalar and vector fields defined on discrete manifolds. The extremal structure of a scalar field consists of critical points and separatrices - certain tangential curves of the gradient field that connect critical points. The extremal structure of a vector field additionally includes periodic orbits - the tangential curves that are closed. These features are of great interest in many applications since they allow to reduce large data sets to their essential structure. One of the biggest challenges for classical numerical algorithms is the discrete nature of the extremal structure which necessitates a lot of binary decisions. Their result therefore strongly depends on computational parameters. Since Morse theory relates the extremal structure of a generic function to the topology of the manifold, e.g. by the Poincare-Hopf Theorem, such numerical methods may thereby compute inadmissible results. Robin Forman has developed a discrete version of Morse theory. This theory can be seen as a discretization of the set of admissible extremal structures for a given manifold. In my thesis I propose a general computational framework for data analysis which is based on Forman's discrete Morse theory in a graph theoretical formulation. The basic idea is to define a combinatorial optimization problem over the set of admissible extremal structures. The result of this framework is thereby provably consistent with the topology of the domain. Also, the solution of the optimization problem gives rise to a natural hierarchy of extremal structures for a given data set. This hierarchy can be used to remove noise induced extremal structure or to extract its essential extremal structure. In the context of this unified framework I have developed efficient algorithms and investigated their applicability in 2D for scalar fields, divergence-free vector fields, general vector fields, and time-dependent scalar fields. Subsequently, this framework has been applied for the analysis of fluid dynamics and for the computation of a global importance measure for critical points. It has also been extended to 3D scalar fields and employed for a memory efficient computation of persistent homology.