Exploiting unconventional QR-algorithms for fast and accurate computations of roots of polynomials

• Antragsteller: Dr. Thomas Mach
• Fachliche Zuordnung: Mathematik
• Förderung: Förderung von 2012 bis 2013
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 227388185

Die Berechnung der Nullstellen eines Polynoms ist ein jahrhundertealtes, klassisches Problem der Mathematik, welches auch heute noch fundamentale Auswirkungen auf moderne Anwendungen hat. Viele Probleme der Natur- und Ingenieurwissenschaften, der Statistik und des Finanzwesen benötigen die Berechnung der Nullstellen von Polynomen mittleren Grades. Neuere Entwicklungen haben jedoch auch zu Anwendungen mit Polynomen deutlich höheren Grades geführt. Diese Probleme stammen, zum Beispiel, aus der Algebraischen Optimierung, der Algebraischen Geometrie oder der Signalverarbeitung. Die dabei auftretenden Polynome haben einen Grad der 1000 deutlich ubersteigt. Die etablierten Algorith¨ men sind für die Lösung dieser Probleme nicht mehr ausreichend, da sie unnötig lange Rechenzeiten benötigen und teilweise unzuverlässiger Resultate liefern.Die dominierenden Programmpakete für Numerische Lineare Algebra verwenden zur Zeit den QR Algorithmus zur Bestimmung der Eigenwerte der Companion Matrizen, welche mit den gesuchten Nullstellen zusammenfallen. Der QR Algorithmus ist einer der Top 10 Algorithmen des 20. Jahrhunderts [Cip00], trotzdem ist die aktuelle Verwendung nicht optimal, wie C. Moler, der Erfinder von Matlab, in[Mol91] erläuterte: Kann man durch optimale Ausnutzung der verborgenen Struktur des Problems eine Ordnung in der Komplexität des Speicher- und Rechenaufwands sparen.In diesem Projekt sollen zwei neue Forschungsansätze verbunden werden um die eben skizzierte Lücke zum theoretisch Möglichem zu schließen. Dazu werden die jüngst entwickelten unkonventionellen QR Algorithmen [Van11, VW12] angewendet auf verallgemeinerte Companion Faktorisierungen um neue schnellere, genauere und verlässlichere Algorithmen zu entwickeln.

• DFG-Verfahren: Forschungsstipendien
• Internationaler Bezug: Belgien
• Gastgeber: Professor Dr. Raf Vandebril