The solution of eigenvalue problems is one of the most important problem types in numerical linear algebra. Many eigenvalue problems are generalized eigenvalue problems which are transformed to standard eigenvalue problems and solved as such. If the matrices of the generalized eigenvalue problem have banded structure, this procedure leads to a huge overhead when using modern two-step solver for computing the resulting standard eigenvalue problem. The reason is the loss of banded structure in the standard eigenvalue problem matrix. A similar loss of the banded structure appears when solving banded generalized singular value decompositions by the transformation to standard singular value decompositions. This thesis describes serial and parallel algorithms for the transformation of the generalized eigenvalue problem to a standard eigenvalue problem and for the transformation of the generalized singular value decomposition to a standard singular value decomposition while maintaining the band. Maintaining the band allows to further exploit the banded structure, e.g. by directly running the second step of a two-step solver, or, if the band is too wide, utilizing a bandreduction step and then employing the second step of a two-step solver to obtain eigenvalues and eigenvectors or singular values and singular vectors. The developed algorithms are based on the Crawford algorithm. The parallel algorithms are analyzed on a theoretical basis and in performance measurements. They have demonstrated high scalability for medium to large size matrices with thin bands. In a comparison with the ELPA two-step solver the eigenvalue implementation has demonstrated its capabilities by reducing the time to solution significantly. The singular value implementation achieves similar runtimes as the eigenvalue implementation.     «

The solution of eigenvalue problems is one of the most important problem types in numerical linear algebra. Many eigenvalue problems are generalized eigenvalue problems which are transformed to standard eigenvalue problems and solved as such. If the matrices of the generalized eigenvalue problem have banded structure, this procedure leads to a huge overhead when using modern two-step solver for computing the resulting standard eigenvalue problem. The reason is the loss of banded structure in the...     »

Eigenwertprobleme sind eine der wichtigsten Problemstellungen in der numerischen linearen Algebra. Viele Eigenwertprobleme in der Praxis sind Verallgemeinerte Eigenwertprobleme, die zu Standard-Eigenwertproblemen transformiert und als solche gelöst werden. Wenn die Matrizen des Verallgemeinerten Eigenwertproblems Bandstruktur haben führt dieses Vorgehen zu unnötigem Mehraufwand bei der Verwendung moderner Zweischrittlöser für das Standard-Eigenwertproblem. Hintergrund dieses Mehraufwands ist der Verlust der Bandstruktur im Standard-Eigenwertproblem. Eine ähnliche Problematik tritt bei der Lösung Verallgemeinerter Singulärwertzerlegungen auf wenn diese zu Standard-Singulärwertzerlegungen transformiert werden. Diese Arbeit beschreibt serielle und parallele Algorithmen für die Transformation von Verallgemeinerten Eigenwertproblemen zu Standard-Eigenwertproblemen und für die Transformation von Verallgemeinerten Singulärwertzerlegungen zu Standard-Singulärwertzerlegungen unter Erhaltung der Bandstruktur. Dadurch lässt sich die Bandstruktur in einem weiteren Schritt, z.B. der Verwendung des zweiten Teils eines Zweischrittlösers, ausnutzen. Bei breiterem Band kann ein Bandreduktionsschritt eingebaut werden bevor der Zweischrittlöser zum Einsatz kommt und Eigenwerte und Eigenvektoren oder Singulärwerte und Singulärvektoren berechnet werden. Die entwickelten Algorithmen basieren auf dem Crawford Algorithmus. Die parallen Algorithmen werden theoretisch analysiert und die Performance der Implementierung untersucht. Die Algorithmen haben dabei für mittlere bis große Matrizen mit dünnem Band hohe Skalierbarkeit gezeigt. Im Vergleich zum ELPA Zweischrittlöser hat die Implementierung ihre Leistungsfähigkeit durch signifikant kürzere Berechnungszeiten unter Beweis gestellt. Die Singulärwertalgorithmen erziehlen ähnliche Laufzeiten wie die Eigenwertalgorithmen.     «

Eigenwertprobleme sind eine der wichtigsten Problemstellungen in der numerischen linearen Algebra. Viele Eigenwertprobleme in der Praxis sind Verallgemeinerte Eigenwertprobleme, die zu Standard-Eigenwertproblemen transformiert und als solche gelöst werden. Wenn die Matrizen des Verallgemeinerten Eigenwertproblems Bandstruktur haben führt dieses Vorgehen zu unnötigem Mehraufwand bei der Verwendung moderner Zweischrittlöser für das Standard-Eigenwertproblem. Hintergrund dieses Mehraufwands ist der...     »