Content deleted Content added
HerrHartmuth (talk | contribs) m added the abbreviation: ILU |
HerrHartmuth (talk | contribs) →Definition: included the mathematical definition |
||
Line 11:
== Definition ==
For a given matrix <math> A \in \R^{n \times n} </math> one defines the graph <math> G(A) </math> as
:<math>
G(A) := \left\lbrace (i,j) \in \N^2 : A_{ij} \neq 0 \right\rbrace \,,
</math>
which is used to define the conditions a ''sparsity patterns'' <math> S </math> needs to fulfill
:<math>
S \subset \left\lbrace 1, \dots , n \right\rbrace^2
\,, \quad
\left\lbrace (i,i) : 1 \leq i \leq n \right\rbrace \subset S
\,, \quad
G(A) \subset S
\,.
</math>
A decomposition of the form <math> A = LU - R </math> where the following hold
* <math> L \in \R^{n \times n} </math> is a [[Triangular_matrix#Unitriangular_matrix|lower unitriangular]] matrix
* <math> U \in \R^{n \times n} </math> is an [[Triangular_matrix|upper triangular]] matrix
* <math> L,U </math> are zero outside of the sparsity pattern: <math> L_{ij}=U_{ij}=0 \quad \forall \; (i,j) \notin S </math>
* <math> R \in \R^{n \times n} </math> is zero within the sparsity pattern: <math> R_{ij}=0 \quad \forall \; (i,j) \in S </math>
is called an '''incomplete LU decomposition''' (w.r.t. the sparsity pattern <math> S </math>).
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).
| |||