Multilevel Adaptive Techniques for Higher-Order Finite Differences in Elliptic Problems with Interfaces

Language
en
Document Type
Doctoral Thesis
Issue Date
2015-05-29
Issue Year
2015
Authors
Ritter, Daniel
Editor
Abstract

Hermitian methods, also known as Mehrstellenverfahren (MSV), are a class of finite-difference (FD)discretization schemes for partial differential equations (PDEs) that have fourth or higher error order and lead to compact stencil operators. Their high order is achieved by forcing the fulfillment of the governing PDE also at neighboring locations of the current grid point, i.e., by averaging the right-hand side of the PDE. Multigrid (MG) methods are efficient, iterative solvers for sparse linear systems, such as those resulting from a PDE that is discretized with an MSV. Based on the combination of local smoothing methods, e.g. Gauss-Seidel iterations, with a coarse-grid error correction, MG methods achieve efficient error elimination over all frequencies. The focus of this thesis is on the derivation of MSV schemes and their application to elliptic PDEs. Out of the various fields where these PDEs occur, examples from quantum electro-chemistry are chosen. Here, interfaces are of special interest: These can be found in the model equation, leading to a transition in the conductivity coefficient of the PDE that can be either modeled by a smooth variation or by a jump, as well as in the discretization, if hierarchical refined grids are coupled. For both cases, the combination of MSV schemes with MG solvers leads to an efficient and precise solution of the PDE. For interfaces in the model equation, different MSV schemes are developed for both the smooth and the discontinuous coefficient, and experiments are performed to compare these approaches. A systematic stencil generation algorithm is introduced, based on Taylor expansions and least-squares optimization. This algorithm can produce both variants. Besides a comparison of the MSV scheme with linear finite elements, enhanced by Tau-extrapolation, the smooth and discontinuous schemes are compared before different variants of MSVs are integrated into the RSDFT software. Within that framework they are applied for the solution of the potential equation and for the calculation of electron-electron interactions. The resulting systems of equations are solved by MG, in particular, by applying V-cycles. Convergence properties, run times of different solver configurations, and errors in the potential and energy terms are analyzed for different MSV approaches. A staggered coefficient MSV variant that is very efficient to establish competes with the aligned coefficient MSV in all means except the error in the potential. For interfaces between grids, the fast adaptive composite (FAC) grid approach is used to simulate open boundary conditions in the potential equation. Hence, grids of different mesh widths are coupled, i.e., coarser grids expand the original domain. Error analysis shows that the original FAC coupling does not preserve the error order of the discretization method, if the latter is not adapted at the interfaces between two grids. Therefore, a slight change in the algorithm is made, introducing higher-order interpolation as the prolongation operator. This approach can restore the original error order, demonstrated for a seven-point FD as well as for the corresponding MSV discretization.

Abstract

Hermitesche Methoden bzw. Mehrstellenverfahren (MSV) bezeichnen eine Klasse von Diskretisierungen für partielle Differentialgleichungen (PDEs) mittels finiter Differenzen (FD), die vierte oder höhere Fehlerordnung besitzen und zu kompakten Stencil-Operatoren führen. Die hohe Ordnung wird dadurch erreicht, dass die Erfüllung der PDE auch an benachbarten Gitterpunkten erzwungen wird, indem die rechte Seite der PDE gemittelt wird. Mehrgittermethoden (MG) zählen zu den effizientesten iterativen Lösungsverfahren für schwachbesetzte lineare Systeme, wie sie bei der Diskretisierung einer PDE mit MSV entstehen. Durch die Kombination eines lokalen Glätters, wie z.B. der Gauß-Seidel-Iteration, mit der Fehlerkorrektur auf einem gröberen Gitter können MG Fehler über alle Frequenzen eliminieren. Im Mittelpunkt dieser Arbeit steht die Herleitung von MSV-Stencils sowie deren Anwendung auf elliptische PDEs. Es werden Beispiele aus der Quanten-Elektrochemie betrachtet, einer von vielen Disziplinen, in denen diese Differentialgleichungen Verwendung finden. Grenzflächen, bzw. Interfaces, sind hier von herausragender Bedeutung: Sie können sowohl in den Modellgleichungen selbst auftreten, wobei sie zu einem variablen Koeffizienten führen, der entweder durch einen glatte Veränderung oder einen Sprung modelliert werden kann, als auch in der Diskretisierung zwischen gekoppelten, hierarchisch verfeinerten Gittern vorkommen. In beiden Fällen können MSV mit MG kombiniert werden, um PDEs effizient und präzise zu lösen. Für Grenzflächen in der Modellgleichung werden MSV sowohl für glatte als auch für springende Koeffizienten entwickelt und anschließend experimentell miteinander verglichen. Basierend auf Taylor-Entwicklungen und der Methode der kleinsten Quadrate wird ein Algorithmus zur systematischen Synthese von MSV-Stencils vorgestellt, der für beide Varianten verwendet werden kann. Das Fehlerverhalten des MSV wird mit dem der Tau-Extrapolation verglichen. Darüber hinaus werden die Schemata für glatte und springenden Koeffizienten einander gegenüber gestellt, bevor die Integration verschiedener Varianten von MSV in die Software RSDFT beschrieben wird. Hier werden die Diskretisierungen für die Lösung der Potentialgleichung und somit für die Berechnung von Elektron-Elektron-Wechselwirkungen verwendet. Die resultierenden linearen Gleichungssysteme werden dann mit einem MG gelöst, indem V-Zyklen ausgeführt werden. Für die verschiedenen MSV werden Konvergenzraten, Laufzeiten für verschiedene Konfigurationen des Lösers sowie die Fehler im Potential und der Energie miteinander verglichen. Es zeigt sich, dass sich ein effizient zu berechnendes MSV mit gestaffelten (staggered) Koeffizienten sich, bis auf den Fehler des Potentials, genauso verhält wie die aufwändigere Variante, in der die Koeffizienten auf einem ausgerichteten (aligned) Gitter diskretisiert sind. Für Grenzflächen bei der Kopplung von Gittern wird der sogenannte Fast Adaptive Composite (FAC) Ansatz verwendet, um offene Randbedingungen in der Potentialgleichung zu simulieren. Dafür wählt man eine Gitterhierarchie, in der die gröberen Gitter das Simulationsgebiet vergrößern, und koppelt diese miteinander. Die Fehleranalyse zeigt, dass die Fehlerordnung einer Diskretisierung mit dem ursprünglichen FAC ohne eine Anpassung der Diskretisierungsoperatoren an den Grenzflächen zwischen zwei Gittern nicht erhalten werden kann. Jedoch kann unter Verwendung von Interpolationsverfahren höherer Ordnung zur Prolongation die ursprüngliche Fehlerordnung wiederhergestellt werden. Dies wird in Tests sowohl für den Sieben-Punkt-Stern als auch für das entsprechende MSV gezeigt.

DOI
Faculties & Collections
Zugehörige ORCIDs