On Multilevel Methods Based on Non-Nested Meshes

Abstract

This thesis is concerned with multilevel methods for the efficient solution of partial differential equations in the field of scientific computing. Further, emphasis is put on an extensive study of the information transfer between finite element spaces associated with non-nested meshes. <br /> For the discretization of complicated geometries with a finite element method, unstructured meshes are often beneficial as they can easily be adjusted to the shape of the computational domain. Such meshes, and thus the corresponding discrete function spaces, do not allow for straightforward multilevel hierarchies that could be exploited to construct fast solvers. In the present thesis, we present a class of "semi-geometric" multilevel iterations, which are based on hierarchies of independent, non-nested meshes. This is realized by a variational approach such that the images of suitable prolongation operators in the next (finer) space recursively determine the coarse level spaces. The semi-geometric concept is of very general nature compared with other methods relying on geometric considerations. This is reflected in the relatively loose relations of the employed meshes to each other. The specific benefit of the approach based on non-nested meshes is the flexibility in the choice of the coarse meshes, which can, for instance, be generated independently by standard methods. The resolution of the boundaries of the actual computational domain in the constructed coarse level spaces is a characteristic feature of the devised class of methods. <br /> The flexible applicability and the efficiency of the presented solution methods is demonstrated in a series of numerical experiments. We also explain the practical implementation of the semi-geometric ideas and concrete transfer concepts between non-nested meshes. Moreover, an extension to a semi-geometric monotone multigrid method for the solution of variational inequalities is discussed. <br /> We carry out the analysis of the convergence and preconditioning properties, respectively, in the framework of the theory of subspace correction methods. Our technical considerations yield a quasi-optimal result, which we prove for general, shape regular meshes by local arguments. The relevant properties of the operators for the prolongation between non-nested finite element spaces are the H¹-stability and an L²-approximation property as well as the locality of the transfer. <br /> This thesis is a contribution to the development of fast solvers for equations on complicated geometries with focus on geometric techniques (as opposed to algebraic ones). Connections to other approaches are carefully elaborated. In addition, we examine the actual information transfer between non-nested finite element spaces. In a novel study, we combine theoretical, practical and experimental considerations. A thourough investigation of the qualitative properties and a quantitative analysis of the differences of individual transfer concepts to each other lead to new results on the information transfer as such. Finally, by the introduction of a generalized projection operator, the pseudo-L²-projection, we obtain a significantly better approximation of the actual L²-orthogonal projection than other approaches from the literature.

<strong>Nicht-geschachtelte Gitter in Multilevel-Verfahren</strong><br /> Diese Arbeit beschäftigt sich mit Multilevel-Verfahren zur effizienten Lösung von Partiellen Differentialgleichungen im Bereich des Wissenschaftlichen Rechnens. Dabei liegt ein weiterer Schwerpunkt auf der eingehenden Untersuchung des Informationsaustauschs zwischen Finite-Elemente-Räumen zu nicht-geschachtelten Gittern. <br /> Zur Diskretisierung von komplizierten Geometrien mit einer Finite-Elemente-Methode sind unstrukturierte Gitter oft von Vorteil, weil sie der Form des Rechengebiets einfacher angepasst werden können. Solche Gitter, und somit die zugehörigen diskreten Funktionenräume, besitzen im Allgemeinen keine leicht zugängliche Multilevel-Struktur, die sich zur Konstruktion schneller Löser ausnutzen ließe. In der vorliegenden Arbeit stellen wir eine Klasse "semi-geometrischer" Multilevel-Iterationen vor, die auf Hierarchien voneinander unabhängiger, nicht-geschachtelter Gitter beruhen. Dabei bestimmen in einem variationellen Ansatz rekursiv die Bilder geeigneter Prolongationsoperatoren im jeweils folgenden (feineren) Raum die Grobgitterräume. Das semi-geometrische Konzept ist sehr allgemeiner Natur verglichen mit anderen Verfahren, die auf geometrischen Überlegungen beruhen. Dies zeigt sich in der verhältnismäßig losen Beziehung der verwendeten Gitter zueinander. Der konkrete Nutzen des Ansatzes mit nicht-geschachtelten Gittern ist die Flexibilität der Wahl der Grobgitter. Diese können beispielsweise unabhängig mit Standardverfahren generiert werden. Die Auflösung des Randes des tatsächlichen Rechengebiets in den konstruierten Grobgitterräumen ist eine Eigenschaft der entwickelten Verfahrensklasse. <br /> Die flexible Einsetzbarkeit und die Effizienz der vorgestellten Lösungsverfahren zeigt sich in einer Reihe von numerischen Experimenten. Dazu geben wir Hinweise zur praktischen Umsetzung der semi-geometrischen Ideen und konkreter Transfer-Konzepte zwischen nicht-geschachtelten Gittern. Darüber hinaus wird eine Erweiterung zu einem semi-geometrischen monotonen Mehrgitterverfahren zur Lösung von Variationsungleichungen untersucht. Wir führen die Analysis der Konvergenz- bzw. Vorkonditionierungseigenschaften im Rahmen der Theorie der Teilraumkorrekturmethoden durch. Unsere technische Ausarbeitung liefert ein quasi-optimales Resultat, das wir mithilfe lokaler Argumente für allgemeine, shape-reguläre Gitterfamilien beweisen. Als relevante Eigenschaften der Operatoren zur Prolongation zwischen nicht-geschachtelten Finite-Elemente-Räumen erweisen sich die H¹-Stabilität und eine L²-Approximationseigenschaft sowie die Lokalität des Transfers. <br /> Diese Arbeit ist ein Beitrag zur Entwicklung schneller Löser für Gleichungen auf komplizierten Gebieten mit Schwerpunkt auf geometrischen Techniken (im Unterschied zu algebraischen). Verbindungen zu anderen Ansätzen werden sorgfältig aufgezeigt. Daneben untersuchen wir den Informationsaustausch zwischen nicht-geschachtelten Finite-Elemente-Räumen als solchen. In einer neuartigen Studie verbinden wir theoretische, praktische und experimentelle Überlegungen. Eine sorgfältige Prüfung der qualitativen Eigenschaften sowie eine quantitative Analyse der Unterschiede verschiedener Transfer-Konzepte zueinander führen zu neuen Ergebnissen bezüglich des Informationsaustauschs selbst. Schließlich erreichen wir durch die Einführung eines verallgemeinerten Projektionsoperators, der Pseudo-L²-Projektion, eine deutlich bessere Approximation der eigentlichen L²-orthogonalen Projektion als andere Ansätze aus der Literatur.