Dissertation (Metadaten)
Titel (original):Das Matrix-Galerkin-Verfahren
(übersetzt):The matrix Galerkin method
 
Autor:Dirk Boysen
 
URN:NBN:urn:nbn:de:gbv:8-diss-175003
 
Fakultät:Technische Fakultät
DDC Sachgebiet:510 Mathematik
 
Datum der mdl. Prüfung:19.08.2015
 
Referent(in):Prof. Dr. Steffen Börm
Korreferent(en) Korreferentin:Prof. Dr. Dr. Wolfgang Hackbusch, Prof. Dr. Lars Grasedyck
 
Beschreibung (original):Matrixgleichungen treten in diversen Anwendungsgebieten numerischer Mathematik auf. Da die Lösungen solcher Gleichungen i.A. vollbesetzt sind, besitzen selbst Lösungsverfahren optimaler Komplexität einen Aufwand von mindestens n^2 Operationen, wobei n hier die zugrundeliegende Dimension beschreibt. Häufig bilden Matrixgleichungen das diskrete Gegenstück eines zu lösenden, kontinuierlichen Problems, wie z.B. bei der Betrachtung bestimmter partieller Differentialgleichungen und deren Diskretisierung mit Tensor-Basisfunktionen. In diesen Fällen kann der Diskretisierungsfehler generell nur durch eine Erhöhung der Dimension n verringert werden. Aufgrund des mindestens quadratischen Aufwands direkter Lösungsverfahren sind diese nicht mehr praktikabel in hohen Dimensionen. Motiviert durch die vorherigen Betrachtungen wurde eine Vielzahl von Verfahren entwickelt, um Lösungen von Matrixgleichungen mit einem geringeren Rechenaufwand zu approximieren. Zu dieser Kategorie gehören auch H- und H2-Matrix-Techniken, welche einen Rechenaufwand in O(k^a n log^b(n)) aufweisen. Hierbei beschreiben a,b>=0 kleine Konstanten und k einen Parameter, der die Genauigkeit steuert. In der vorliegenden Arbeit wird ein neuartiger, auf H2-Matrizen basierender Ansatz zur Approximation von Lösungen linearer Matrixgleichungen vorgestellt. Der Grundgedanke ist hierbei, die zu behandelnde Matrixgleichung in eine Variationsformulierung zu überführen, um so zu einer Galerkin-Formulierung zu gelangen. Der Teilraum aller H2-Matrizen dient hierbei als Ansatzraum. Diese Vorgehensweise beruht auf einem der Grundgedanken der Finite-Elemente-Theorie, wodurch sich die dort gängige Lösungstheorie - Lemma von Lax-Milgram und Cea's Lemma - anwenden lässt, um so die Existenz sowie Stabilität einer eindeutigen Lösung zu zeigen. Eine nähere Untersuchung der Galerkin-Formulierung führt auf ein matrixwertiges Gleichungssystem, bei dem die Unbekannten durch Matrizen mit k^2 Einträgen gegeben sind (k << n). Die zu berechnende H2-Matrix-Approximation ergibt sich dann über das Lösen dieses Systems, z.B. durch iterative Verfahren. Aufgrund der speziellen hierarchischen Struktur von H2-Matrizen ist die Formulierung effizienter Algorithmen von zentraler Bedeutung. Zu diesen Algorithmen zählen insbesondere das Aufstellen, das Assemblieren sowie das Lösen des hergeleiteten Gleichungssystems. Unter plausiblen Annahmen wird gezeigt, dass alle verwendeten Algorithmen einen für H2-Matrizen typischen Aufwand in O(k^a n) aufweisen. Im Anschluss an die konkrete Definition des Matrix-Galerkin-Verfahrens sowie die Analyse aller im Rahmen dieser Arbeit benötigten Algorithmen folgen numerische Beispiele, die das Verhalten des neuen Ansatzes illustrieren.
 
(übersetzt):Matrix equations arise in many applications of numerical mathematics. Since solutions of these equations are generally densely populated, even solution strategies with optimal complexity need at least n^2 operations, with n being the underlying dimension. Frequently, matrix equations represent the discrete counterpart of some continuous problem, e.g., when derived from the discretization of certain partial differential equations with tensor basis functions. In these cases a reduction of the discretization error can only be achieved by increasing the dimension n. As a result of their at least quadratic complexity, direct solution methods are typically not feasible for large dimensions. Based on the aforementioned observations, a wide range of solution strategies have been developed that only approximate the solution, but with lower computational effort. These strategies comprise both H- and H2-matrix techniques that exhibit a complexity in O(k^a n log^b(n)) with small constants a,b>=0 and k being a parameter controlling the accuracy. This thesis presents a novel approach for approximating solutions of linear matrix equations by using H2-matrices. The basic idea is to translate the underlying matrix equation into a variational formulation in order to apply a Galerkin method. To this end the subspace of H2-matrices is employed as trial space. This approach is based on the commonly used practice in the field of finite elements. Thus the same solution theory - namely the lemma of Lax-Milgram and Cea's lemma - is applicable, which allows to proof the existence and stability of a unique solution. Further investigations show that the employed Galerkin method results in a linear system of matrix-valued equations, where the unknowns are matrices with k^2 entries (k << n). The desired H2-matrix approximation is then obtained by solving this system, e.g., by using iterative methods. Since H2-matrices are given in a special hierarchical format, the design of efficient algorithms is a crucial point. These algorithms particularly include those for setting up, assembling, as well as solving the derived system of equations. Under plausible assumptions this thesis shows that all used algorithms exhibit a computational effort in O(k^a n), which is the typical complexity in the sense of H2-matrices. Subsequent to the definition of the new solution technique and the analysis of all required algorithms, numerical examples illustrate the behavior of this novel approach.
 
Schlagworte:Hierarchische Matrizen, H2-Matrizen, Lokale Niedrigrangapproximation, Matrixgleichungen, Partielle Differentialgleichungen, Vorkonditionierer, Galerkin-Verfahren, Numerische lineare Algebra
hierarchical matrices, H2-matrices, local low-rank approximations, matrix equations, partial differential equations, preconditioner, Galerkin method, numerical linear algebra
 
Dokumente: