Deutsch

Die Arbeit "On MRRR-type Algorithms for the Tridiagonal Symmetric Eigenproblem and the Bidiagonal SVD" behandelt neue und verbesserte Ansätze zur Berechnung von Eigenzerlegungen symmterisch tridiagonaler Matrizen (Problem TSEP) und Singulärwertzerlegungen 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-/Singulär-Systemen allgemeiner dichtbesetzter Matrizen lösen 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 überarbeiteten modularisierten und Rahmenwerk-orientierten Form präsentiert. 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 lösen. Aufbauend auf vorangegangenen Arbeiten von Benedikt Großer und Bruno Lang wird eine umfangreiche Theorie entwickelt, auf welche drei weitere Beiträge aufbauen: ein besseres Verständnis, warum die sogenannten "Black-Box" Ansätze nicht funktionieren können, eine rigorose Fehleranalyse des kopplungsbasierten Algorithmus von Großer und Lang, und schliesslich ein neuer Lösungsansatz über 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 Stabilität. Letzteres ist entscheidend, um die Benutzung der Methode im Rahmen von MRRR überhaupt erst zu erlauben. Der große Vorteil von Block-Faktorisierungen liegt darin, dass sie eine Möglichkeit zur Kontrolle von Elementwachstum bieten, und daher stark zur Robustheit von MRRR-basierten Methoden beitragen können. 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 Lösern aus der LAPACK Software Bibliothek ebenbürtig und teilweise sogar überlegen sind.

English

The thesis "On MRRR-type Algorithms for the Tridiagonal Symmetric Eigenproblem and the Bidiagonal SVD" concerns new and improved approaches to compute eigendecompositions of symmetric tridiagonal matrices (problem TSEP) and singular value decompositions of bidiagonal matrices (BSVD). These two intimately related tasks lie at the core of numerical linear algebra, since they represent the respective hardest subtasks to be solved by the standard algorithm to compute eigen-/singular-systems of general dense matrices. The tool that lies in the main focus of this thesis is the algorithm of "Multiple Relatively Robust Representations (MRRR)" by Inderjit Dhillon and Beresford Parlett. In a first part the algorithm and its accompanying theory are presented in a revised and modularized, framework-driven form, based on which a series of improvements to the core algorithm itself are developed. The second, and central, part of this thesis concerns how algorithm MRRR can be harnessed to solve BSVD. Building on previous work by Benedikt Großer and Bruno Lang, a rigid body of theory is developed on which three more contributions rest: a better understanding why the so called "black-box" approaches cannot work, a rigorous error analysis of the coupling-based algorithm by Großer and Lang, and last but not least a new solution approach using the Golub-Kahan matrix. The third part of the thesis introduces a new algorithm to shift symmetric tridiagonal matrices given in block-factored form with mixed componentwise relative stability. The latter is crucial to allow using the method within MRRR in the first place. The big advantage of block-factorizations lies in the fact that they provide a means to control element growth and thus can contribute greatly to the robustness of MRRR-based methods. The variants of MRRR developed during the thesis were implemented in software prototypes, and in a series of numerical experiments those are shown to be highly competitive and in some regards even superior to respective solvers from the LAPACK software library.