Detailseite
Projekt Druckansicht

Geglättete Analyse von Konditionszahlen

Fachliche Zuordnung Mathematik
Förderung Förderung von 2007 bis 2016
Projektkennung Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 40997669
 
Erstellungsjahr 2019

Zusammenfassung der Projektergebnisse

Die Laufzeit vieler iterativer numerischer Algorithmen wird von der Konditionszahl der Eingabe des Berechnungsproblems dominiert, einer kritischen Grösse, welche misst, wie sensitiv die Lösung von der Eingabe abhängt. Dies trifft zu auf iterative Verfahren der linearen Algebra, auf innere Punkt-Methoden der linearen und konvexen Optimierung, auf Homotopieverfahren zur Lösung polynomialer Gleichungssysteme, sowie auf gitterbasierte Methoden der nichtlinearen algorithmischen Geometrie. Zum Verständnis der typischen Laufzeit solcher Algorithmen wird eine Annahme über die zufällige Verteilung der Eingaben getroffen werden; häufig kann die Laufzeitanalyse auf eine entsprechende probabilistische Analyse einer Konditionszahl zurückgeführt werden. Dabei spielen geometrische Überlegungen eine wichtige Rolle. Dieser Ansatz geht zurück auf wichtige Arbeiten von Stephen Smale, Michael Shub und James Renegar. Eine Verfeinerung dieses Ansatzes, die geglättete Analyse (smoothed analysis) wurde von Daniel Spielman und Shang-Hua Teng vorgeschlagen. Hier werden kleine Störungen der Eingaben zufällig modelliert. Das Ziel des Projektes war die geglättete Analyse von Konditionszahlen und, damit verbunden, die geglättete Analyse der oben genannten numerischen Algorithmen. Das Projekt verlief insgesamt sehr erfolgreich: viele der neuen Ergebnisse sind in der Monographie Condition: The geometry of numerical algorithms von Peter Burgisser und Felipe Cucker umfassend dargestellt (Springer 2013). Ein Höhepunkt des Projekts war die Lösung von Smales 17. Problem durch Bürgisser und Cucker sowie Pierre Lairez, der für seine Arbeit mit dem “SIAM Activity Group on Algebraic Geometry Early Career Prize” ausgezeichnet wurde. Die Dissertation von Dennis Amelunxen (2011) schlägt eine Brücke zwischen konvexer Optimierung und sphärischer (konvexer) Integralgeometrie. Erstaunlicherweise sind die dabei auftretenden sphärischen intrinsischen Volumina das passende Konzept zur Analyse von Algorithmen im Compressive Sensing. (Letzere ist eine Methodik, welche die Signalverarbeitung revolutioniert hat.) Dies führte zu der mit dem “Information and Inference Best Paper Prize 2015” ausgezeichneten Arbeit von Dennis Amelunxen, Martin Lotz, Michael McCoy und Joel Tropp. Die Dissertation “Numerical and Statistical Aspects of Tensor Decompositions” von Paul Breiding (2017) und die daraus hervorgegangenen Publikationen mit seinen Coauthoren sind von grossem Interesse in der Datenanalyse. Weiterhin entwickelt Breiding zusammen mit Sascha Timme (TÜ Berlin) das leistungsfähige Julia Softwarepaket HomotopyContinuation.jl zur Lösung polynomialer Gleichungssysteme mittels Homotopieverfahren. Damit werden die theoretischen Grundlagen des Projekts den Anwendungen zugeführt. Nennenswerte, aus dem Projekt im weiteren Sinne hervorgegangene Entwicklungen sind neue numerische Algorithmen zur Berechnung von topologischen Informationen in hochdimensionalen Daten (Homologiegruppen), gegeben als semialgebraische Mengen. Schliesslich steht das Projekt in Zusammenhang mit einer fruchtbaren Entwicklung, die man als “zufällige reelle algebraische Geometrie” bezeichnen könnte.

Projektbezogene Publikationen (Auswahl)

 
 

Zusatzinformationen

Textvergrößerung und Kontrastanpassung