Analyse der H-Matrix Invertierung

Datenschwache Matrixformate sind ein zentrales Werkzeug für die numerische Lösung von partiellen Differentialgleichungen. Insbesondere Diskretisierungen von Integralgleichungen wie sie bei der Randelementmethode auftreten, sind heute allein aufgrund der Möglichkeiten, die datenschwachen matrixformate bieten, kompetitiv. Nur diese erlauben es, die quadratrische Komplexität (in der Problemgrösse) auf fast lineare zu drücken. Die schnelle Multipolmethode ist das vielleicht bekannteste Beispiel eines solches Verfahrens, denn es zählt zu den Top-10 Algorithmen des 20. Jahrhunderts. Während die Forschung sich in der Anfangphase mit dem Entwickeln von Datenformaten und Algorithmen für die schnelle Matrix-Vektor-Multiplikation beschäftigt hat, ist ein aktueller Forschungsschwerpunkt auf der Realisierung komplexerer Matrixfunktionen wie z.B. der Inversen oder Faktorisierungen. Diese Inversen sind nicht exakt, können aber z.B. für Vorkonditionierungszwecke eingesetzt werden bei schweren Problemklassen, bei denen die etablierten Vorkonditionierer nicht greifen. Das Projekt zielt auf die Analyse der Matrixinvertierung (und den verwandten Problemen von Matrixfaktorisierungen) beim datenschwachen Matrixformat der H-Matrizen. Diese wurden 1999 von W. Hackbusch eingeführt. H-Matrizen sind blockweise Niedrigrangmatrizen, wobei die Blöcke in einer Baustruktur organisiert sind, um eine schnelle Arithmetik zu ermöglichen. Die geeignete Blockstruktur ist natürlich problemabhängig. Eine Grundfrage im Kontext des H- Matrix-Arithmetik ist deshalb, die Blockstrukturen ausfindig zu machen, die die Inverse mit hoher Genauigkeit darstellen können. Wir betrachten Matrizen die bei der Diskretisierung von partiellen Differentialgleichungen entstehen. Für Standard-Blockstrukturen structuren und skalare elliptischte Gleichungen zweiter Ordnung ist bereits bekannt, dass die Inverse gut dargestellt werden kann. In dem Projekt wird dies in mehrer Hinsicht erweitert: Wir betrachten elliptische Systeme wie die Gleichungen der (linearen) Elastizität, die Stokesgleichungen der Strömungsmechanik und die Maxwellgleichungen aus der Elektrodynamik. Zudem betrachten wir gekoppelte Mehrfeldprobleme. Das gemeinsame Merkmal dieser Gleichungen ist ihre Elliptizität, weshalb ähnliche Blockstrukturen verwendet werden können. Wellenausbreitungsphänomene benötigen völlig andere Blockstrukturen. Am Beispiel der Helmholtzgleichung, die in der Akustik auftritt, analysieren wir die Approximierbarkeit der Inversen der Systemmatrix basierend auf anderen, dieser Problemklasse angepassten Blockstrukturen. Die Frage der Approximierbakeit ist nur ein erster Schritt in Richtung Verständnis der H-Matrix-Invertierung. Für eine Klasse von Diskretisierungen, die von symmetrisch positiv definiten Problem herrührt, werden wir eine Fehleranalyse des tatsächlichen Algorithmuses angehen.

Zahlreiche Probleme, die in der mathematischen Physik und im Ingenieurwesen auftreten, werden durch sogenannte nichtlokale Operatoren beschrieben. Ein klassisches Beispiel sind Vielteilchenprobleme mit N Teilchen, wie sie z.B. in der Astrophysik auftreten, wo alle Koerper gravitativ gekoppelt sind. Der Rechenaufwand ist dann quadratisch in N. Der 'fast multipole algorithm' von Rokhlin und Greengard, einer der Top-10-Algorithmen des 20. Jahrhunderts, reduziert diesen Aufwand auf im wesentlichen linearen Aufwand in N. Mathematisch handelt es es um eine datenschwache Darstellung einer N x N Matrix mit lediglich O(N) Daten. W. Hackbusch hat 1999 die Klasse dieser Matrizen zur Klasse der H-Matrizen verallgemeinert, welche blockweise Niedrigrangmatrizen sind, aber zusaetzlich hierarchische Strukturen haben, so dass er sie mit einer Arithmetik (schnelle Addition, Multiplikation, Invertierung) versehen konnte. Die Arithmetik ist notgedrungen approximativ, so dass die mathematische Frage beantwortet werden muss, fuer welche Matrizen ihre Inverse im H-Matrix-Format gut dargestellt werden kann. In dem Projekt konnte gezeigt werden, dass (Galerkin)-Diskretisierungen elliptischer Probleme auf Matrizen fuehren, deren Inverse im H-Matrix-Format sehr gut approximiert werden koennen. Eine Reihe elliptischer Probleme wurde in dem Projekt genauer betrachtet. Ein klassisches Problem sind elliptische partielle Differentialgleichungen (PDGl), die im Ganzraum gestellt sind. Numerisch zerlegt man das Rechengebiet in ein endliches Gebiet, in dem die PDGl diskretisiert wird und ein unendliches Gebiet, in dem die Gleichung mittels einer Randintegralgleichung dargestellt wird. Diese beiden Gleichung werden geeignet gekoppelt. Fuer Diskretisierung des gekoppelten Systems basierend auf quasi-uniformen Gittern kann die Inverse der Systemmatrix sehr gut im H-Marix-Format dargestellt werden kann. Auch fuer die Maxwellgleichungen, die gewisse elektromagnetische Phaenomene beschreiben, konnte die Approximierbarkeit der Inversen gezeigt werden. Fuer skalare elliptische Randwertprobleme wurde die existierende Theorie, die lediglich fuer quasi-uniforme Gitter betrachtet wurde, auf relativ allgemeine Gitter erheblich erweitert. Die Moeglichkeit, allgemeine Gitter zuzulassen ist wesentlich fuer die numerische Behandlung elliptischer Probleme, da sie das Aufloesen lokaler Eigenschaften der gesuchten Loesung oder der vorgegebenen Geometrie ermoeglicht. Eine ganz andere Problemklasse ergibt sich aus der Fragestellung, gegebene Daten moeglichst "glatt" zu interpolieren. Eine wichtige Klasse von Interpolationsfunktionen in diesem Kontext sind radiale Basisfunktionen (RBF). Fuer die beliebte Klasse der 'polyharmonic splines' konnte gezeigt werden, dass die Inverse der Interpolationsmatrix im H-Matrix-Format dargestellt werden kann. Die Inversionsalgorithmen fuer H-Matrizen von Hackbusch sind, wie oben erwaehnt, nur approximativ. Dennoch kann auch eine Approximation der Inversen von grossen Nutzen sein, da sie als Vorkonditionierer zum Beschleunigen eines klassischen iterativen Loesungsprozesses verwendet werden kann.