What is the difference between ILU(0) and ILU(1)?

Question

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)?

Answer 1

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.