E101 - Institut für Analysis und Scientific Computing
-
Date (published):
2013
-
Number of Pages:
92
-
Abstract:
Das Berechnen der sogenannten Quasispezies in Eigen's Quasispeziesmodell ist gleichbedeutend mit der Berechnung des dominierenden Eigenvektors von sehr großen, stark strukturierten Matrizen. Insbesondere wächst die Dimension dieser Matrizen exponentiell mit dem für die Praxis entscheidenden Modellparameter. Daher leiden Standardmethoden am sogenannten "Fluch der Dimensionalität" und können somit keine Ergebnisse in praktisch relevanten Dimensionen liefern. Um dieses Problem zu umgehen, wurde gezeigt, dass die auftretenden Matrizen eine Repräsentation als Kronecker-Produkt erlauben, welche unmittelbar zu effizienten impliziten Matrix-Vektor Routinen führt. Darauf aufbauend erweist sich die Potenzmethode als einfaches Werkzeug zur Berechnung des dominanten Eigenvektors in praktisch relevanten Dimensionen. Der gravierende Nachteil der Potenzmethode ist ihre langsame Konvergenz im Falle einer schlechten Separation des dominierenden Eigenwerts. In dieser Arbeit zeigen wir, wie dieses Problem mittels so genannter shift-and-invert Methoden auch im Falle einer schlechten Separation, wie sie in der Praxis zu erwarten ist, effizient gelöst werden kann. Shift-and-invert Methoden erfordern die Lösung eines linearen Gleichungssystems in jedem Iterationsschritt. Grundsätzlich ist die iterative Lösung von linearen Gleichungssystemen ein bestens erforschtes Gebiet und jede Menge effiziente Ansätze, wie zum Beispiel Krylow-Unterraum-Verfahren, sind bekannt. Das eigentliche Problem ist diesbezüglich die Bereitstellung eines Vorkonditionierers der eine Lösung in möglichst wenigen Iterationsschritten erlaubt. Standardverfahren zur Vorkonditionierung scheitern im Kontext dieser Arbeit auf Grund der Größe und Struktur der betrachteten Matrizen. Daher ist es das vorrangige Ziel dieser Arbeit effektive Vorkonditionierer für das betrachtete Problem zu entwickeln, die es schlussendlich ermöglichen auch Probleme mit schlechter Separation des dominanten Eigenwerts effizient zu behandeln. Im Zuge dessen erarbeiten wir Themen aus verschiedenen Bereichen: Hinsichtlich wohl bekannter Resultate aus der Literatur erörtern wir Krylow-Unterraum-Verfahren sowie die Theorie und Anwendungen des Kronecker-Produkts, jeweils im Lichte des betrachteten Eigenwertproblems. Die zentralen neuartigen Resultate dieser Arbeit bestehen aus einer umfassenden Theorie Hamming-Distanz-basierter Matrizen. Letztere sind Matrizen deren Eintrag (i, j) einzig von der Hamming-Distanz zwischen den Indizes i und j (geeignet interpretiert als endliche Zeichenkette) abhängt. Diese neuartigen Resultate beinhalten dabei unter anderem algebraische und algorithmische Aspekte, so wie die Struktur dieser Klasse von Matrizen im Allgemeinen. Basierend auf den Resultaten zu Hamming-Distanz-basierten Matrizen leiten wir effiziente Vorkonditionierer für das betrachtete Problem her. Zusätzlich stellen wir Experimente der so erhaltenen numerischen Lösungsverfahren dar, welche Verbesserungen der Gesamtlaufzeit von zumindest einer Größenordnung aufzeigen.
de
Computing the so-called quasispecies in Eigen's quasispecies model is tantamount to the computation of the dominating eigenvector of a highly structured large scale matrix. In particular, all of the involved matrices are data-sparse matrices whose dimension grows exponentially with the practically important model parameter. As an immediate consequence, standard solvers suffer from the curse of dimensionality and are incapable of reaching practically relevant dimensions. In order to overcome this issue, it was shown that the required matrices allow for a Kronecker product representation which directly implies that highly efficient implicit matrix vector routines can be provided. Based on such efficient matrix vector products, the power iteration serves as simple tool to compute the dominating eigenvector also for problems at a relevant scale. The severe drawback of the power iteration is its inferior convergence speed in case of a bad separation of the dominating eigenvalue. In this thesis we show how to overcome this issue by employing more subtle shift-and-invert methods in order to provide efficient solvers also in case of a bad separation of the dominating eigenvalue---as it has to be expected in practice. Shift-and-invert methods require the solution of a linear system in every iteration. The iterative solution of linear systems is in principle a well-developed subject and a myriad of solvers, e.g., Krylov subspace methods, exist. The actual problem in this context is to provide a good preconditioner such that only a considerably small number of iterations are required. In particular, standard preconditioning approaches fail in the context of the problems considered in this thesis due to the high dimensionality and structure of the respective matrices. Therefore, the high level aim of this thesis is to provide suitable preconditioners for the problem at hand, in order to allow for an efficient computation of the quasispecies also in cases of a bad separation of the dominating eigenvalue. In the course of that, we elaborate on different fields: In terms of existing work we discuss Krylov subspace methods and the theory and application of the Kronecker product each with respect to the considered extreme scale eigenvalue problem. The central novel results presented in this thesis consist of a comprehensive theory of Hamming distance-based matrices, i.e., matrices whose (i,j)-th element solely depends on the Hamming distance between the indices i and j (appropriately interpreted as finite strings). These novel results cover among others algebraic and algorithmic aspects, as well as the structure of this family of matrices in general. Based on the theory of Hamming distance-based matrices, we eventually derive efficient preconditioners for the problem at hand. Moreover, we provide experimental data of the resulting solvers which depict overall performance gains by at least an order of magnitude.
en
Additional information:
Abweichender Titel laut Übersetzung der Verfasserin/des Verfassers Zsfassung in dt. Sprache