Please use this identifier to cite or link to this item:
Main Title: Inexact methods for the solution of large scale Hermitian eigenvalue problems
Translated Title: Inexakte Methoden zur Lösung großer hermitescher Eigenwertprobleme
Author(s): Kandler, Ute
Advisor(s): Mehrmann, Volker
Schröder, Christian
Referee(s): Mehrmann, Volker
Mehl, Christian
Beattie, Christopher
Granting Institution: Technische Universität Berlin
Type: Doctoral Thesis
Language Code: en
Abstract: This thesis focuses on the solution of high dimensional Hermitian eigenproblems in situations where vector operations cannot be carried out exactly. To this end an inexact Arnoldi method with the aim to approximate extreme eigenvalues and eigenvectors is developed. This method is particularly wellsuited for large scale problems as it efficiently reduces the storage and computational requirements by constructing an orthonormal basis of the associated Krylov subspace. To consider the effect of the inexactness of the operations, a variant of Gram Schmidt orthogonalization is introduced in this thesis. The so called compensated Gram Schmidt orthogonalization (ComGS), if necessary enhanced by reorthogonalization, is used in the inexact Arnoldi method to compute a nearly orthogonal basis of the associated Krylov subspace. The effects of small perturbations on the distance to orthogonality of the resulting basis are studied and the ComGS method is compared to classical methods such as the modified and classical Gram Schmidt method. To investigate the influence of the inexactness of the vector operations not only on the orthogonality of the Krylov subspace basis but also on the quality of the spectral approximations, the convergence behavior of the inexact Arnoldi method and more general of inexact Krylov subspace methods is analyzed. By using the concept of the angle of inclusion, bounds for the distance of the exact invariant subspace to (i) an inexact Krylov subspace and (ii) a Ritz space therein are found. While based on the first bound an a priori statement about how many more iteration steps of the inexact Krylov method are necessary to ensure convergence to a given tolerance can be derived, the second bound allows for an a posteriori statement regarding the quality of the computed Ritz space. To avoid the sensitivity of both bounds to the gap between the desired and the remaining eigenvalues the concept of nested subspaces is used in the a priori setting whereas in the a posteriori setting the Ritz space is allowed to be of larger dimension than the invariant subspace. Consequently, the bounds can be valid and meaningful even in the presence of perturbations and a small gap between the desired and remaining eigenvalues. Lastly, the inexact Arnoldi method is generalized to the tensor setting to make storage and computations feasible. Numerical experiments with the YZ-model show that in the operator-tensor setting the inexact Arnoldi method allows for the solution of quantum systems of much larger dimension than it would be possible in the matrix-vector setting.
In dieser Arbeit werden Lösungsverfahren für hochdimensionale Hermitesche Eigenwertprobleme unter Berücksichtigung von inexakten Vektoroperationen untersucht. Zu diesem Zweck wird eine inexakte Arnoldi Methode zur approximativen Berechnung extremer Eigenwerte und Eigenvektoren entwickelt. Diese Methode ist besonders für hochdimensionale Probleme geeignet, da sie den Speicher- und Rechenaufwand durch den Aufbau einer orthonormalen Basis des zugehörigen Krylovraumes reduziert. Um die Auswirkungen inexakter Operationen zu berücksichtigen, wird in dieser Dissertation eine Variante der Gram Schmidt Orthogonalisierung, die so genannte compensated Gram-Schmidt Orthogonalisierung (ComGS), vorgestellt. Diese Methode (ggf. ergänzt durch Reorthogonalisierung) wird in der inexakten Arnoldi Methode verwendet, um eine nahezu orthogonale Basis des zugehörigen Krylovraumes zu berechnen. Es werden die Auswirkungen der Störungen auf den Orthogonalitätsabstand der resultierenden Basis untersucht und die ComGS Methode mit klassischen Orthogonalisierungsverfahren verglichen. Um nicht nur die Auswirkungen der inexakten Vektoroperationen auf die Orthogonalität der Krylov-Unterraumbasis, sondern auch auf die Qualität der spektralen Approximationen zu untersuchen, wird das Konvergenzverhalten der inexakten Arnoldi Methode und allgemein der inexakten Krylov-Unterraumraum-Verfahren analysiert. Unter Verwendung des Konzepts Angle of inclusion werden Schranken für den Abstand des invarianten Teilraums zu (i) einem inexakten Krylov-Unterraum und (ii) zu einem Ritz-Raum, welcher im inexakten Krylov-Unterraum enthalten ist, gefunden. Basierend auf der ersten Schranke kann eine a priori Aussage gemacht werden, wie viele zusätzliche Iterationsschritte der inexakten Krylov Methode notwendig sind, um die Konvergenz zu einer gegebenen Toleranz zu gewährleisten. Die zweite Schranke ermöglicht eine a posteriori Aussage über die Qualität des berechneten Ritz-Raums. Um die Sensitivität beider Schranken hinsichtlich des Abstandes zwischen den gesuchten Eigenwerten und dem restlichen Spektrum zu vermeiden, wird in der Herleitung der a priori Schranke das Prinzip verschachtelter Unterräume verwendet, während in der Herleitung der a posteriori Schranke der betrachtete Ritz-Raum eine größere Dimension als der gesuchte invariante Teilraum haben darf. Die hergeleiteten Schranken sind somit auch gültig und aussagekräftig, falls die Matrix einer Störung unterliegt oder ihr Spektrum einen kleinen Abstand zwischen den gesuchten und restlichen Eigenwerten aufweist. Schließlich wird die inexakte Arnoldi Methode auf Tensoren übertragen. Numerische Experimente mit dem YZ-Modell zeigen, dass im Operator-Tensor-Setting die inexakte Arnoldi Methode die Lösung des Eigenwertproblems von Quantensystemen deutlich höherer Dimensionen ermöglicht, als es im Matrix-Vektor-Setting möglich wäre.
Exam Date: 31-Jul-2019
Issue Date: 2019
Date Available: 2-Sep-2019
DDC Class: 510 Mathematik
Subject(s): inexact Krylov methods
Arnoldi method
Hermitian eigenvalue problem
convergence analysis
inexakte Krylov Methode
Arnoldi Methode
hermitesche Eigenwertprobleme
Sponsor/Funder: DFG, 169213306, Scalable Numerical Methods for Adiabatic Quantum Preparation
Appears in Collections:FG Numerische Mathematik » Publications

Files in This Item:
File Description SizeFormat 
kandler_ute.pdf1.93 MBAdobe PDFThumbnail

This item is licensed under a Creative Commons License Creative Commons