Universitätsbibliothek Wien

On implementation and evaluation of a divide & conquer eigensolver for the real bandsymmetric eigenproblem and comparison to current methods

Felsner, Kastor Maximilian (2018) On implementation and evaluation of a divide & conquer eigensolver for the real bandsymmetric eigenproblem and comparison to current methods.
Masterarbeit, University of Vienna. Fakultät für Informatik
BetreuerIn: Gansterer, Wilfried

[img] PDF-File
Alle Rechte vorbehalten / All rights reserved

Download (2722Kb)
DOI: 10.25365/thesis.54720
URN: urn:nbn:at:at-ubw:1-18498.93675.294670-8

Link zu u:search

Abstract in English

As the architecture of modern computers continues to evolve, numerical software has to adapt. To make use of the ever increasing computational power parallelism needs to be exploited efficiently. For the specific case of a symmetric eigenproblem it was found that a new approach for the tridiagonal reduction is needed. This new approach first reduces the full problem S to banded form B and later tridiagonalises B. Arbenz [4] generalised the idea behind Cuppen's divide and conquer algorithm and proposed a new method which directly solves the bandsymmetric eigenproblem B. This creates the possibility of omitting the computationally expensive second reduction stage when solving a full symmetric eigenproblem S. Unfortunately, Arbenz [4] reported numerical instabilities which lead to insufficiently accurate eigenvectors. This thesis evaluates the approach of computing the eigendecomposition of S by using a full-to-band reduction followed by a bandsymmetric eigensolver. In a first step the algorithm described in [4] is implemented and the reported results are reproduced. Later the numerical inaccuracies of the algorithm are analysed and an improved version is proposed. The final algorithm is then compared to state-of-the-art eigensolvers which include both bandsymmetric ones as well as those available in LAPACK which use a full-to-tridiagonal reduction. It is found that the algorithm has a promising runtime complexity, however further improvements are needed to guarantee orthogonal eigenvectors for problems with tightly clustered eigenvalues.

Schlagwörter in Englisch

eigensolver / eigenproblem / band matrix / symmetric / divide and conquer / tridiagonal reduction

Abstract in German

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.

Schlagwörter in Deutsch

Eigenwertproblem / Bandmatrix / symmetrisch / divide and conquer / Tridiagonalisierung

Item Type: Hochschulschrift (Masterarbeit)
Author: Felsner, Kastor Maximilian
Title: On implementation and evaluation of a divide & conquer eigensolver for the real bandsymmetric eigenproblem and comparison to current methods
Umfangsangabe: 133 Seiten : Illustrationen, Diagramme
Institution: University of Vienna
Faculty: Fakultät für Informatik
Studiumsbezeichnung bzw.
Universitätslehrgang (ULG):
Masterstudium Scientific Computing
Publication year: 2018
Language: eng ... Englisch
Supervisor: Gansterer, Wilfried
Assessor: Gansterer, Wilfried
Classification: 54 Informatik > 54.00 Informatik: Allgemeines
31 Mathematik > 31.76 Numerische Mathematik
AC Number: AC15535047
Item ID: 54720
(Das PDF-Layout ist ident mit der Druckausgabe der Hochschulschrift.)

Urheberrechtshinweis: Für Dokumente, die in elektronischer Form über Datennetze angeboten werden, gilt uneingeschränkt das österreichische Urheberrechtsgesetz; insbesondere sind gemäß § 42 UrhG Kopien und Vervielfältigungen nur zum eigenen und privaten Gebrauch gestattet. Details siehe Gesetzestext.

Edit item (Administrators only) Edit item (Administrators only)