Geglättete Analyse von Konditionszahlen

• Applicant: Professor Dr. Peter Bürgisser
• Subject Area: Mathematics
• Term: from 2007 to 2016
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 40997669

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.

• DFG Programme: Research Grants