Detailansicht

On implementation and evaluation of a divide & conquer eigensolver for the real bandsymmetric eigenproblem and comparison to current methods
Kastor Maximilian Felsner
Art der Arbeit
Masterarbeit
Universität
Universität Wien
Fakultät
Fakultät für Informatik
Studiumsbezeichnung bzw. Universitätlehrgang (ULG)
Masterstudium Scientific Computing
Betreuer*in
Wilfried Gansterer
Volltext herunterladen
Volltext in Browser öffnen
Alle Rechte vorbehalten / All rights reserved
DOI
10.25365/thesis.54720
URN
urn:nbn:at:at-ubw:1-18498.93675.294670-8
Link zu u:search
(Print-Exemplar eventuell in Bibliothek verfügbar)

Abstracts

Abstract
(Deutsch)
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.
Abstract
(Englisch)
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

Schlagwörter
(Englisch)
eigensolver eigenproblem band matrix symmetric divide and conquer tridiagonal reduction
Schlagwörter
(Deutsch)
Eigenwertproblem Bandmatrix symmetrisch divide and conquer Tridiagonalisierung
Autor*innen
Kastor Maximilian Felsner
Haupttitel (Englisch)
On implementation and evaluation of a divide & conquer eigensolver for the real bandsymmetric eigenproblem and comparison to current methods
Paralleltitel (Deutsch)
Implementierung und Evaluierung eines Divide & Conquer Algorithmus für das reelle bandsymmetrische Eigenwertproblem und Vergleich mit aktuellen Methoden
Publikationsjahr
2018
Umfangsangabe
133 Seiten : Illustrationen, Diagramme
Sprache
Englisch
Beurteiler*in
Wilfried Gansterer
Klassifikationen
31 Mathematik > 31.76 Numerische Mathematik ,
54 Informatik > 54.00 Informatik: Allgemeines
AC Nummer
AC15535047
Utheses ID
48363
Studienkennzahl
UA | 066 | 940 | |
Universität Wien, Universitätsbibliothek, 1010 Wien, Universitätsring 1