5.3.1 Unvollständige LU- und tridiagonale Faktorisierung



next up previous contents
Next: 5.3.2 Mehrfarbenordnungen und das Up: 5.3 Vorkonditionierung Previous: 5.3 Vorkonditionierung

5.3.1 Unvollständige LU- und tridiagonale Faktorisierung

 

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üllgradgif 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-Typgif 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.



next up previous contents
Next: 5.3.2 Mehrfarbenordnungen und das Up: 5.3 Vorkonditionierung Previous: 5.3 Vorkonditionierung



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