Tensor networks and large-scale eigenvalue problems

Abstract

The present thesis is concerned with the numerical solution of large-scale eigenvalue problems via methods based on tensor networks. We address the computation of an eigenvector associated with the minimal eigenvalue of a Hamilton operator modeling a quantum mechanical many-particle spin system. If d denotes the number of particles and q the number of degrees of freedom for each particle, then the size of this symmetric eigenvalue problem scales exponentially in d to the base q. A well-known strategy with regard to the numerical treatment is to reshape those components of a method whose size scales exponentially into a tensor, i.e. a higher-dimensional array of numbers. This opens up the possibility of representation in a low-rank tensor format with non-exponentially growing ranks. In this way, a numerical method may be formulated by means of tensor networks which are a convenient tool when working with low-rank tensor formats. Our focus is on the q-XYZ and the q-Potts model. We introduce sets of vectors with a certain sparsity pattern whose definition is based on the q-ary representation of the indices of the potential nonzero entries. We show that for each eigenspace of a Hamilton operator of the q-XYZ or q-Potts model, there exists an orthonormal basis all of whose elements have a sparsity pattern suitable for the model. Moreover we show that for the q-XYZ model, the characterization of the sparsity pattern depends on the coupling parameters determining the Hamilton operator. We consider the hierarchical Tucker format and the tensor train format and describe how to represent the given Hamilton operators in these formats. In order to solve the eigenvalue problem numerically, we employ on the one hand the locally optimal conjugate gradient method expressed in the hierarchical Tucker format and on the other hand the modified alternating linear scheme, also called density matrix renormalization group, built on the representation in the tensor train format. A key aspect of this thesis is the construction of an initial guess for a numerical eigensolver. We propose a strategy which utilizes information about the relation of solutions for two different small problem sizes to construct an approximation of a solution for the original large problem which then may be used as an initial guess in an iterative method. This particular way of construction is enabled by the specific sparsity patterns of the eigenvectors and we show that the result of the construction has a sparsity pattern suitable for an eigenvector as well. In this context we discuss for the q-XYZ model two alternative construction strategies depending on the coupling parameters. We explain how to carry out the construction of the initial guess in the hierarchical Tucker format and in the tensor train format and that the ranks of the initial guess are independent of d or scale only linearly in d. To demonstrate the effect of our contribution on the computational cost, we conduct extensive numerical tests. We compare the constructed initial guesses with random initial guesses in terms of an acceleration of the methods.

Die vorliegende Arbeit behandelt die numerische Lösung von groß-skaligen Eigenwertproblemen durch Methoden, welche auf Tensornetzwerken basieren. Wir beschäftigen uns mit der Bestimmung eines Eigenvektors zum minimalen Eigenwert eines Hamilton-Operators, der ein quantenmechanisches Vielteilchen-Spinsystem modelliert. Wenn d die Anzahl der Teilchen und q die Anzahl der Freiheitsgrade für jedes Teilchen beschreibt, skaliert die Größe dieses symmetrischen Eigenwertproblems exponentiell in d zur Basis q. Im Hinblick auf die numerische Behandlung ist es eine wohlbekannte Strategie, diejenigen Komponenten eines Verfahrens, deren Größe exponentiell skaliert, jeweils in einen Tensor, das heißt in ein höherdimensionales Zahlenfeld, umzusortieren. Dies eröffnet die Möglichkeit der Darstellung in einem Niedrigrang-Tensorformat mit nicht exponentiell wachsenden Rängen. Auf diese Art und Weise kann ein numerisches Verfahren mithilfe von Tensornetzwerken, die ein praktisches Werkzeug sind, um mit Niedrigrang-Tensorformaten zu arbeiten, formuliert werden. Unser Fokus liegt auf dem q-XYZ- und dem q-Potts-Modell. Wir führen Mengen von Vektoren mit einer gewissen Besetzungsstruktur ein, deren Definition auf der q-nären Darstellung der Indizes der potenziellen Nicht-Null-Einträge beruht. Wir zeigen, dass für jeden Eigenraum eines Hamilton-Operators des q-XYZ- oder q-Potts-Modells eine Orthonormalbasis existiert, deren Elemente alle eine zum Modell passende Besetzungsstruktur haben. Zudem zeigen wir, dass für das q-XYZ-Modell die Charakterisierung der möglichen Besetzungsstrukturen von der Wahl der den Hamilton-Operator festlegenden Kopplungsparameter abhängt. Wir betrachten das hierarchische Tucker-Format und das Tensor-Train-Format und beschreiben, wie sich die vorliegenden Hamilton-Operatoren in diesen Formaten darstellen lassen. Zur numerischen Lösung des Eigenwertproblems ziehen wir zum einen das lokal optimale konjugierte-Gradienten-Verfahren in einer Formulierung im hierarchischen Tucker-Format und zum anderen das modifizierte alternierende lineare Schema, auch Dichtematrix-Renormierungsgruppe genannt, das auf der Darstellung im Tensor-Train-Format aufbaut, heran. Einen Schwerpunkt dieser Arbeit bildet die Konstruktion einer Startlösung für einen numerischen Eigenlöser. Wir schlagen eine Strategie vor, die Informationen über die Beziehung von Lösungen für zwei verschiedene kleine Problemgrößen nutzt, um daraus eine Approximation einer Lösung für das ursprüngliche große Problem zu konstruieren, welche dann als Startlösung in einem iterativen Verfahren verwendet werden kann. Die konkrete Art und Weise dieser Konstruktion wird einerseits durch die speziellen Besetzungsstrukturen der Eigenvektoren ermöglicht, andererseits zeigen wir, dass das Resultat der Konstruktion eine zu den Eigenvektoren passende Besetzungsstruktur hat. In diesem Zusammenhang diskutieren wir für das q-XYZ-Modell zwei alternative Konstruktionsstrategien in Abhängigkeit der Kopplungsparameter. Wir erklären, wie sich die Konstruktion der Startlösung im hierarchischen Tucker-Format und im Tensor-Train-Format durchführen lässt und dass die Ränge der Startlösung unabhängig von d sind oder nur linear in d skalieren. Um den Effekt unseres Beitrags auf die Laufzeitkosten zu demonstrieren, führen wir umfangreiche numerische Tests durch. Dabei vergleichen wir die konstruierten Startlösungen mit zufällig gewählten Startlösungen hinsichtlich einer Beschleunigung der Verfahren.