Invarianten der Nichtlinearen Gleichungssysteme

In der letzten Dekade haben Verbindungen zwischen algebraischer Topologie und Informatik neue Theorien und algorithmische Methoden hervorgebracht, die eine beeindruckende Anzahl von Anwendungen, zum Beispiel im Data Mining, in der Bildverarbeitung, der Bewegungsplanung von Robotern und der Analyse von Sensornetzwerken haben. Ein gemeinsames Merkmal dieser Methoden ist die Robustheit und Stabilität bezüglich Abweichungen - ein gemeinsames Merkmal der meisten Anwendungen von Topologie. In diesem Projekt werden wir Methoden aus der algorithmischen Topologie auf ein grundlegendes mathematisches und informatisches Problem anwenden: dem Lösen von Systemen von nichtlinearen Gleichungen. Hier werden wir topologische Methoden verwenden, um die Lösung zu lokalisieren, und diejenigen Eigenschaften der Lösungsmenge zu charakterisieren, die invariant bezüglich Perturbationen des Systems sind. Solche Eigenschaften sind oft wünschenswert, weil das Gleichungssystem durch ungenaue Messungen bestimmt sein kann oder von einem Modell mit inhärenten Unsicherheiten. Ein Beispiel von solchen Invarianten ist der Begriff der Well Gruppen, die unlängst von Edelsbrunner, Morozov und Patel entwickelt wurden. Die Ziele des Projektes sind: (1) Die Berechenbarkeit von Well Gruppen und anderer unter Perturbationen robuster Invarianten von nichtlinearen Gleichungssystemen zu untersuchen. (2) Die Anwendbarkeit von topologischen Methoden auf robuste Optimierungsprobleme mit inhärenten Unsicherheiten zu analysieren. (3) Experimente mit niedrigdimensionalen Daten durchzuführen und ein Softwarepaket zu entwickeln, das topologische Invarianten von nichtlinearen Systemen durch so genannte persistente Diagramme darstellen kann - eine Technik um wichtige robuste Eigenschaften durch gewisse Barcodes darzustellen. Wir erwarten zukünftige Anwendungen in der Analyse von Daten die Niveaumengen von Funktionen beschreiben. Für skalare Funktionen existiert der bekannte Marching Cube Algorithmus, der dazu verwendet wird, Niveaumengen aus medizinischen Abbildungen zu extrahieren. Das Projekt könnte der Ausgangspunkt für Techniken zum robusten Extrahieren von Niveaumengen mehrdimensionaler Daten sein. Die Hauptverantwortlichen des Projektes sind der Antragssteller Dr. Peter Franek und der Mitantragssteller Dr. Uli Wagner (IST Austria).

Hauptziel des Projektes war die Analyse von Algorithmen zur Ermittlung von Invarianten nichtlinearer Gleichungen mittels topologischer Methoden. Solche Invarianten sind robust gegenüber Störungen des Systems und/oder Rundungsfehlern. Ergebnisse: (1) Eine theoretische Analyse der topologischen Methoden, die für diesen Zweck geeignet sind: Wir haben mehrere algebraische Deskriptoren solcher Invarianten sowie Algorithmen, um diese zu berechnen sind. (2) Eine Demonstration, dass solche Invarianten zwar berechenbar sind, aber wahrscheinlich nur in geringen Dimensionen. In allen Computerexperimenten war die Anzahl der Variablen oder Gleichungen höchstens 7. (3) Während der vorherige Punkt einige Anwendungen ausschließt, bei denen eine hohe Dimension entscheidend ist, haben wir ein potenzielles industrielles Anwendungsgebiet erkannt: die Robotik. Zu unserer Überraschung fanden wir eine Anwendung von Invarianten nichtlinearer Systeme zur Verbesserung der Lokalisierung von unbemannten Unterwasserrobotern. (4) Über Systeme nichtlinearer Gleichungen hinaus haben wir die Berechenbarkeit topologischer Invarianten von Räumen im Allgemeinen analysiert, nämlich die Berechenbarkeit von Homotopiegruppen und deren Repräsentanten. Es stellte sich heraus, dass eine explizite Berechnung von Funktionen mit einer gegebenen homotopischen Eigenschaft möglich, aber nicht praktisch durchführbar ist, da die unteren Komplexitätsgrenzen in der Regel exponentiell in der Eingabegröße sind, selbst wenn die Dimension fixiert ist.