Incomplete LU factorization: Difference between revisions

Revision as of 10:46, 14 March 2018

Revision as of 11:01, 14 March 2018

Line 33:

The sparsity pattern of ''L'' and ''U'' is often chosen to be the same as the sparsity pattern of the original matrix ''A''. If the underlying matrix structure can be referenced by pointers instead of copied, the only extra memory required is for the entries of ''L'' and ''U''. This preconditioner is called ILU(0).

== Stability ==

Concerning the stability of the ILU the following theorem was proven by Meijerink an van der Vorst<ref>{{Cite journal|last=Meijerink|first=J. A.|last2=Vorst|first2=Van Der|last3=A|first3=H.|date=1977|title=An iterative solution method for linear systems of which the coefficient matrix is a symmetric 𝑀-matrix|url=http://www.ams.org/home/page/|journal=Mathematics of Computation|language=en-US|volume=31|issue=137|pages=148–162|doi=10.1090/S0025-5718-1977-0438681-4|issn=0025-5718}}</ref>.

Let <math> A </math> be an [[M-matrix]], the (complete) LU decomposition given by <math> A=\hat{L} \hat{U} </math>, and the ILU by <math> A=LU-R </math>.

Then

:<math>

|L_{ij}| \leq |\hat{L}_{ij}|

\quad \forall \; i,j

</math>

holds.

Thus, the ILU is at least as stable as the (complete) LU decomposition.

== Generalizations ==