Effiziente Verfahren zur Lösung partieller Differentialgleichungen mit variablen Koeffizienten auf dünnen Gittern

Language
de
Document Type
Doctoral Thesis
Issue Date
2018-07-02
Issue Year
2018
Authors
Hartmann, Rainer
Editor
Abstract

This thesis offers an efficient solution for highly dimensional, elliptic partial differential equations on sparse grids. The discretization applies the Galerkin method and the finite element method. In order to ensure an efficient implementation, an effective matrix-vector-multiplication, whose complexity scales linearly with the number of grid points of the sparse grid, is required. For this end an algorithm will be presented, which collects and distributes the hierarchical surplus through traversing over all grids using a combination of restriction and prolongation operators. Sparse grips, however, skip some paths compared to full grids. Thanks to the semi-orthogonality this does not influence the convergence, with prewavelets being -orthogonal for overlapping basis functions. A convergence proof shows that this orthogonality holds also for variable coefficients since the induced errors by the semi-orthogonality property are small. In contrast to full grids the number of unknowns decreases dramatically, whereas the order of convergence is only slightly reduced for the discretization of sparse grids.

Numerical results with variable coefficients show an optimal convergence behavior for three- and six-dimensional problems. Transformations for curvilinear bounded domains have variable coefficients and are not based on tensor products. The calculation of the coefficients of the system matrix utilizes numerical integration in high dimensions. The matrix-vector multiplication is reduced to one-dimensional operators via recursion. In the scope of this work a comprehensive software framework has been created. By using templates, the implementation can be applied to arbitrary dimensions. A parallelization for distributed memory, as well as shared memory, guarantees a high accuracy for higher dimensions. An approach of semi-adaptive refinement enables a partial refinement, while maintaining the structure of a tensor product grid. This dissertation concludes with an outlook on the implementation of fully adaptive sparse grids.

Abstract

Ziel dieser Arbeit ist die effiziente L\osung hochdimensionaler elliptischer partieller Differentialgleichungen auf d\unnen Gittern. Bei Diskretisierung wird der Galerkin-Ansatz und die Finite-Elemente-Methode verwendet. Eine effiziente Implementierung der Matrix-Vektor-Multiplikation skaliert linear mit der Anzahl der Gitterpunkte. Dazu wird ein Algorithmus vorgestellt, der durch eine Kombination von Restriktionen und Prolongationen die hierarchischen \Ubersch\usse aller Gitter einsammelt und verteilt. F\ur d\unne Gitter muss allerdings auf den Austausch zwischen einigen Gittern verzichtet werden. Dies hat aufgrund der Semi-Orthogonalit\at keinen Einfluss auf die Konvergenz, da Prewavelets f\ur \uberlappende Gebiete -orthogonal sind. Bei variablen Koeffizienten zeigt ein Konvergenzbeweis, dass diese Werte sehr klein sind und keinen Einfluss auf die Konvergenz haben. Die Konvergenzordnung der D\unngitterdiskretisierung reduziert sich im Vergleich zu vollen Gittern nur leicht, w\ahrend die Anzahl der Unbekannten dramatisch abnimmt.

Numerische Ergebnisse mit variablen Koeffizienten zeigen optimale Konvergenz f\ur dreidimensionale und sechsdimensionale Probleme. Transformationen f\ur krummlinig umrandete Gebiete besitzen variable Koeffizienten und beruhen nicht auf einem Tensorprodukt. Die Berechnung der Steifigkeitsmatrix verwendet eine hochdimensionale numerische Integration. Multiplikationen werden durch Rekursion auf eindimensionale Operatoren zur\uckgef\uhrt. Dazu ist im Rahmen dieser Arbeit eine umfangreiche Softwarebibliothek entstanden. Durch die Verwendung von Templates kann die Implementierung auf beliebige hochdimensionale Probleme angewendet werden. Parallelisierung sowohl f\ur geteilten Speicher als auch verteilte Systeme gew\ahrleistet eine hohe Genauigkeit f\ur gro\ss{}e Dimensionen. Ein Ansatz mit semi-adaptiver Verfeinerung erm\oglicht partielle Verfeinerung bei gleichzeitigem Erhalt der Tensorprodukt-Struktur. Die Umsetzung adaptiver d\unner Gitter wird als Ausblick behandelt.

DOI
Faculties & Collections
Zugehörige ORCIDs