Hierarchische Matrizen

von Wolfgang Hackbusch

Teil II

zurück zum vorhergehenden Teil

Vollbesetzte Gleichungssysteme

Im Falle eines n-dimensionalen Gleichungssystems Ax=b, d.h. tex2html_wrap_inline305 für tex2html_wrap_inline307 haben die Vektoren x,b je n Komponenten, während die Matrix A im Prinzip durch tex2html_wrap_inline315 Daten beschrieben wird. Glücklicherweise liefern die üblichen Diskretisierungsverfahren partieller Differentialgleichungen sogenannte schwachbesetzte Matrizen A, d.h. die meisten Matrixeinträge sind Nullen und die Zahl der Nichtnullelemente ist proportional zu n. Insbesondere ist dann die Matrix-Vektor-Multiplikation tex2html_wrap_inline321 von linearer Komplexität, die Grundlage verschiedenster Iterationsverfahren ist.

Anders stellt sich die Situation bei vollbesetzten Matrizen dar. Da die Lösung x von Ax=b von den tex2html_wrap_inline315 Matrixeinträgen abhängt, kann eine exakte Auflösung keinen geringeren Rechenaufwand als tex2html_wrap_inline329 benötigen, wobei für den allgemeinen Fall nicht einmal ein Lösungsalgorithmus mit quadratischer Komplexität bekannt ist.

Vollbesetzte Matrizen treten unter anderem bei der Diskretisierung von Integralgleichungen auf, die in speziellen Fällen eine äquivalente Umformulierung partieller Differentialgleichungen darstellen (während die Differentialgleichung über einen möglicherweise unbeschränkten dreidimensionalen Bereich erstreckt, bezieht sich die Integralgleichung nur auf die Oberfläche dieses Bereiches). Die unter dem Namen Randelementmethode (englische Abkürzung: BEM) bekannte Diskretisierungsmethode kann nur konkurrenzfähig sein, wenn der Aufwand tex2html_wrap_inline329 auf lineare Komplexität tex2html_wrap_inline279 reduziert wird.

Auch wenn die Matrix A schwachbesetzt ist, entsteht eine vollbesetzte Matrix, wenn man zur Inverse von A (oder einer Hauptuntermatrix von A wie bei Schur-Komplementen) übergeht. Diese Tatsache hat dazu geführt, daß man bei der Gestaltung von Algorithmen die Invertierung strikt umgeht und im wesentlichen nur die Matrix-Vektor-Multiplikation einsetzt.

Approximation vollbesetzter Matrizen

Die gewünschte lineare Komplexität tex2html_wrap_inline279 ist so nicht erreichbar, da wie ausgeführt tex2html_wrap_inline329 nicht unterschritten werden kann. Dies bezieht sich aber auf die Bestimmung der exakten Lösung. Da das Gleichungssystem Ax=b kein Selbstzweck ist, sondern x nur die Approximation einer anderen Lösung darstellt, ist es akzeptabel, A durch eine benachbarte Matrix tex2html_wrap_inline351 zu ersetzen. Damit stellt sich die Frage, ob man in hinreichender Nähe von A ein tex2html_wrap_inline351 findet, so daß sich tex2html_wrap_inline357 genügend genau lösen läßt (d.h. tex2html_wrap_inline359 für gegebenes tex2html_wrap_inline361 und nur linearen Rechenaufwand erfordert.

Im folgenden wird eine neue Lösungsmethode skizziert, die nicht nur die Gleichungslösung betrifft, sondern die gesamte Matrix-Arithmetik in fast linearer Komplexität ermöglicht. Mit ``fast linear'' ist gemeint, daß tex2html_wrap_inline363 für ein tex2html_wrap_inline365 was in der Praxis der linearen Komplexität gleichkommt. Zu der Matrix-Arithmetik gehört die Matrix-Vektor-Multiplikation Ax (üblicher Rechenaufwand tex2html_wrap_inline329), die Addition A +B (üblich: tex2html_wrap_inline329), die Multiplikation tex2html_wrap_inline375 (üblich: tex2html_wrap_inline283) und die Invertierung tex2html_wrap_inline379 (üblich: tex2html_wrap_inline283). Ferner muß die Ersatzmatrix mit fast linearem Speicheraufwand repräsentierbar sein (üblich: tex2html_wrap_inline315).

Der Anwendungsbereich der nachfolgenden Methode sind vollbesetzte Matrizen, die zu geeigneten Integraloperatoren oder Inversen von Differentialoperatoren gehören. Ein Beispiel eines typischen Integraloperators ist tex2html_wrap_inline385 mit dem Coulomb-Kern tex2html_wrap_inline387 wobei der Integrationsbereich tex2html_wrap_inline389 beispielsweise die Oberfläche eines 3D-Gebietes ist. Da k(x,y) bei x=y singulär ist, ist bei der Matrixapproximation in der Diagonalnähe vorsichtiger anzunähern als weit entfernt von der Diagonalen.

weiter mit dem nächsten Teil

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

11.02.2013, 16:02