5.5 Unvollständige Zerlegungen

Schon seit Jahrzehnten wird zum Lösen von (5.1) die Matrix $K$ in eine obere Dreiecksmatrix  $\widetilde{U} \makebox[0pt]{}$ und eine untere Dreiecksmatrix  $\widetilde{L} \makebox[0pt]{}$ zerlegt. Während die Auflösung der resultierenden, gestaffelten Gleichungssysteme mit diesen Dreiecksmatrizen sehr schnell ausführbar ist, explodiert die Rechenzeit für die Faktorisierung

$$K \;\;=\;\; \widetilde{L} \makebox[0pt]{} \cdot \widetilde{U} \makebox[0pt]{} \enspace,$$ (5.4)

da sich die Anzahl der arithmetischen Operationen wie ${\mathcal O}(N^3)$ verhält. Bei der Faktorisierung dünnbesetzter Matrizen tritt ein Fill-In auf, welches bei einem sehr ausgedünnten Besetztheitsmuster der Matrix (FEM, FDM,  ...) zu einem gravierenden Mehraufwand an Speicher zur Abspeicherung der zerlegten Matrix führt.

Aus diesen Gründen wird versucht, die Matrix $K$ in die Dreiecksmatrizen $L$ und $U$ mit dem gleichen Besetztheitsmuster zu zerlegen. Die Gleichung (5.4) gilt dadurch nicht mehr, zur exakten Beschreibung muß noch eine Restmatrix $P$ in Betracht gezogen werden :

$$K\;\;=\;\; L \cdot U \,-\, P \enspace.$$ (5.5)

Die entstandene Faktorisierung $L \cdot U$ bzw. $U \cdot L$ kann in der einfachen Iteration zur Approximation des Defektes genutzt werden (auch anstelle von $D^{-1}$ in der Jacobi-Iteration).

Es gibt spezielle Faktorisierungen für symmetrische, positiv definite Matrizen (ICC= Incomplete Cholesky) und Faktorisierungen, die ein gewisses Fill-In zulassen (ILU(m)). Auch Lumpingtechniken, d.h. wegzulassende Einträge werden auf die Hauptdiagonale addiert, sind in Verwendung (MAF).

Im folgenden betrachten wir die unvollständige Faktorisierung (5.5) für nichtsymmetrische Matrizen $K$ ohne Fill-In, d.h. die klassische ILU(0) Faktorisierung und den entsprechenden Auflösungsschritt $L\cdot U \cdot \underline{w} = \underline{r}\enspace$.