Geglättete Analyse von Konditionszahlen

点击翻译按钮获取中文摘要

Das Ziel des Projekts ist die Weiterentwicklung eines systematischen Ansatzes zur probabilistischen Analyse numerischer Algorithmen im Sinne der von D. Spielman und S.-H. Teng 2001 eingeführten geglätteten Analyse (smoothed analysis). Untersucht werden sollen iterative Verfahren der linearen Algebra, innere Punkt-Methoden der linearen und konvexen Optimierung, sowie Homotopieverfahrenzur Lösung polynomialer Gleichungssysteme. Da die Laufzeit vieler iterativer numerischer Algorithmen von einer Konditionszahl der Eingabe des Berechnungsproblems dominiert wird, kann die Analyse von Algorithmen häufig auf eine entsprechende probabilistische Analyse von Konditionszahlen zurückgeführt werden. Mittlerweile ist die geglätteten Analyse als wichtige Methodik akzeptiert. Dies ist dokumentiert durch hochrangige Preise an deren Ernder Spielman und Teng (Gödel Preis 2008, Fulkerson Preis 2009) sowie durch die Verleihung des Nevanlinna Preises 2010 an Spielman. Eine intensive Weiterentwicklung dieses Ansatzes ist deshalb naheliegend und wird auf eine entsprechende internationale Resonanz stoßen.