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.