von Wolfgang Hackbusch 

Teil III

zurück zum vorhergehenden Teil

Hierarchische Matrizen

Zwei Ziele sind gleichzeitig zu erreichen: A ist durch aus einer Menge hinreichend genau zu approximieren (d.h. ) und gleichzeitig sollen Matrizen aus 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 von -Matrizen (hierarchischen Matrizen) vorgestellt, die allerdings zu einfach gebaut ist, um auch zu gewährleisten.

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

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

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

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

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

Ausblick

Die Arithmetik der -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 -Matrixtechnik neue Möglichkeiten. Beispiele für Aufgaben mit matrix-wertigen Lösungen sind a) die Berechnung der Exponentialfunktion oder b) die Lösung der Silvester-Gleichung AX+XB=C (A,B,C gegeben, X gesucht).