5.3 Vorkonditionierung

Unter Vorkonditionierung eines linearen Gleichungssystems versteht man im engeren Sinne die Transformation desselbigen derart, daß eine zur Lösung verwendete iterative Methode schneller konvergiert. Vorkonditionierung ist also eine Form der Konvergenzbeschleunigung. Vorkonditionierung kann aber auch die Konvergenz erst herbeiführen. Der Vorkonditionierungsschritt muß während jeder Iteration eines iterativen Gleichungslösers in Form von Matrizenmultiplikationen durchgeführt werden. Die arithmetischen Operationen für die Vorkonditionierung dominieren in der Regel im gesamten iterativen Lösungsprozeß. In dieser Arbeit wurden mehrere Vorkonditionierungsmethoden untersucht:

: Punkt- und Block-Jacobi-Verfahren.
: Unvollständige LU-Faktorisierungen (ILU()).
: Tridiagonale Faktorisierung (TF).
: Unvollständige LU-Faktorisierungen mit Umordnung zur Entkopplung der Unbekannten.
: Reduziertes System (RS).
: Optimale Polynome (LS).

Die verschiedenen Vorkonditionierungs-Verfahren haben unterschiedliche Einsatzbereiche, die von der Computerarchitektur mitbestimmt werden. Namentlich der Einsatz vorkonditionierter Gleichungslöser auf Vektor- und Parallelrechnern hat zur Entwicklung neuer (Multicolor-ILU) oder zur Wiederentdeckung existierender Verfahren (LS) geführt. Die Reihenfolge der in der Liste angeführten Methoden entspricht etwa der Chronologie der Untersuchung im Rahmen dieser Arbeit. In analoger Weise ist dieser Abschnitt aufgebaut.
Der Beginn der Entwicklung iterativer Verfahren für den dreidimensionalen Programmteil von MINIMOS war geprägt von der Übertragung effektiver linearer Gleichungslöser vom zweidimensionalen Problem auf das dreidimensionale. Für die Poisson- und die Kontinuitätsgleichungen wurde ein Block-CJCG-Verfahren bzw. ein Block-CJ-BiCG-Verfahren nach dem Muster der Methode von Reid [88] entwickelt. Als Vorkonditionierung dient dabei eine tridiagonale Matrix, deren Invertierung direkt erfolgt [106]. Während die Poissongleichung mit dem Block-CJCG-Verfahren schnell gelöst werden konnte, was zu einer anfänglich spektakulären Beschleunigung der Modellstufe 1 des dreidimensionalen Programmteils von MINIMOS um den Faktor

führte, erwies sich das CJ-BiCG-Verfahren für die beiden Kontinuitätsgleichungen als wenig robust. Namentlich beim Auftritt signifikanter Stoßionisationsraten kam es zu Konvergenzstagnationen oder chaotischem Verhalten. Die tridiagonale (Block-Jacobi) Vorkonditionierung im CJ-BiCG-Verfahren kann wahlweise in den drei Raumrichtungen (x-, y- oder z-Richtung) des Simulationswürfels erfolgen, was zu sehr unterschiedlichen Konvergenzraten führt. Eine räumliche Vorzugsrichtung konnte nicht festgestellt werden [106].
Die robusteste und schnellste Vorkonditionierung basiert auf unvollständiger LU-Faktorisierung der Koeffizientenmatrix. Varianten, in denen ein diagonales Spärlichkeitsmuster in den LU-Faktoren vorgegeben wird, ILU(

), wurden untersucht. Alternative unvollständige Faktorisierungen beruhen auf tridiagonalen Systemen [18] (Abschnitt 5.3.1).
Die unvollständige Faktorisierung führt auf Rekursionen höherer Ordnung und eignet sich nicht direkt zur Implementation auf einer parallelen Rechnerarchitektur bzw. auf Vektorrechnern. Parallelisierung der Vorkonditionierung kann durch Entkopplung der Iteration mittels Umsortierung der Variablen erreicht werden (Abschnitt 5.3.2).
Schließlich wurden noch polynomiale Iterationen untersucht, deren Vorteil in der Beschränkung auf lokale Interprozessor-Kommunikation besteht und deren Anwendungsbereich parallele Computersysteme mit lokalem Speicher sind (Abschnitt 5.3.3).

Next: 5.3.1 Unvollständige LU- und Up: 5 Lineare Gleichungssysteme in Previous: 5.2.4 BiCGCGS und

Martin Stiftinger
Fri Oct 14 21:33:54 MET 1994