Solving an Elliptic PDE Eigenvalue Problem via Automated Multi-Level Substructuring and Hierarchical Matrices

Gerds, Peter; Grasedyck, Lars; Börm, Steffen

doi:HT019536477

Solving an Elliptic PDE Eigenvalue Problem via Automated Multi-Level Substructuring and Hierarchical Matrices = Lösen des elliptischen PDE Eigenwertproblems mithilfe der Automated Multi-Level Substructuring und der hierarchischen Matrizen

Gerds, Peter^RWTH*

2017

Verantwortlichkeitsangabevorgelegt von Peter Gerds

ImpressumAachen 2017

Umfang181 Seiten : Illustrationen

Dissertation, RWTH Aachen University, 2017

Veröffentlicht auf dem Publikationsserver der RWTH Aachen University

Genehmigende Fakultät
Fak01

Hauptberichter/Gutachter
Grasedyck, Lars (Thesis advisor) ; Börm, Steffen (Thesis advisor)

Tag der mündlichen Prüfung/Habilitation
2017-10-10

Online
DOI: 10.18154/RWTH-2017-10520
URL: http://publications.rwth-aachen.de/record/710880/files/710880.pdf

Einrichtungen

Inhaltliche Beschreibung (Schlagwörter)
approximated eigensolutions (frei) ; automated multi-level substructuring (frei) ; elliptic PDE eigenvalue problem (frei) ; finite element method (frei) ; hierarchical matrices (frei)

Thematische Einordnung (Klassifikation)
DDC: 510

Kurzfassung
Elliptische PDE Eigenwertprobleme werden in der Praxis typischerweise mithilfe der Finite-Element-Diskretisierung gelöst. Aus der Approximationstheorie ist bekannt, dass nur die kleinsten Eigenwerte und die zugehörigen Eigenfunktionen sich gut durch die Finite-Element-Diskretisierung approximieren lassen, da der entsprechende Approximationsfehler mit der Größe des Eigenwertes wächst. Resultate bezüglich der Anzahl der gut approximierbaren Eigenwerte und Eigenfunktionen sind bisher aber noch unbekannt. In dieser Arbeit werden Abschätzungen hergeleitet, die es erlauben diese Größen asymptotisch zu beschreiben. So wird zum Beispiel gezeigt, dass für drei-dimensionale Probleme (unter bestimmten Glattheitsbedingungen der Daten) nur die kleinsten $\Theta (N^{2/5})$ Eigenwerte und die Eigenfunktionen zu den kleinsten $\Theta (N^{1/4})$ Eigenwerten gut durch die Finite-Element-Diskretisierung approximierbar sind, wenn $N$-dimensionale Finite-Element-Räume mit stückweise affinen Funktionen bei gleichmäßiger Gitterverfeinerung verwendet werden. Um das diskretisierte elliptische PDE Eigenwertproblem zu lösen und um alle gut approximierbaren Eigenwerte und Eigenfunktionen zu berechnen, wird in dieser Arbeit eine neue Methode vorgestellt, welche eine rekursive Version der Automated Multi-Level Substructuring (kurz AMLS) Methode mit dem Konzept der hierarchischen Matrizen (kurz $\mathcal{H}$-Matrix) kombiniert. AMLS ist eine Gebietszerlegungsmethode zum Lösen elliptischer PDE Eigenwertprobleme, bei der nach einer bestimmten Problemtransformation ein reduziertes Eigenwertproblem aufgestellt wird. Die Eigenlösungen des reduzierten Problems liefern schließlich Approximationen der gesuchten Eigenlösungen des Ausgangsproblems. Die klassische AMLS Methode ist sehr effizient für PDE Eigenwertprobleme definiert auf einem zwei-dimensionalen Gebiet, jedoch wird die Methode sehr teuer für drei-dimensionale Probleme, da in AMLS das reduzierte Problem mittels vollbesetzter Matrixoperationen berechnet wird. In dieser Arbeit wird dieses Effizienzproblem von AMLS durch den Einsatz von hierarchischen Matrizen gelöst. $\mathcal{H}$-Matrizen sind kosteneffiziente Approximation von vollbesetzten Matrizen, welche beispielsweise auftreten bei der Invertierung der Steifigkeitsmatrix der Finite-Element-Diskretisierung elliptischer PDE Operatoren. Der große Vorteil von $\mathcal{H}$-Matrizen ist, dass diese eine Matrixarithmetik mit fast linearer Komplexität ermöglichen. Diese schnelle $\mathcal{H}$-Matrixarithmetik wird verwendet um das reduzierte Problem zu berechnen. Darüber hinaus wird die Größe des reduzierten Problems durch eine neue rekursive Version von AMLS beschränkt, was die Kosten für das Aufstellen und das Lösen des reduzierten Problems weiter verringert. Insgesamt führt dies zu einer neuen Methode, welche sehr gut geeignet ist um drei-dimensionale elliptische PDE Eigenwertprobleme zu lösen und welche eine Vielzahl von Eigenpaar Approximationen in optimaler Komplexität berechnet.

To solve an elliptic PDE eigenvalue problem in practice, typically the finite element discretisation is used. From approximation theory it is known that only the smaller eigenvalues and their corresponding eigenfunctions can be well approximated by the finite element discretisation because the approximation error increases with increasing size of the eigenvalue. The number of well approximable eigenvalues or eigenfunctions, however, is unknown. In this work asymptotic estimates of these quantities are derived. For example, it is shown that for three-dimensional problems under certain smoothness assumptions on the data only the smallest $\Theta (N^{2/5})$ eigenvalues and only the eigenfunctions associated to the smallest $\Theta (N^{1/4})$ eigenvalues can be well approximated by the finite element discretisation, when the $N$-dimensional finite element spaces of piecewise affine functions with uniform mesh refinement are used. To solve the discretised elliptic PDE eigenvalue problem and to compute all well approximable eigenvalues and eigenfunctions, a new method is introduced which combines a recursive version of the automated multi-level substructuring (short AMLS) method with the concept of hierarchical matrices (short $\mathcal{H}$-matrices). AMLS is a domain decomposition technique for the solution of elliptic PDE eigenvalue problems where, after some transformation, a reduced eigenvalue problem is derived whose eigensolutions deliver approximations of the sought eigensolutions of the original problem. Whereas the classical AMLS method is very efficient for elliptic PDE eigenvalue problems posed in two dimensions, it is getting very expensive for three-dimensional problems, due to the fact that it computes the reduced eigenvalue problem via dense matrix operations. This problem is resolved by the use of hierarchical matrices. $\mathcal{H}$-matrices are a data-sparse approximation of dense matrices which, e.g., result from the inversion of the stiffness matrix that is associated to the finite element discretisation of an elliptic PDE operator. The big advantage of $\mathcal{H}$-matrices is that they provide matrix arithmetic with almost linear complexity. This fast $\mathcal{H}$-matrix arithmetic is used for the computation of the reduced eigenvalue problem. Beside this, the size of the reduced eigenvalue problem is bounded by a new recursive version of AMLS which further reduces the costs for the computation and the solution of this problem. Altogether this leads to a new method which is well-suited for three-dimensional problems and which allows us to compute a large amount of eigenpair approximations in optimal complexity.

OpenAccess:
PDF
(additional files)