Adaptive und parallele Algorithmen zur Lösung partieller Differentialgleichungen mit variablen Koeffizienten auf dünnen Gittern

Abstract

Finite element methods are used to solve partial differential equations numerically. They are characterized by high accuracy and accurate convergence theory. However, they can hardly be used efficiently for partial differential equations of higher dimensions d>3, since the computational effort increases with the order O(Nd), where N is the number of unknowns in one spatial direction. Furthermore, classic parallelization techniques, such as domain decomposition, do not allow a reduction in the computational effort, since they are inefficient at higher dimensions. Theoretically, a hierarchical approach can significantly reduce the computational effort in higher dimensions. This approach is called sparse grids. It leads to only O(N 〖log⁡(N)〗^(d-1)) grid points compared to O(Nd) grid points of classic full finite element grids. However, it is not trivial to develop algorithms, which numerically solve partial differential equations with a computational effort of the same order. In previous scientific work, algorithms were developed that can only be used in case of simple coefficients in the differential equation or in case of non-adaptive grids. In this research project, novel algorithms were developed that enable a much wider range of applications. On the one hand, locally adaptive thin grids could be created, which also allow discretization of partial differential equations with variable coefficients. To this end, locally adaptive sparse grids were developed, which also allow discretization of partial differential equations with variable coefficients. The concept of this discretization extends the discretization of semi-orthogonality with prewavelets as hierarchical basis functions in a suitable way. The discretization of general variable coefficients is particularly difficult. In previous work, only variable coefficients that have a tensor product structure were considered in numerical simulations. This makes both the storage and the calculation of the local stiffness matrices much easier than with general variable coefficients. The reason for the high computational effort for general coefficients is the anisotropy of the geometry of local stiffness elements and that the resulting local stiffness matrix has O((2d)2) = O(4d) entries. These problems were solved by a suitable Monte Carlo calculation of the local stiffness matrices. In order to obtain simulation results even in case of high dimensions d=4-6, suitable parallelization techniques for high-performance computers were developed. Simulation results show good convergence of the new finite element method even in case of high dimensions d = 4-6, in case of difficult variable coefficients with singularities and in case of solutions that require locally refined adaptive grids.

Finite-Elemente-Verfahren werden verwendet um partielle Differentialgleichungen numerisch zu lösen. Sie zeichnen sich durch eine hohe Genauigkeit und eine genaue Konvergenztheorie aus. Bei partiellen Differentialgleichungen höherer Dimension d>3 können sie jedoch effizient kaum angewendet werden, da der Rechenaufwand mit der Ordnung O(Nd) ansteigt, wobei N die Anzahl der Unbekannten in einer Raumrichtung ist. Klassische Parallelisierungstechniken, wie der Gebietszerlegung sind bei höheren Dimensionen sehr ineffizient, so dass diese eine Reduzierung des Rechenaufwandes nicht ermöglichen. Durch einen hierarchischen Ansatz kann der Rechenaufwand in höheren Dimensionen theoretisch wesentlich verringert werden. Dieser führt zu sogenannten dünnen Gittern, die nur O(N log(N)d-1) Gitterpunkte im Vergleich zu O(Nd) Gitterpunkten von klassischen vollen Finite-Elemente-Gittern besitzen. Es ist jedoch nicht trivial Algorithmen zu entwickeln, die numerisch partielle Differentialgleichungen mit ei-nem Rechenaufwand von der gleichen Ordnung lösen. In früheren wissenschaftlichen Arbeiten wurden hierzu Algorithmen entwickelt, die nur bei einfachen Koeffizienten in der Differential-gleichung oder nur bei nicht adaptiven Gittern angewendet werden können. Im vorliegenden Forschungsprojekt wurden neuartige Algorithmen entwickelt, die eine wesentlich größere An-wendungsbreite ermöglichen. Zum einen konnten lokal adaptive dünne Gitter erzeugt werden, die auch eine Diskretisierung von partiellen Differentialgleichungen mit variablen Koeffizienten erlauben. Hierbei wurde das Konzept der Diskretisierung mit Semi-Orthogonalität mit Prewa-velets als hierarchische Basisfunktionen geeignet erweitert. Schwierig ist insbesondere die Diskretisierung von allgemeinen variablen Koeffizienten. In vorherigen Arbeiten wurden bei numerischen Simulationen nur variable Koeffizienten betrachtet, die eine Tensorproduktstruk-tur aufweisen. Dadurch ist sowohl die Speicherung als auch die Berechnung der lokalen Stei-figkeitsmatrizen wesentlich einfacher als bei allgemeinen variablen Koeffizienten. Der Grund für den hohen Rechenaufwand bei allgemeinen Koeffizienten ist die Anisotropie der Geometrie lokaler Steifigkeitselemente und dass die entstehende lokale Steifikeitsmatrix O((2d)2) = O(4d) Einträge besitzt. Diese Probleme wurden mit einen geeigneten Monte-Carlo-Berechnung der lokalen Steifigkeitsmatrizen gelöst. Um Simulationsergebnisse auch bei hohen Dimensionen d=4,6 zu erhalten wurden geeignete Parallelisierungstechniken für Hochleistungsrechner ent-wickelt. Die Simulationsergebnisse zeigen eine gute Konvergenz des Finite-Elemente-Verfahrens auch bei hohen Dimensionen d=4,6, bei schwierigen variablen Koeffizienten mit Singularitäten und bei Lösungen, die eine lokale adaptive Verfeinerung der Gitter verlangen.