Corvino, Corvino and Schoen, Chruściel and Delay have shown the existence of a large class of asymptotically flat vacuum initial data for Einstein's field equations which are static or stationary in a neighborhood of space-like infinity, yet quite general in the interior. The proof relies on some abstract, non-constructive arguments which makes it difficult to calculate such data numerically by using similar arguments. A quasilinear elliptic system of equations is presented of which we expect that it can be used to construct vacuum initial data which are asymptotically flat, time-reflection symmetric, and asymptotic to static data up to a prescribed order at space-like infinity. A perturbation argument is used to show the existence of solutions. It is valid when the order at which the solutions approach staticity is restricted to a certain range. Difficulties appear when trying to improve this result to show the existence of solutions that are asymptotically static at higher order. The problems arise from the lack of surjectivity of a certain operator. Some tensor decompositions in asymptotically flat manifolds exhibit some of the difficulties encountered above. The Helmholtz decomposition, which plays a role in the preparation of initial data for the Maxwell equations, is discussed as a model problem. A method to circumvent the difficulties that arise when fast decay rates are required is discussed. This is done in a way that opens the possibility to perform numerical computations. The insights from the analysis of the Helmholtz decomposition are applied to the York decomposition, which is related to that part of the quasilinear system which gives rise to the difficulties. For this decomposition analogous results are obtained. It turns out, however, that in this case the presence of symmetries of the underlying metric leads to certain complications. The question, whether the results obtained so far can be used again to show by a perturbation argument the existence of vacuum initial data which approach static solutions at infinity at any given order, thus remains open. The answer requires further analysis and perhaps new methods. / Corvino, Corvino und Schoen als auch Chruściel und Delay haben die Existenz einer grossen Klasse asymptotisch flacher Anfangsdaten für Einsteins Vakuumfeldgleichungen gezeigt, die in einer Umgebung des raumartig Unendlichen statisch oder stationär aber im Inneren der Anfangshyperfläche sehr allgemein sind. Der Beweis beruht zum Teil auf abstrakten, nicht konstruktiven Argumenten, die Schwierigkeiten bereiten, wenn derartige Daten numerisch berechnet werden sollen. In der Arbeit wird ein quasilineares elliptisches Gleichungssystem vorgestellt, von dem wir annehmen, dass es geeignet ist, asymptotisch flache Vakuumanfangsdaten zu berechnen, die zeitreflektionssymmetrisch sind und im raumartig Unendlichen in einer vorgeschriebenen Ordnung asymptotisch zu statischen Daten sind. Mit einem Störungsargument wird ein Existenzsatz bewiesen, der gilt, solange die Ordnung, in welcher die Lösungen asymptotisch statische Lösungen approximieren, in einem gewissen eingeschränkten Bereich liegt. Versucht man, den Gültigkeitsbereich des Satzes zu erweitern, treten Schwierigkeiten auf. Diese hängen damit zusammen, dass ein gewisser Operator nicht mehr surjektiv ist. In einigen Tensorzerlegungen auf asymptotisch flachen Räumen treten ähnliche Probleme auf, wie die oben erwähnten. Die Helmholtzzerlegung, die bei der Bereitstellung von Anfangsdaten für die Maxwellgleichungen eine Rolle spielt, wird als ein Modellfall diskutiert. Es wird eine Methode angegeben, die es erlaubt, die Schwierigkeiten zu umgehen, die auftreten, wenn ein schnelles Abfallverhalten des gesuchten Vektorfeldes im raumartig Unendlichen gefordert wird. Diese Methode gestattet es, solche Felder auch numerisch zu berechnen. Die Einsichten aus der Analyse der Helmholtzzerlegung werden dann auf die Yorkzerlegung angewandt, die in den Teil des quasilinearen Systems eingeht, der Anlass zu den genannten Schwierigkeiten gibt. Für diese Zerlegung ergeben sich analoge Resultate. Es treten allerdings Schwierigkeiten auf, wenn die zu Grunde liegende Metrik Symmetrien aufweist. Die Frage, ob die Ergebnisse, die soweit erhalten wurden, in einem Störungsargument verwendet werden können um die Existenz von Vakuumdaten zu zeigen, die im räumlich Unendlichen in jeder Ordnung statische Daten approximieren, bleibt daher offen. Die Antwort erfordert eine weitergehende Untersuchung und möglicherweise auch neue Methoden.

We present a unified and self-contained treatment of rational Krylov methods for approximating the product of a function of a linear operator with a vector. With the help of general rational Krylov decompositions we reveal the connections between seemingly different approximation methods, such as the Rayleigh–Ritz or shift-and-invert method, and derive new methods, for example a restarted rational Krylov method and a related method based on rational interpolation in prescribed nodes. Various theorems known for polynomial Krylov spaces are generalized to the rational Krylov case. Computational issues, such as the computation of so-called matrix Rayleigh quotients or parallel variants of rational Arnoldi algorithms, are discussed. We also present novel estimates for the error arising from inexact linear system solves and the approximation error of the Rayleigh–Ritz method. Rational Krylov methods involve several parameters and we discuss their optimal choice by considering the underlying rational approximation problems. In particular, we present different classes of optimal parameters and collect formulas for the associated convergence rates. Often the parameters leading to best convergence rates are not optimal in terms of computation time required by the resulting rational Krylov method. We explain this observation and present new approaches for computing parameters that are preferable for computations. We give a heuristic explanation of superlinear convergence effects observed with the Rayleigh–Ritz method, utilizing a new theory of the convergence of rational Ritz values. All theoretical results are tested and illustrated by numerical examples. Numerous links to the historical and recent literature are included.

We present a unified and self-contained treatment of rational Krylov methods for approximating the product of a function of a linear operator with a vector. With the help of general rational Krylov decompositions we reveal the connections between seemingly different approximation methods, such as the Rayleigh–Ritz or shift-and-invert method, and derive new methods, for example a restarted rational Krylov method and a related method based on rational interpolation in prescribed nodes. Various theorems known for polynomial Krylov spaces are generalized to the rational Krylov case. Computational issues, such as the computation of so-called matrix Rayleigh quotients or parallel variants of rational Arnoldi algorithms, are discussed. We also present novel estimates for the error arising from inexact linear system solves and the approximation error of the Rayleigh–Ritz method. Rational Krylov methods involve several parameters and we discuss their optimal choice by considering the underlying rational approximation problems. In particular, we present different classes of optimal parameters and collect formulas for the associated convergence rates. Often the parameters leading to best convergence rates are not optimal in terms of computation time required by the resulting rational Krylov method. We explain this observation and present new approaches for computing parameters that are preferable for computations. We give a heuristic explanation of superlinear convergence effects observed with the Rayleigh–Ritz method, utilizing a new theory of the convergence of rational Ritz values. All theoretical results are tested and illustrated by numerical examples. Numerous links to the historical and recent literature are included.

Normalformen drücken semantische Eigenschaften einer Logik durch syntaktische Restriktionen aus. Sie ermöglichen es Algorithmen, Grenzen der Ausdrucksstärke einer Logik auszunutzen. Ein Beispiel ist die Lokalität der Logik erster Stufe (FO), die impliziert, dass Graph-Eigenschaften wie Erreichbarkeit oder Zusammenhang nicht FO-definierbar sind. Gaifman-Normalformen drücken die Bedeutung einer FO-Formel als Boolesche Kombination lokaler Eigenschaften aus. Sie haben eine wichtige Rolle in Model-Checking Algorithmen für Klassen dünn besetzter Graphen, deren Laufzeit durch die Größe der auszuwertenden Formel parametrisiert ist. Es ist jedoch bekannt, dass Gaifman-Normalformen im Allgemeinen nur mit nicht-elementarem Aufwand konstruiert werden können. Dies führt zu einer enormen Parameterabhängigkeit der genannten Algorithmen. Ähnliche nicht-elementare untere Schranken sind auch für Feferman-Vaught-Zerlegungen und für die Erhaltungssätze von Lyndon, Łoś und Tarski bekannt. Diese Arbeit untersucht die Komplexität der genannten Normalformen auf Klassen von Strukturen beschränkten Grades, für welche die nicht-elementaren unteren Schranken nicht gelten. Für diese Einschränkung werden Algorithmen mit elementarer Laufzeit für die Konstruktion von Gaifman-Normalformen, Feferman-Vaught-Zerlegungen, und für die Erhaltungssätze von Lyndon, Łoś und Tarski entwickelt, die in den ersten beiden Fällen worst-case optimal sind. Wichtig hierfür sind Hanf-Normalformen. Es wird gezeigt, dass eine Erweiterung von FO durch unäre Zählquantoren genau dann Hanf-Normalformen erlaubt, wenn alle Zählquantoren ultimativ periodisch sind, und wie Hanf-Normalformen in diesen Fällen in elementarer und worst-case optimaler Zeit konstruiert werden können. Dies führt zu Model-Checking Algorithmen für solche Erweiterungen von FO sowie zu Verallgemeinerungen der Algorithmen für Feferman-Vaught-Zerlegungen und die Erhaltungssätze von Lyndon, Łoś und Tarski. / Normal forms express semantic properties of logics by means of syntactical restrictions. They allow algorithms to benefit from restrictions of the expressive power of a logic. An example is the locality of first-order logic (FO), which implies that properties like reachability or connectivity cannot be defined in FO. Gaifman's local normal form expresses the satisfaction conditions of an FO-formula by a Boolean combination of local statements. Gaifman normal form serves as a first step in fixed-parameter model-checking algorithms, parameterised by the size of the formula, on sparse graph classes. However, it is known that in general, there are non-elementary lower bounds for the costs involved in transforming a formula into Gaifman normal form. This leads to an enormous parameter-dependency of the aforementioned algorithms. Similar non-elementary lower bounds also hold for Feferman-Vaught decompositions and for the preservation theorems by Lyndon, Łoś, and Tarski. This thesis investigates the complexity of these normal forms when restricting attention to classes of structures of bounded degree, for which the non-elementary lower bounds are known to fail. Under this restriction, the thesis provides algorithms with elementary and even worst-case optimal running time for the construction of Gaifman normal form and Feferman-Vaught decompositions. For the preservation theorems, algorithmic versions with elementary running time and non-matching lower bounds are provided. Crucial for these results is the notion of Hanf normal form. It is shown that an extension of FO by unary counting quantifiers allows Hanf normal forms if, and only if, all quantifiers are ultimately periodic, and furthermore, how Hanf normal form can be computed in elementary and worst-case optimal time in these cases. This leads to model-checking algorithms for such extensions of FO and also allows generalisations of the constructions for Feferman-Vaught decompositions and preservation theorems.