Die unvollständige Faktorisierung der Koeffizientenmatrix
( und sind die strikt unteren (lower) und oberen (upper) Teil-Dreiecksmatrizen von und ist die Hauptdiagonale) läßt sich als Matrizenprodukt
anschreiben. Die Diagonalmatrix ergibt sich aus der Forderung
Wird das Spärlichkeitsmuster
der Dreiecksmatrizen und vergrößert,
etwa durch zusätzliche Diagonalen entlang der
bereits vorhandenen, so erhält man modifizierte ILU-Faktorisierungen,
die nach ihrem Füllgrad
als ILU() bezeichnet werden [24][63].
= notiert keine zusätzliche Füllung außerhalb des
Original-Spärlichkeitsmusters der Koeffizientenmatrix .
= bedeutet Addition von
je einer Diagonale an die existierenden Diagonalen,
und zwar von der Hauptdiagonale diametral nach außen gerichtet.
Die höheren Füllgrade sind sinngemäße Fortsetzungen
dieses Schemas. Mit steigendem approximieren die unvollständigen
Faktoren und immer besser die
exakten LU-Faktoren von , und
die vorkonditionierte Matrix
nähert sich immer mehr der Einheitsmatrix.
Im dreidimensionalen Fall haben Simulationen mit dem
Code NSPCG [75] gezeigt, daß für Werte von
der Aufwand für die unvollständige Faktorisierung
stark ansteigt, sodaß der
iterative Lösungsprozeß durch die unvollständige
Faktorisierung dominiert wird. Diese Faktorisierungen
bringen dann keine Rechenzeitersparnis.
Die Berechnung der vorkonditionierten Matrix erfordert
die sukzessive Inversion der Dreiecksmatrizen und
und Multiplikation mit der Koeffizientenmatrix A.
Im Fall von = wird diese Berechnungssequenz optimal
unter Ausnützung des Tricks von Stanley Eisenstat
durchgeführt [21].
Folgende Varianten wurden untersucht: Symmetrische
Vorkonditionierung
und linksseitige Vorkonditionierung
Nach anfänglich symmetrischer Skalierung der Matrix durch
findet man für den symmetrischen Vorkonditionierungsschritt die beiden Formeln
und für linksseitige Vorkonditionierung nach linksseitiger Skalierung die Formel
Symmetrische Vorkonditionierung benötigt zur ihrer
Durchführung zwei zusätzliche Vektoren und einen
Vektor zur Rückskalierung des Lösungsvektors
mit . Hingegen erfordert
linksseitige Vorkonditionierung keinen zusätzlichen
Speicherplatz, jedoch eine Rücksubstitution
in einem triangularen Faktor mehr. Wegen der hohen
Iterationszahlen, die bei der iterativen Lösung der
Kontinuitätsgleichungen auftreten, ist die erste Variante
zu bevorzugen.
Zu bemerken ist ferner, daß linksseitige,
rechtsseitige und symmetrische Vorkonditionierung
verschiedene vorkonditionierte Matrizen mit
identischem Spektrum ergeben. Aufgrund von Rundungsfehlern
ist die Iterationsgeschichte der drei Vorkonditionierungsvarianten
allerdings nicht gleich.
Ein Vorkonditionierungs-Verfahren vom
ADI-Typ
erhält man durch unvollständige Faktorisierung der Matrix in
drei tridiagonale Faktoren [18]
wobei die Hauptdiagonale von ist und die tridiagonalen Matrizen , und durch die Gleichung
gegeben sind. Es ist einfach zu sehen, daß die Bedingung
erfüllt ist, weswegen der Faktorisierungsschritt entfällt. Verglichen mit ILU() enthält die Fehlermatrix mehr Einträge als . Die Konvergenz einer TF-vorkonditionierten Iteration ist deswegen schlechter als die korrespondierende ILU-Iteration. Richtwerte sind Faktoren von bis . Hinzu kommt weiters, daß zur Durchführung des TF-Vorkonditionierungsschrittes drei Matrizeninversionen erforderlich sind. Allerdings ist die Zahl unabhängiger Operationen bei diesen Inversionen groß. Die Matrizen bestehen korrespondierend zu einzelnen Gitterlinien im Simulationswürfel aus vielen entkoppelten tridiagonalen Systemen, zu deren effizienter Lösung optimierte Routinen auf Vektorcomputern zur Verfügung stehen. Ein gewisses Problem ist allerdings die Lage der Unbekannten im Speicher. Bei einer lexikographischen Ordnung der Unbekannten im Speicher in der Reihenfolge der x-, y- und z-Achse ist das Adreßinkrement (,,Stride``) zur nächsten unabhängigen Variable bei (z-Richtung) eins, bei (x-Richtung) gleich NX (Anzahl der Gitterlinien in x-Richtung). Bei (y-Richtung) variiert das Stride von Ebene zu Ebene. Solche nichtkonstanten Strides führen leicht zu Speicherkonflikten, die die Leistungsfähigkeit eines Vektorcomputers stark beeinträchtigen können. Nichtsdestotrotz berichten Doi und Harada [18] sehr günstige Resultate auf dem NEC-SX2-Supercomputer.