Krylov techniques and approximations to the action of matrix exponentials

Abstract

Die Matrixexponentialfunktion stellt eine Fundamentallösung für autonome Systemen linearer Differentialgleichungen dar. Angewendet auf einen Startvektor lässt sich damit die Zeitentwicklung dieses Vektors für einen gegebenen Zeitschritt berechnen. In der aktuellen Arbeit betrachten wir schwachbesetzte Systeme von großer Dimension, welche sich häufig aus der numerischen Behandlung von partiellen Differentialgleichungen (Evolutionsgleichungen) ergeben. Für solche Systeme ist eine direkte Auswertung der Matrixexponentialfunktion nicht praxistauglich. Die Anwendung der Matrixexponentialfunktion auf einem Startvektor lässt sich aber effizient durch Krylov-Unterraum Methoden annähern. Solche Methoden sind Thema dieser Arbeit. Unter anderem betrachten wir Abschätzungen für den Fehler von Krylov-Unterraum Verfahren zur numerischen Zeitintegration. Damit lässt sich die Dimension des Unterraums bzw. die Größe von Zeitschritten des Verfahrens steuern, um die numerische Zeitenwicklung mit hinreichender Genauigkeit zu berechnen. Für verschiedene Arten von Systemen leiten wir auch neue obere Schranken für die Fehlernorm her, welche eine besonders zuverlässige Fehlerschätzung erlauben. Ein weiteres Thema dieser Arbeit ist der Zusammenhang zwischen der Spektralzerlegung des Startvektors und Spektralzerlegungen, welche sich aus der Projektion auf einen Krylov-Unterraum ergeben. Der Fehler der betrachteten Verfahren zur numerischen Zeitintegration lässt sich über eine Spektralzerlegung des Startvektors darstellen, welche aber in der Praxis nicht zur Verfügung steht. Abschätzungen zur Spektralzerlegung des Startvektors basierend auf Krylov-Unterräume können aber hilfreiche Informationen zum Problem liefern, z.B. um rationale Matrixfunktionen zur numerischen Zeitintegration zu generieren, die relevante Charakteristiken der Lösung besonders gut imitieren. In dieser Arbeit betrachten wir auch das Konvergenzverhalten von Methoden zur numerischen Zeitintegration von schief-Hermiteschen Systemen basierend auf rationalen Krylov-Unterraum Verfahren. Die Struktur der Spektralzerlegung des Startvektors bleibt im rationalen Krylov-Unterraum teilweise erhalten. Bestimmte Charakteristiken solcher Systeme, welche sich vorteilhaft auf rationale Annäherungen auswirken, lassen sich daher auch mit Verfahren basierend auf rationalen Krylov-Unterräumen nutzen. Damit lässt sich teilweise ein von einer zugrundeliegenden Gitterdiskretisierung unabhängiges Konvergenzverhalten solcher Methoden erklären.

The matrix exponential represents a time evolution operator for a linear autonomous system of ordinary differential equations. The action of the matrix exponential on a starting vector yields its time evolution for a given time step. In the present thesis, we consider sparse and large systems, which appear frequently in the context of discretized partial differential equations of evolutionary type. In this setting, a direct computation of the matrix exponential is not practicable. However, the action of the matrix exponential can be efficiently approximated using Krylov techniques which are the topic of the present thesis. The first part of this thesis is mainly dedicated to error estimates for the Krylov approximation to the action of matrix exponentials. Error estimates provide a proper dimension for the underlying Krylov subspace, or a proper choice of time steps such that the constructed time propagator is sufficiently accurate. For various types of systems, we introduce upper bounds on the error norm, which constitute most reliable error estimates. Another topic of the present thesis is the relation between the spectral distribution of the starting vector and spectral distributions which result from projection on Krylov subspaces. The error of the discussed time integration methods can be represented by the spectral distribution of the starting vectors, which is not accessible in practice. Estimates on this spectral distribution based on Krylov subspace techniques can be of some use for numerical time integration, e.g., to design rational approximants to the matrix exponential which imitate specific characteristics of the exact time evolution. In the present thesis, we also study the convergence behavior of rational Krylov approximations to the action of the exponential of skew-Hermitian matrices. The structure of the spectral distribution of the starting vector is partly preserved in the rational Krylov subspace. Thus, specific characteristics of such systemts which are desirable for rational approximation are also of some use for rational Krylov approximations. Such ideas yield some insight on convergence behavior independent of a refinement of an underlying grid discretization for such methods.