ILU-Zerlegung

Als ILU-Zerlegung (von incomplete LU-Decomposition) oder unvollständige LU-Zerlegung bezeichnet man in der numerischen Mathematik die fehlerbehaftete Zerlegung einer Matrix in das Produkt einer unteren Dreiecksmatrix L und einer oberen Dreiecksmatrix U

,

bei der von den Zerlegungsmatrizen L und U nur die Einträge einer vorgegebenen Besetzungsstruktur berechnet werden.

Die ILU-Zerlegung wird erfolgreich als Vorkonditionierer zur Beschleunigung der iterativen Lösung großer dünnbesetzter linearer Gleichungssysteme Ax = b mittels Krylow-Unterraum-Verfahren eingesetzt. Es werden dabei keine Eigenschaften des eigentlichen Problems (meist die numerische Lösung einer partiellen Differentialgleichung) ausgenutzt. Damit ist sie nicht auf bestimmte Problemklassen beschränkt und hat Einzug in viele Bereiche der numerischen Simulation gefunden, beispielsweise in der numerischen Strömungsmechanik ist die Technik weit verbreitet.

Zuerst erwähnt wurde das Verfahren 1960 von Varga und Buleev. Eine genauere Analyse wurde 1977 von Meijerink und van der Vorst veröffentlicht. Diese untersuchten Vorkonditionierungstechniken für das CG-Verfahren und schlugen eine unvollständige Cholesky-Zerlegung für symmetrische Matrizen vor. Gleichzeitig erwähnten sie eine Erweiterung auf allgemeine Matrizen.

Bei der Berechnung einer normalen LU-Zerlegung einer dünnbesetzten Matrix kann man die Besetzungsstruktur in der Regel nicht ausnutzen. Es wird daher sehr viel mehr Speicherplatz benötigt als für die ursprüngliche Matrix und auch die Anzahl der notwendigen Rechenoperationen ist nicht geringer als die für eine vollbesetzte Matrix. Durch die Vorgabe einer maximalen Besetzungsstruktur wird dieses Problem unter Inkaufnahme einer fehlerbehafteten Zerlegung umgangen.

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