Masterprüfung mit Defensio, Felsner Kastor

07.11.2018 13:30 - 14:30

Universität Wien

Forschungslabor 7 (6.03)

Währinger Straße 29

1090 Wien

07.11.2018, 13:30 Uhr

Universität Wien
Forschungslabor 7 (6.03)
Währinger Straße 29
1090 Wien

Titel: “On Implementation and Evaluation of a Divide & Conquer Eigensolver for the Real Bandsymmetric Eigenproblem and Comparison to Current Methods”

Kurzfassung:
Die fortlaufende Weiterentwicklung moderner Computerarchitekturen fordert eine stetige Anpassung numerischer Software. Um die Rechenleistung heutiger Systeme auszunutzen müssen Algorithmen ein hohes Maß an Parallelität aufweisen. Für den spezifischen Fall eines symmetrischen Eigenwertproblems wurde festgestellt, dass eine neue Methode für die Tridiagonalisierung der ursprünglichen dicht besetzten Matrix S erforderlich ist, um parallele Systeme voll auszulasten. Dieser neue Ansatz bringt S in einem ersten Schritt durch eine Ähnlichkeitstransformation auf bandsymmetrische Form B und tridiagonalisiert B anschließend. Arbenz [4] verallgemeinerte die Idee hinter Cuppens divide and conquer Algorithmus und entwickelte so eine neue Methode, welche das bandsymmetrische Eigenwertproblem B direkt löst. Dies ermöglicht es, die zeitintensive Tridiagonalisierung der Bandmatrix B zu vermeiden. Bedauerlicherweise berichtete Arbenz [4] von numerischen Instabilitäten, die in ungenauen Eigenvektoren resultierten. Die vorliegende Arbeit evaluiert den Ansatz, die Spektralzerlegung einer dicht besetzten Matrix S durch Reduktion zu einer Bandmatrix B gefolgt von der Berechnung der Eigenwertzerlegung von B zu lösen. Hierfür werden in einem ersten Schritt der in [4] beschriebene Algorithmus implementiert und die Laufzeit optimiert. Später werden die numerischen Ungenauigkeiten des Algorithmus analysiert und eine verbesserte Version vorgestellt. Der finale Algorithmus wird abschließend mit modernen Methoden verglichen. Dieser Vergleich umfasst sowohl bandsymmetrische Verfahren, als auch die in LAPACK verfügbaren, die eine herkömmliche Tridiagonalisierung durchführen. Es zeigt sich, dass der Algorithmus eine vielversprechende Laufzeit-Komplexität aufweist, jedoch weitere Verbesserungen vonnöten sind, um orthogonale Eigenvektoren auch für Probleme mit eng geclusterten Eigenwerten garantieren zu können.

Organiser:

SPL 5