# Preconditioners based on Incomplete LU Factorization Technique

Usually, preconditioners, or accelerators are used to accelerate an iterative solution process. In some cases, their use can reduce the number of iterations dramatically and thus lead to better solver performance. Although the terms ‘preconditioner’ and ‘accelerator’ are synonyms, hereafter only ‘preconditioner’ is used.

Currently, Intel MKL provides two preconditioners, ILU0 and ILUT, for the sparse matrix presented only in the format accepted in the Intel MKL direct sparse solvers (three-array variation of the CSR storage format, see Sparse Matrix Storage Format section). The used algorithms are described in [Saad03].

The ILU0 preconditioner is based on a well-known factorization of the original matrix into a product of two triangular matrices: low triangular and upper triangular matrices. Usually, such decomposition leads to some fill-in in the resulting matrix structure in comparison with the original matrix. The distinctive feature of the ILU0 preconditioner is that it preserves the structure of the original matrix in the result.

Unlike the ILU0 preconditioner, the ILUT preconditioner preserves some resulting fill-in in the preconditioner matrix structure. The distinctive feature of the ILUT preconditioner is that it saves the resulting entry of the preconditioner if the entry satisfies two conditions simultaneously: the value of the entry is greater than the product of the given tolerance and matrix row norm, and the entry is in the given bandwidth of the resulting preconditioner matrix.

Both ILU0 and ILUT preconditioners can apply to any non-degenerate matrix. They can be used alone or together with the Intel MKL RCI FGMRES solver (see Sparse Solver Routines). Avoid using this preconditioners with MKL RCI CG solver because in general, they produce non-symmetric resulting matrix even if the original matrix is symmetric. Usually, an inverse of the preconditioner is required in this case. To do this the Intel MKL triangular solver routine mkl_dcsrtrsv must be applied twice: for the low triangular part of the preconditioner, and then for its upper triangular part.

### Note

Although ILU0 and ILUT preconditioners apply to any non-degenerate matrix, in some cases the algorithm may fail to ensure successful termination and the required result. The result of the preconditioner routine can be checked only in practice.

A preconditioner may increase the number of iterations for an arbitrary case of the system and the initial guess, and even ruin the convergence. It is user's responsibility to carefully use a suitable preconditioner.

## General Scheme of Using ILUT and RCI FGMRES Routines

The scheme is the same for both preconditioners. Some differences exist in the calling parameters of the preconditioners and in the subsequent call of two triangular solvers. All these differences can be seen in the example codes for both preconditioners in the Preconditioner Code Examples in the Appendix C.

The following pseudocode shows the general scheme of using the ILUT preconditioner in the RCI FGMRES context.

...

generate matrix A

generate preconditioner C (optional)

call `dfgmres_init(n, x, b, RCI_request, ipar, dpar, tmp)`

change parameters in ipar, dpar if necessary

call `dcsrilut(n, a, ia, ja, bilut, ibilut, jbilut, tol, maxfil, ipar, dpar, ierr)`

call `dfgmres_check(n, x, b, RCI_request, ipar, dpar, tmp)`

1 call `dfgmres(n, x, b, RCI_request, ipar, dpar, tmp)`

if `(RCI_request.eq.1)` then

multiply the matrix A by `tmp(ipar(22))` and put the result in `tmp(ipar(23))`

`c proceed with FGMRES iterations`

`goto 1`

`endif`

`if (RCI_request.eq.2) then`

do the stopping test

`if` (test not passed) `then`

`c` proceed with FGMRES iterations

`go to 1`

`else`

`c` stop FGMRES iterations.

`goto 2`

`endif`

`endif`

`if (RCI_request.eq.3)` then

`c` Below, `trvec` is an intermediate vector of length at least n

`c` Here is the recommended use of the result produced by the ILUT routine.

`c` via standard Intel MKL Sparse Blas solver routine mkl_dcsrtrsv.

`call mkl_dcsrtrsv('L','N','U', n, bilut, ibilut, jbilut, tmp(ipar(22)),trvec)`

`call mkl_dcsrtrsv('U','N','N', n, bilut, ibilut, jbilut, trvec, tmp(ipar(23)))`

`c` proceed with FGMRES iterations

`goto 1`

`endif`

`if (RCI_request.eq.4) then`

check the norm of the next orthogonal vector, it is contained in `dpar(7)`

`if` (the norm is not zero up to rounding/computational errors) `then`

`c proceed with FGMRES iterations`

`goto 1`

`else`

`c stop FGMRES iterations`

`goto 2`

`endif`

`endif`

2 call `dfgmres_get(n, x, b, RCI_request, ipar, dpar, tmp, itercount)`

current iteration number is in itercount

the computed approximation is in the array x

- ILU0 and ILUT Preconditioners Interface Description
- dcsrilu0
  ILU0 preconditioner based on incomplete LU factorization of a sparse matrix.
- dcsrilut
  ILUT preconditioner based on the incomplete LU factorization with a threshold of a sparse matrix.

Parent topic: Sparse Solver Routines