Scientific Computing

H²-Matrix-Arithmetik

Beteiligte: Steffen Börm, Knut Reimer, Nadine Albrecht

Gefördert durch die Deutsche Forschungsgemeinschaft, Projekt BO 3289/4-1 "H²-Matrix-Vorkonditionierer für Integral- und elliptische Differentialgleichungen"

Bei der Behandlung von Integralgleichungen und elliptischen Differentialgleichungen treten explizit oder implizit Matrizen auf, die vollbesetzt sind, bei denen also fast alle Koeffizienten ungleich null sind. Eine derartige Matrix mit n Zeilen und Spalten als konventionelles zweidimensionales Array abzuspeichern würde zu einem Speicherbedarf von O(n²) führen und wäre deshalb für große Dimensionen viel zu aufwendig. H²-Matrizen ermöglichen es, diese Matrizen mit einem Speicherbedarf von O(n k) zu approximieren, wobei k ein Parameter ist, mit dem sich die Genauigkeit der Approximation steuern lässt.

Im Rahmen dieses Forschungsvorhabens untersuchen wir, welche algebraischen Operationen sich mit H²-Matrizen effizient durchführen lassen. Beispielsweise lässt sich relativ einfach ein Algorithmus entwickeln, der die Multiplikation einer H²-Matrix mit einem Vektor in O(n k) Operationen ausführt. Wesentlich aufwendiger ist die Multiplikation zweier H²-Matrizen. Falls die Struktur des Ergebnisses vorgegeben ist, lässt sich diese Aufgabe in O(n k²) Operationen lösen. In der Praxis, insbesondere bei der Konstruktion von Lösungsverfahren für große lineare Gleichungssysteme, ist die Struktur unbekannt und muss während der Berechnung gefunden werden. Unser Ziel ist es, eine Matrix-Multiplikation zu entwickeln, die in O(n k² log n) Operationen Struktur und Ergebnis berechnet und so gestaltet ist, dass sie sich verwenden lässt, um kompliziertere Operationen wie die Berechnung der Inversen oder der LR-Faktorisierung einer H²-Matrix ebenfalls in nur O(n k² log n) auszuführen.