Computational discrete Morse theory

Abstract

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.

Basierend auf Formans diskreter Morse Theorie schlage ich in meiner Doktorarbeit einen allgemeinen algorithmischen Ansatz zur Datenanalyse in einer graphentheoretischen Formulierung vor. Dieser rein kombinatorische Ansatz erlaubt es, die extremale Struktur von Skalarfeldern und Vektorfeldern, welche auf diskrete Mannigfaltigkeiten definiert sind, zu extrahieren. Die extremale Struktur von einem Skalarfeld besteht aus kritischen Punkten und Separatrizen -- bestimmte Tangentialkurven des Gradientenfelds, die die kritischen Punkte verbinden. Die extremale Struktur von Vektorfeldern beinhaltet zusätzlich periodische Orbits -- die geschlossenen Tangentialkurven des Vektorfelds. Diese Merkmale sind in vielen Anwendungen von großem Interesse, da sie es ermöglichen, große Datensätze auf ihre essentielle Struktur zu reduzieren. Eine Herausforderung für klassische numerische Algorithmen stellt die diskrete Natur der extremalen Struktur dar, welche eine große Zahl von Binärentscheidungen bedingt. Das Ergebnis solcher Methoden hängt daher stark von der Wahl der Berechnungsparameter ab. Die Morse Theorie setzt die extremale Struktur einer generischen Funktion zu der Topologie der Mannigfaltigkeit in Beziehung, z.B. im Poincare-Hopf Theorem. Unter Umständen können klassische numerische Methoden daher unzulässige Ergebnisse erzeugen. Robin Forman hat eine diskrete Version von der Morse Theorie entwickelt. Diese Version kann als eine Diskretisierung der zulässigen extremalen Strukturen einer diskreten Mannigfaltigkeit interpretiert werden. Die Grundidee meines allgemein algorithmischen Ansatzes zur Datenanalyse ist es, ein kombinatorisches Optimierungsproblem über die Menge der zulässigen extremalen Strukturen zu definieren. Das Ergebnis dieses Ansatzes ist daher immer konsistent in Bezug auf die Topologie von dem Definitionsgebiet. Zusätzlich definiert die Lösung des Optimierungsproblems eine natürliche Hierarchie der extremalen Struktur des Datensatzes. Diese Hierarchie kann benutzt werden, um die von eventuell vorhandenem Rauschen induzierte extremale Struktur zu entfernen, oder, um ausschließlich die essentielle extremale Struktur eines Datensatzes zu extrahieren. Im Kontext dieses allgemeinen Ansatzes wurden effiziente Algorithmen entwickelt und ihre Anwendbarkeit wurde für zweidimensionale Skalarfelder, divergenzfreie Vektorfelder, allgemeine Vektorfelder und zeitabhängige Skalarfelder, untersucht. Die Praxistauglichkeit dieses kombinatorischen Ansatzes zur Datenanalyse wird weiterhin substantiviert durch Anwendungen in der Fluiddynamik und als Ausgangspunkt für ein globales Wichtigkeitsmaß für kritische Punkte. Zusätzlich wurde dieser Ansatz auf dreidimensionale Skalarfelder erweitert und diente als Basis für eine Speicherplatz effiziente Berechnung von persistenter Homologie.