Time integration for the dynamical low-rank approximation of matrices and tensors

Abstract

This thesis is concerned with the low-rank approximation of time-dependent high-dimensional matrices and tensors that can be given explicitly or are the unknown solution to a matrix or tensor differential equation. Large differential equations typically arise from a space discretization of a high-dimensional evolutionary partial differential equation and are not solvable by direct discretization because of their sheer size. The dynamical low-rank approximation approach counters this computational infeasibility by evolving a differential equation for an approximation matrix or tensor with underlying low-rank structure. The Lipschitz constant of the right-hand side of this differential equation grows inversely proportional to the size of the smallest singular value of the approximation matrix or of matricizations of the approximate tensor. Therefore, standard numerical integrators deteriorate in this situation. In practice, small singular values appear often due to overapproximation.

A constitutive method for time integration of matrices in low-rank format is the matrix projector-splitting integrator. It updates factor matrices of the underlying truncated singular value decomposition. We present a rigorous error analysis for this integrator that shows its robustness with respect to small singular values and its first order convergence. This result is achieved by using the exactness property of the integrator and the preservation of subspaces during the integration procedure. By means of the same ingredients, we extend this error analysis to the time integrator of tensor trains.

We further derive an integration method for time-dependent Tucker tensors. Matricizations of Tucker tensors enable us to a nested application of a modified version of the matrix projector-splitting integrator, where a substep in the integration step is not done exactly, but by another low-rank approximation. This nested Tucker integrator turns out to be exact in the explicit case and robust in the presence of small singular values of matricizations of the Tucker tensor.

We also propose a numerical integrator for the approximation of a matrix that is the unknown solution to a stiff matrix differential equation. We deal with a class of matrix differential equations that is characterized by a stiff linear and a non-stiff nonlinear part. This integrator separates the stiff differential equation into a linear and a nonlinear subproblem by the Lie-Trotter splitting method. We show an error bound of order one that is independent of singular values and of the severe Lipschitz constant.

We contribute to the development and to the analysis of efficient and robust time integration methods by following the dynamical low-rank approximation approach using low-rank structures of matrix and tensor representations.

Die Niedrigrangapproximation zeitabhängiger, hochdimensionaler Matrizen und Tensoren, die explizit oder implizit als unbekannte Lösung einer Matrix- oder Tensordifferentialgleichung gegeben sein können, ist Gegenstand der Betrachtung. Differentialgleichungen für sehr große Matrizen und Tensoren treten typischerweise nach der Ortsdiskretisierung einer hochdimensionalen partiellen Differentialgleichung auf und sind auf Grund der Größe der Matrix beziehungsweise des Tensors nicht direkt lösbar. Der Ansatz der dynamischen Niedrigrangapproximation bringt eine Differentialgleichung für die Approximationsmatrix oder den -tensor mit Niedrigrangstruktur hervor und wirkt den rechentechnischen Schwierigkeiten auf diese Weise entgegen. Die Lipschitzkonstante der rechten Seite dieser Differentialgleichung verhält sich jedoch proportional zur Inversen des kleinsten Singulärwertes der Approximationsmatrix beziehungsweise der Matrizisierungen des Approximationstensors. Aus diesem Grund sind klassische numerische Verfahren nicht praktikabel, da sie eine starke Schrittweitenbeschränkung erfordern, um Lösungen zu liefern. In der Anwendung der Niedrigrangapproximation ist a priori nicht klar wie groß der effektive Rang der zu approximierenden Matrix oder des Tensors ist und daher wird dieser oft zu groß gewählt. Dies führt dazu, dass kleine Singulärwerte auftreten. Der Matrixintegrator ist ein wesentliches Verfahren für die Zeitintegration von Matrizen im Singulärwert zerlegten Niedrigrangformat und ist grundlegend für diese Arbeit. Er bestimmt die drei Faktormatrizen zum nächsten Zeitpunkt und liefert so eine Approximationslösung von niedrigem Rang. Wir führen eine Fehleranalyse dieses Integrators durch, die eine Konvergenz erster Ordnung zeigt und die eine Fehlerschranke unabhängig von kleinen Singulärwerten nachweist. Um die Schwierigkeit mit der Lipschitzkonstante zu umgehen, machen wir Gebrauch von der Exaktheit des Integrators im expliziten Fall und von der Beobachtung, dass jeweils eine der beiden Basismatrizen der Singulärwertzerlegung während der Zeitintegration konstant bleibt. Mit den gleichen Ideen lässt sich die Fehleranalyse für den Integrator für Tensor Trains ausweiten. Ferner entwickeln wir eine Integrationsmethode für die Zeitentwicklung von Tucker-Tensoren. Die Matrizisierung von Tucker Tensoren erlaubt es uns eine leicht abgeänderte Version des Matrixintegrators anzuwenden, indem wir die ersten beiden Teilschritte direkt lösen, beim dritten Schritt hingegen eine Niedrigrangapproximation durchführen. Dieser Tucker Integrator ist exakt wenn der zu approximierende Tensor explizit gegeben ist. Dieses Verfahren liefert auch bei auftretenden kleinen Singulärwerten gute Ergebnisse, was aus der Fehleranalyse hervorgeht, die Fehlerschranken angibt, welche unabhängig von Singulärwerten sind. Überdies beschäftigen wir uns mit der Niedrigrangapproximation von Lösungsmatrizen steifer Differentialgleichungen. Hierbei betrachten wir jene Differentialgleichungen, die aus einem linearen und steifen sowie einem nichtlinearen und nicht steifen Anteil bestehen. Die Hauptidee dieses Integrationsverfahrens besteht darin, den steifen vom nicht steifen Anteil mit Hilfe der Lie-Trotter Splittingmethode zu trennen und die beiden resultierenden Differentialgleichungen für sich zu lösen. Auf Grund dieser Aufteilung ist es möglich eine Fehleranalyse zu führen, die aufzeigt, dass das Verfahren von der Lipschitzkonstanten nicht beeinflusst wird und dass dessen Fehlerschranke unabhängig von Singulärwerten ist. Die vorliegende Arbeit ist ein Beitrag zur Entwicklung sowie zur numerischen Analyse effizienter und bezüglich kleiner Singulärwerte robuster numerischer Integrationsverfahren. Grundlegend hierfür ist das Verfahren der dynamischen Niedrigrangapproximation unter Verwendung einer Niedrigrangfaktorisierung der Matrix oder des Tensors.