I know that ILU (0) has the same sparsity pattern as that of the original matrix A, and while performing the Gaussian elimination all the fillins are ignored. But I am not clear how ILU(1) or ILU(2) and so on work. What is the difference between ILU(0) and ILU(1), and how the sparsity pattern is chosen in ILU(1)?
$\endgroup$ 41 Answer
$\begingroup$I think the best way to explain the ILU decomposition is with pictures. Let $A$ be the band matrix from the 5-point-star of the Finite Difference method \begin{align*} A&=\begin{pmatrix} B_m & -I_m & \\ -I_m & B_m & -I_m \\ & -I_m & B_m & -I_m \\ & & \ddots & \ddots & \ddots \\ &&& -I_m & B_m & -I_m \\ & &&& -I_m & B_m \\ \end{pmatrix}∈ℝ^{n×n}, \\ B_m&=\begin{pmatrix} 4 & -1 & \\ -1 & 4 & -1 \\ & -1 & 4 & -1 \\ & & \ddots & \ddots & \ddots \\ &&& -1 & 4 & -1 \\ & &&& -1 & 4 \\ \end{pmatrix}∈ℝ^{m×m}. \end{align*}
The structure of that matrix looks like this (for $m=5$):
The $LU$-Decomposition given by $A=LU$, has the typical fill-in
The ILU($0$) factorisation takes the sparsity pattern of $A$. Hence, if $A_{ij}=0$, the entries $L_{ij}$ and $U_{ij}$ are set to $0$.
The ILU($0$) matrices look like:
With these two matrices the ILU($0$) factorisations reads: $$A\approx A_0 = L_0U_0.$$ And the sparsity pattern of the matrix $A_0$ is
You can see some additional entries, compared to the sparsity pattern of $A$. These exist simply, because we set the fill-in of the original $LU$-Decomposition to $0$.
The ILU($1$) factorisation now takes the sparsity pattern of the ILU($0$) matrix $A_0$. Therefore if $[A_0]_{ij}=0$, the entries $L_{ij}$ and $U_{ij}$ are set to $0$.
With these two matrices the ILU($1$) factorisations reads: $$A\approx A_1 = L_1U_1.$$
And the ILU($2$) decomposition would again take the sparsity pattern of $A_1$.
I recommend Yousef Saad's book Iterative Methods for Sparse Linear Systems. It is the best book for that kind of stuff.
$\endgroup$
