Universität zu Köln

Pabel, Roland (2015). Adaptive Wavelet Methods for Variational Formulations of Nonlinear Elliptic PDES on Tensor-Product Domains. PhD thesis, Universität zu Köln.

Preview

PDF pabel_phd.pdf - Submitted Version Download (22MB)

Abstract

This thesis is concerned with the numerical solution of boundary value problems (BVPs) governed by semilinear elliptic partial differential equations (PDEs). Semilinearity here refers to a special case of nonlinearity, i.e., the case of a linear operator combined with a nonlinear operator acting as a perturbation. In general, such BVPs are solved in an iterative fashion. It is, therefore, of primal importance to develop efficient schemes that guarantee convergence of the numerically approximated PDE solutions towards the exact solution. Unlike the typical finite element method (FEM) theory for the numerical solution of the nonlinear operators, the new adaptive wavelet theory proposed in [Cohen.Dahmen.DeVore:2003:a, Cohen.Dahmen.DeVore:2003:b] guarantees convergence of adaptive schemes with fixed approximation rates. Furthermore, optimal, i.e., linear, complexity estimates of such adaptive solution methods have been established. These achievements are possible since wavelets allow for a completely new perspective to attack BVPs: namely, to represent PDEs in their original infinite dimensional realm. Wavelets are the ideal candidate for this purpose since they allow to represent functions in infinite-dimensional general Banach or Hilbert spaces and operators on these. The purpose of adaptivity in the solution process of nonlinear PDEs is to invest extra degrees of freedom (DOFs) only where necessary, i.e., where the exact solution requires a higher number of function coefficients to represent it accurately. Wavelets in this context represent function bases with special analytical properties, e.g., the wavelets considered herein are piecewise polynomials, have compact support and norm equivalences between certain function spaces and the l_2 sequence spaces of expansion coefficients exist. This new paradigm presents nevertheless some problems in the design of practical algorithms. Imposing a certain structure, a tree structure, remedies these problems completely while restricting the applicability of the theoretical scheme only very slightly. It turns out that the considered approach naturally fits the theoretical background of nonlinear PDEs. The practical realization on a computer, however, requires to reduce the relevant ingredients to finite-dimensional quantities. It is this particular aspect that is the guiding principle of this thesis. This theoretical framework is implemented in the course of this thesis in a truly dimensionally unrestricted adaptive wavelet program code, which allows one to harness the proven theoretical results for the first time when numerically solving the above mentioned BVPs. In the implementation, great emphasis is put on speed, i.e., overall execution speed and convergence speed, while not sacrificing on the freedom to adapt many important numerical details at runtime and not at the compilation stage. This means that the user can test and choose wavelets perfectly suitable for any specific task without having to rebuild the software. The computational overhead of these freedoms is minimized by caching any interim data, e.g., values for the preconditioners and polynomial representations of wavelets in multiple dimensions. Exploiting the structure in the construction of wavelet spaces prevents this step from becoming a burden on the memory requirements while at the same time providing a huge performance boost because necessary computations are only executed as needed and then only once. The essential BVP boundary conditions are enforced using trace operators, which leads to a saddle point problem formulation. This particular treatment of boundary conditions is very flexible, which especially useful if changing boundary conditions have to be accommodated, e.g., when iteratively solving control problems with Dirichlet boundary control based upon the herein considered PDE operators. Another particular feature is that saddle point problems allow for a variety of different geometrical setups, including fictitious domain approaches. Numerical studies of 2D and 3D PDEs and BVPs demonstrate the feasibility and performance of the developed schemes. Local transformations of the wavelet basis are employed to lower the absolute condition number of the already optimally preconditioned operators. The effect of these basis transformations can be seen in the absolute runtimes of solution processes, where the semilinear PDEs are solved as fast as in fractions of a second. This task can be accomplished using simple Richardson-style solvers, e.g., the method of steepest descent, or more involved solvers like the Newton's method. The BVPs are solved using an adaptive Uzawa algorithm, which requires repeated solution of semilinear PDE sub-problems. The efficiency of different numerical methods is compared and the theoretical optimal convergence rates and complexity estimates are verified. In summary, this thesis presents for the first time a numerically competitive implementation of a new theoretical paradigm to solve semilinear elliptic PDEs in arbitrary space dimensions with a complete convergence and complexity theory.

Item Type:	Thesis (PhD thesis)
Translated title:	Title Language Adaptive Waveletmethoden für Variationsformulierungen von Nichtlinearen Elliptischen PDEs auf Tensorprodukt Gebieten German
Translated abstract:	Abstract Language Diese Arbeit behandelt adaptive Waveletmethoden zur numerischen Lösung semilinearer partieller Differentialgleichungen (PDEs) und Randwertprobleme (BVPs) basierend auf solchen PDEs. Semilineare PDEs sind Spezialfälle aus der Klasse der allgemeinen nichtlinearen PDEs, hier besteht die PDE aus einem linearen Operator und einem nichtlinearen Störungsterm. Im Allgemeinen werden solche BVPs mit iterativen Verfahren gelöst. Es ist daher von höchster Wichtigkeit, effiziente als auch konvergente Lösungsverfahren für die zugrunde liegenden nichtlinearen PDEs zur Verfügung zu haben. Im Gegensatz zu Finite-Elemente-Methoden (FEM) garantieren die adaptive Waveletmethoden aus [Cohen.Dahmen.DeVore:2003:a, Cohen.Dahmen.DeVore:2003:b], dass Lösungen nichtlinearer PDEs mit konstanten Approximationsraten berechnet werden können. Des Weiteren wurden optimale, d.h. lineare, Komplexitätsabschätzungen für diese adaptiven Lösungsmethoden nachgewiesen. Diese Errungenschaften sind nur möglich, weil Wavelets einen neuartigen Ansatz zur Lösung von BVPs ermöglichen: die PDE wird in ihrer ursprünglichen unendlichdimensionalen Formulierung behandelt. Wavelets sind der ideale Kandidat für diesen Zweck, da sie es erlauben sowohl Funktionen als auch Operatoren in unendlichdimensionalen Banach- und Hilberträumen exakt darzustellen. Der Zweck adaptiver Verfahren im Lösungsprozess von PDEs ist die Einsetzung von Freiheitsgraden (DOFs) nur dort wo notwendig, d.h. an Stellen wo die exakte Lösung unglatt ist und nur durch eine höhere Anzahl von Funktionskoeffizienten präzise beschrieben werden kann. In diesem Zusammenhang stellen Wavelets eine Basis mit besonderen Eigenschaften für die betrachteten Funktionenräume dar. Die benutzten Wavelets sind stückweise polynomial, haben kompakten Träger und es bestehen Normäquivalenzen zwischen den Funktionenräumen und den l_2 Folgenräumen der Entwicklungskoeffizienten. Dieser neue Ansatz zieht einige Probleme für das Design der numerischen Algorithmen nach sich, welche aber durch eine Struktur der Waveletkoeffizienten, genauer gesagt eine Baumstruktur, komplett ausgeräumt. Diese Baumstruktur bedeutet dabei nur eine geringfügige Einschränkung in der theoretischen Anwendbarkeit in Bezug auf Funktionenräume. Es stellt sich heraus, dass der aufgezeigte Ansatz genau auf den funktionalanalytischen Hintergrund nichtlinearer PDEs passt. Die praktische Umsetzung auf einem Computer erfordert dabei aber eine Einschränkung der unendlichdimensionalen Darstellungen auf endlichdimensionale Quantitäten. Es ist genau dieser Aspekt, der das Leitmotiv dieser Arbeit darstellt. Diese theoretischen Vorgaben wurde im Rahmen dieser Arbeit in einem neuen vollständig dimensionsunabhängigen adaptiven Waveletprogrammpaket umgesetzt. Dieses erlaubt zum ersten Mal die bewiesenen theoretischen Resultate zur numerischen Lösung der oben genannten Randwertprobleme zu nutzen. Für diese Arbeit sind sowohl theoretische als auch numerische Aspekte von höchster Bedeutung. Großer Wert wurde dabei auf die Optimierung der Geschwindigkeit gelegt, ohne dabei die Möglichkeit zu verlieren, verschiedene numerische Parameter noch zur Laufzeit verändern zu können. Dies bedeutet, dass der Benutzer verschiedenste Aspekte, wie z.B. die verwendete Waveletkonstruktion, austauschen und testen kann, ohne die Software neu kompilieren zu müssen. Der zusätzliche Rechenaufwand für diese Optionen wird während der Laufzeit des Programms durch verschiedene Arten von Zwischenspeichern, z.B. das Abspeichern der Werte des Vorkonditionierers oder die polynomielle Darstellung der mehrdimensionalen Wavelets, so klein wie möglich gehalten. Die Ausnutzung der Struktur in der Konstruktion der Waveleträume verhindert, dass das Zwischenspeichern eine große Menge im Speicher des Computers belegt. Gleichzeitig ermöglicht dies sogar eine Erhöhung der Ausführungsgeschwindigkeit, da die Berechnungen so nur noch ausgeführt werden, wenn sie notwendig sind, und dann auch nur ein einziges Mal. Die essentiellen Randbedingungen in den BVPs werden hier durch Spuroperatoren umgesetzt, was das Problem zu einem Sattelpunktsproblem macht. Diese spezielle Formulierung ist sehr flexibel; insbesondere wechselnde Randbedingungen, wie sie zum Beispiel im Rahmen von Kontrollproblemen mit Dirichlet-Randkontrolle auftreten, können sehr effizient behandelt werden. Ein weiterer Vorteil der Sattelpunktsformulierung ist, dass nicht-Tensorproduktgebiete durch den "Fictitious Domain"-Ansatz behandelt werden können. Numerische Studien von 2D und 3D BVPs und nichtlinearen PDEs demonstrieren die Möglichkeiten und die Leistungsfähigkeit dieser Algorithmen. Lokale Basistransformationen der Waveletbasen senken dabei die absoluten Konditionszahlen der schon optimal vorkonditionierten Operatoren. Der Effekt dieser Basistransformationen zeigt sich dabei in Verkürzungen der absoluten Laufzeit der eingesetzten Löser; im Idealfall kann dabei eine semilineare PDE innerhalb von Sekundenbruchteilen gelöst werden. Dies kann im einfachsten durch Fall Richardson-Verfahren, wie das Verfahren des steilsten Abstiegs, oder das aufwändigere Newton-Verfahren geschehen. Die BVPs werden mittels eines adaptiven Uzawa-Algorithmus gelöst; dieser erfordert das Lösen einer semilinearen PDE in jedem Schritt. Außerdem wird die Effektivität verschiedener numerischer Lösungsverfahren verglichen und es werden die optimalen Konvergenzraten und Komplexitätsabschätzungen verifiziert. Zusammenfassend präsentiert diese Arbeit zum ersten Mal eine numerisch wettbewerbsfähige Implementierung dieses neuartigen theoretischen Paradigmas zur Lösung von semilinearen elliptischen PDEs in beliebigen Raumdimensionen einschließlich Konvergenz- und Komplexitätsergebnissen. German
Creators:	Creators Email ORCID ORCID Put Code Pabel, Roland roland@pabel.name UNSPECIFIED UNSPECIFIED
URN:	urn:nbn:de:hbz:38-60938
Date:	May 2015
Language:	English
Faculty:	Faculty of Mathematics and Natural Sciences
Divisions:	Faculty of Mathematics and Natural Sciences > Department of Mathematics and Computer Science > Mathematical Institute
Subjects:	Mathematics
Uncontrolled Keywords:	Keywords Language Adaptivity;Wavelet;Variational Formulations;Boundary Value Problems;Nonlinear Partial Differential Equations;PDE;Tensor-Product Domains English
Date of oral exam:	18 May 2015
Referee:	Name Academic Title Kunoth, Angela Prof. Dr. Gassner, Gregor Prof. Dr. Harbrecht, Helmut Prof. Dr.
Refereed:	Yes
URI:	http://kups.ub.uni-koeln.de/id/eprint/6093