5.5 Incomplete factorizations

If direct solvers are used for solving (5.1), matrix $K$ will be factored into an upper  $\widetilde{U} \makebox[0pt]{}$ and and lower triangular matrix  $\widetilde{L} \makebox[0pt]{}$. The solving of the resulting graduated system of equations with the triangular matrices is fast but the time for the factorization

$$K \;\;=:\;\; \widetilde{L} \makebox[0pt]{} \cdot \widetilde{U} \makebox[0pt]{} \enspace,$$ (5.4)

behaves like ${\mathcal O}(N^3)$. If the matrix is sparse (FEM, FDM,  ...) then the fill-in in the factorization blows up the memory requirements for storing the factored matrix dramatically.

Therefore, one tries to factor matrix $K$ into triangular matrices $L$ and $U$ with the same matrix pattern as $K$. Equation (5.4) has to be modified by taking the rest matrix $P$ into account.

$$K\;\;=:\;\; L \cdot U - P \enspace.$$ (5.5)

The factorization $L \cdot U$ or $U \cdot L$, respectively, can be used in a simple iteration for approximating the defect (e.g., replace $D^{-1}$ in the Jacobi iteration).

There exist special modifications for symmetric and positive definite matrices (ICC= Incomplete Cholesky) and for factorizations allowing a certain fill-in in the pattern of the triangular matrices (ILU(m)). They are often used in combination with lumping techniques, i.e., entries not fitting in the admissible pattern are added to the main diagonal (e.g., MAF).

We investigate in the following the incomplete factorizations (5.5) for non-symmetric matrices $K$ without fill-in, i.e. the classical ILU(0) factorization, and the appropriate elimination step $L\cdot U \cdot \underline{w} = \underline{r}\enspace$.