Approximation inverser Finite Elemente- und Randelementematrizen mittels hierarchischen Matrizen

Abstract

Die vorliegende Arbeit beschäftigt sich mit der Approximierbarkeit inverser Matrizen, die aus der Diskretisierung verschiedener partieller Differentialgleichungen mittels Finiter Elemente Methode oder Randelementmethode erhalten werden, im Matrixkompressionsformat der hierarchischen Matrizen. Das Konzept der hierarchischen Matrizen erlaubt die Speicherung sowie (approximative) arithmetische Operationen in logarithmisch linearer Komplexität. Da inverse Finite Elemente- und Randelementmatrizen im Allgemeinen vollbesetzt sind und daher Speicherung und Rechnungen mit diesen ineffizient sind, ist die sinnvolle Approximierbarkeit dieser Matrizen durch hierarchische Matrizen wünschenswert. In dieser Arbeit wird gezeigt, dass Approximationen an inverse Finite Elemente Matrizen für elliptische partielle Differentialgleichungen zweiter Ordnung mit gemischten Randbedingungen sowie für die Lame-Gleichung existieren und der auftretende Fehler exponentiell im Rang der Approximation konvergiert. Unsere Resultate erweitern die bisher bekannten theoretischen Aussagen, welche nur elliptische partielle Differentialgleichungen zweiter Ordnung und die Lame-Gleichung jeweils mit Dirichlet-Randbedingungen behandelt und Genauigkeit bis zum Diskretisierungsfehler gezeigt haben, auf generellere Randbedingungen und liefern Approximationen mit beliebiger Genauigkeit. Für inverse Randelementmatrizen ist die Anwendbarkeit von hierarchischen Matrizen bisher nur numerisch beobachtet worden. Eines der Hauptresultate dieser Arbeit ist der Beweis der Existenz einer Approximation an inverse Matrizen zu Diskretisierungen des Einfachschichtoperators sowie des hypersingulären Integraloperators, was eine theoretische Grundlage für den numerisch beobachteten, erfolgreichen Einsatz der hierarchischen Matrizen liefert. Im Gegensatz zu den bestehenden Ansätzen in der Literatur wird eine volldiskrete Approximation konstruiert, wodurch keine Einschränkung an die Genauigkeit der Approximation entsteht. Ein entscheidender Schritt hierbei ist der Beweis einer diskreten inneren Regularitätsabschätzung, ähnlich zu der klassischen Caccioppoli-Ungleichung. Neben der Approximation von inversen Matrizen wird auch die Existenz approximativer Cholesky- und LU-Zerlegungen für die erwähnten Finite Elemente- und Randelementdiskretisierungen untersucht. Mit Hilfe der Approximation gewisser Schurkomplemente durch blockweise Niedrigrangmatrizen können wir die Existenz approximativer Cholesky- und LU-Zerlegungen im Format der hierarchischen Matrizen zeigen. Diese Faktorisierungen können beispielsweise zur Black-Box-Vorkonditionierung für iterative Lösungsverfahren verwendet werden. Schlussendlich werden numerische Beispiele angegeben, die die theoretischen Resultate untermauern.

This thesis is concerned with the existence of approximations to the inverses of matrices that are obtained from finite element or boundary element discretizations of some partial differential equations. The approximation is performed in the format of hierarchical matrices. The concept of hierarchical matrices permits to store as well as to apply some (approximate) arithmetic operations in logarithmic linear complexity. The inverses of finite element and boundary element matrices are dense in general, which leads to slow computations and large amounts of memory consumption. Therefore, the approximability of these matrices by hierarchical matrices is desirable. In this thesis, we show that approximations to inverses of finite element matrices for second order elliptic partial differential equations with mixed boundary conditions and for the Lam'e equation exist, and the error converges exponentially in the block-rank of the approximation. Our results generalize the known theoretical results for elliptic partial differential equations and the Lame system with Dirichlet boundary conditions to more general boundary conditions. Moreover, the existence of approximations with arbitrary accuracy is proven, whereas the previous results only achieved accuracy up to the discretization error. For the inverses of boundary element matrices the applicability of hierarchical matrices has only been observed numerically. One of the main results of this work is the proof of existence of an approximation to the inverse matrices corresponding to discretizations of the single-layer and the hypersingular integral operator. These results give a mathematical foundation to the numerically observed success of hierarchical matrices for the approximation of inverse matrices. In contrast to the known results in the literature, we work in a fully discrete setting, which leads to approximations of arbitrary accuracy. A main ingredient for our purpose is the proof of a discrete interior regularity result similar to the classical Caccioppoli inequality. Besides the approximations to inverse matrices, we are also concerned with the existence of approximative Cholesky- and LU-decompositions for the above mentioned finite element and boundary element discretizations. By approximating certain Schur complements by some blockwise low rank factorizations, we are able to prove the existence of approximate Cholesky- and LU-decompositions in the format of hierarchical matrices. For example, these factorizations can be used for black-box preconditioning in iterative solvers. A series of numerical examples is given, which confirm the theoretical results.