ILU-Zerlegung

Anwendung

Für die Anwendung als Vorkonditionierer wird das Gleichungssystem Ax = b formal mit (LU)^-1 multipliziert,

(LU)^-1 Ax = (LU)^-1 b

Wendet man darauf Krylow-Unterraum-Verfahren an, so konvergieren diese besser, da die Matrix (LU)^-1 A näher an der Einheitsmatrix als A ist. Für diese Verfahren benötigt man in jedem Schritt Matrix-Vektor-Multiplikationen. Da A schwach besetzt ist, ist die Berechnung von y = Ax mit geringem Rechenaufwand möglich. Für die Lösung von c = (LU)^-1 y kann man das äquivalente Gleichungssystem

LUc = y

effizient durch Vorwärts-Rückwärts-Einsetzen lösen. Dabei lässt sich die schwache Besetztheit der Matrizen L und U ausnutzen.

Die Berechnung einer ILU-Zerlegung ist, etwa im Vergleich zu Splitting-basierten Vorkonditionierern wie Gauß-Seidel, relativ aufwändig, wobei der Aufwand direkt mit der Größe der erlaubten Besetzungsstruktur zusammenhängt. Aufgewogen wird dies durch die Beschleunigung der Krylow-Unterraum-Verfahren, die in der Regel besser ist, je größer die erlaubte Besetzungsstruktur. Werden direkt hintereinander mehrere Systeme mit derselben Matrix, aber verschiedenen rechten Seiten gelöst, empfiehlt es sich somit, mehr in die Berechnung der ILU zu investieren. Bei der numerischen Lösung zeitabhängiger partieller Differentialgleichungen, bei denen häufig Sequenzen tausender ähnlicher linearer Gleichungssysteme nacheinander zu lösen sind, wird eine einmal berechnete ILU-Zerlegung in der Regel eingefroren und periodisch neuberechnet.

ILU-Zerlegungen oder Varianten sind Teil jeder größeren Programmbibliothek zur Lösung dünnbesetzter linearer Gleichungssysteme, etwa von PetSc oder von MATLAB.

Copyright- und Lizenzinformationen: Diese Seite basiert auf dem Artikel ILU-Zerlegung aus der freien Enzyklοpädιe Wιkιpedιa und steht unter der Lizenz Creative Commons CC-BY-SA 3.0 Unported (Kurzfassung). Liste der Autoren

Anbieterkennzeichnung