Hierarchische Matrizen

von Wolfgang Hackbusch 

Teil III

zurück zum vorhergehenden Teil

Hierarchische Matrizen

Zwei Ziele sind gleichzeitig zu erreichen: A ist durch tex2html_wrap_inline397 aus einer Menge tex2html_wrap_inline399 hinreichend genau zu approximieren (d.h. tex2html_wrap_inline401) und gleichzeitig sollen Matrizen aus tex2html_wrap_inline399 die oben genannten Eigenschaften haben. Im allgemeinen kann für die genannte Klasse von Matrizen eine solche Menge konstruiert werden. Da aber insbesondere die Frage interessiert, wie eine Arithmetik mit fast linearer Komplexität möglich ist, wird hier eine Modellmenge tex2html_wrap_inline405 von tex2html_wrap_inline407-Matrizen (hierarchischen Matrizen) vorgestellt, die allerdings zu einfach gebaut ist, um auch tex2html_wrap_inline401 zu gewährleisten.

Die Matrixdimension sei die Zweierpotenz tex2html_wrap_inline411 (tex2html_wrap_inline413). Für p=0 stimmen die tex2html_wrap_inline417-Matrizen mit den üblichen Zahlen überein und sollen per definitionem tex2html_wrap_inline407-Matrizen sein. Die allgemeine Definition ist rekursiv. Eine tex2html_wrap_inline417-Matrix A läßt sich in der Blockform

tex2html_wrap_inline425 schreiben, wobei tex2html_wrap_inline427 vom Format tex2html_wrap_inline429 sind. Wir nennen A eine tex2html_wrap_inline407-Matrix, falls tex2html_wrap_inline435 und tex2html_wrap_inline437 jeweils tex2html_wrap_inline407-Matrizen sind und tex2html_wrap_inline441 als Rank-k-Matrizen (mit kleinem k) dargestellt sind. Im weiteren beschreiben wir den Fall k=1, in dem tex2html_wrap_inline449 und tex2html_wrap_inline451 Produkte von Spaltenvektoren a,c und Zeilenvektoren b,d der Länge tex2html_wrap_inline457 sind.

Die rekursive Konstruktion ist in den folgenden Darstellungen von tex2html_wrap_inline407-Matrizen der Dimension n=1,2,4,8 abzulesen:

H-Matrix

Beispielhaft für die Aufwandsbestimmung sei der notwendige Speicherplatz diskutiert. Sei N(p) die Zahl der Daten zu tex2html_wrap_inline465 Für p=0 gilt N(0)=1. Die rekursive Konstruktion führt auf die rekursive Gleichung tex2html_wrap_inline471 (für die zwei tex2html_wrap_inline407-Matrizen der Stufe p-1 und die vier Vektoren der Länge tex2html_wrap_inline477). Die Lösung der Rekursion tex2html_wrap_inline479 lautet tex2html_wrap_inline481 und zeigt die fast lineare Komplexität.

Ebenso ist der Aufwand der Matrix-Vektor-Multiplikation tex2html_wrap_inline483 Die Addition A+B ist approximativ möglich zum Aufwand tex2html_wrap_inline483 Die approximative Multiplikation tex2html_wrap_inline375 kostet ebenso wie die approximative Invertierung tex2html_wrap_inline491

Ausblick

Die Arithmetik der tex2html_wrap_inline407-Matrizen erlaubt beispielsweise die automatische Berechnung von Vorkonditionierungsmatrizen und kann so zur Konstruktion schneller Iterationsverfahren dienen. Interessanter sind aber Anwendung, bei denen matrix-wertige Lösungen zu bestimmen sind. Hier eröffnet die tex2html_wrap_inline407-Matrixtechnik neue Möglichkeiten. Beispiele für Aufgaben mit matrix-wertigen Lösungen sind a) die Berechnung der Exponentialfunktion tex2html_wrap_inline497 oder b) die Lösung der Silvester-Gleichung AX+XB=C (A,B,C gegeben, X gesucht).

Inhalt

  • Teil 1
    • Aktueller Forschungsschwerpunkt Wissenschaftliches Rechnen
    • Großskalige Aufgaben
    • Lineare Komplexität
  • Teil 2
    • Vollbesetzte Gleichungssysteme
    • Approximation vollbesetzter Matrizen
  • Teil 3
    • Hierarchische Matrizen
    • Ausblick

Kontakt

Prof. Dr. Wolfgang Hackbusch
Max-Planck Institut für Mathematik in den Naturwissenschaften
Inselstrasse 22
04103 Leipzig
Email

09.03.2017, 13:19