On MR3-type Algorithms for the Tridiagonal Symmetric Eigenproblem and the Bidiagonal SVD
Paul R. Willems · 2018
Die Arbeit On MRRR-type Algorithms for the Tridiagonal Symmetric Eigenproblem and the Bidiagonal SVD behandelt neue und verbesserte Ansatze zur Berechnung von Eigenzerlegungen symmterisch tridiagonaler Matrizen (Problem TSEP) und Singularwertzerlegungen von bidiagonalen Matrizen (BSVD). Diese zwei eng verwandten Aufgaben sind ein Kernthema der Numerischen Linearen Algebra, da sie die jeweiligen schwierigsten Teilaufgaben darstellen, die der Standardalgorithmus zur Berechnung von Eigen-/Singular-Systemen allgemeiner dichtbesetzter Matrizen losen muss. Das Werkzeug im Hauptfokus dieser Arbeit ist der Algorithmus Multiple Relatively Robust Representations (MRRR) von Inderjit Dhillon und Beresford Parlett. In einem ersten Teil werden der Algorithmus und seine begleitende Theorie in einer uberarbeiteten modularisierten und Rahmenwerk-orientierten Form prasentiert. Darauf basierend wird eine Reihe von Weiterentwicklungen am Kernalgorithmus selbst vorgestellt. Der zweite, und zentrale, Teil dieser Arbeit behandelt, wie Algorithmus MRRR eingesetzt werden kann, das Problem BSVD zu losen. Aufbauend auf vorangegangenen Arbeiten von Benedikt Groser und Bruno Lang wird eine umfangreiche Theorie entwickelt, auf welche drei weitere Beitrage aufbauen: ein besseres Verstandnis, warum die sogenannten Black-Box Ansatze nicht funktionieren konnen, eine rigorose Fehleranalyse des kopplungsbasierten Algorithmus von Groser und Lang, und schliesslich ein neuer Losungsansatz uber die Golub-Kahan Matrix. Der dritte Teil der Arbeit stellt einen neuen Algorithmus zum Verschieben (shiften) symmetrischer Tridiagonalmatrizen in block-faktorisierter Form vor, und zwar mit gemischter komponentenweiser relativer Stabilitat. Letzteres ist entscheidend, um die Benutzung der Methode im Rahmen von MRRR uberhaupt erst zu erlauben. Der grose Vorteil von Block-Faktorisierungen liegt darin, dass sie eine Moglichkeit zur Kontrolle von Elementwachstum bieten, und daher stark zur Robustheit von MRRR-basierten Methoden beitragen konnen. Die in der Arbeit entwickelten Varianten von MRRR wurden als Software-Prototypen implementiert und in einer Reihe von numerischen Experimenten wird belegt, dass diese entsprechenden Losern aus der LAPACK Software Bibliothek ebenburtig und teilweise sogar uberlegen sind.