von Wolfgang Hackbusch

Teil II

zurück zum vorhergehenden Teil

Vollbesetzte Gleichungssysteme

Im Falle eines n-dimensionalen Gleichungssystems Ax=b, d.h. für haben die Vektoren x,b je n Komponenten, während die Matrix A im Prinzip durch 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 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 Matrixeinträgen abhängt, kann eine exakte Auflösung keinen geringeren Rechenaufwand als 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 auf lineare Komplexität 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 ist so nicht erreichbar, da wie ausgeführt 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 zu ersetzen. Damit stellt sich die Frage, ob man in hinreichender Nähe von A ein findet, so daß sich genügend genau lösen läßt (d.h. für gegebenes 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ß für ein was in der Praxis der linearen Komplexität gleichkommt. Zu der Matrix-Arithmetik gehört die Matrix-Vektor-Multiplikation Ax (üblicher Rechenaufwand ), die Addition A +B (üblich: ), die Multiplikation (üblich: ) und die Invertierung (üblich: ). Ferner muß die Ersatzmatrix mit fast linearem Speicheraufwand repräsentierbar sein (üblich: ).

Der Anwendungsbereich der nachfolgenden Methode sind vollbesetzte Matrizen, die zu geeigneten Integraloperatoren oder Inversen von Differentialoperatoren gehören. Ein Beispiel eines typischen Integraloperators ist mit dem Coulomb-Kern wobei der Integrationsbereich 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