# Taxonomy of ILU preconditioners

I learned that for BiCGStab solver for sparse linear systems it's pretty much always necessary to use a preconditioner. I realized by now that choosing a good one is problem dependent.

Surfing the web I found out there are many ILU based preconditioners (ILUT, MILU,etc.) This is where I got confused.

I was wondering if someone can briefly explain taxonomy of ILU preconditioners, give some literature sources for particular ones, and which of those are suited for BiCGStab.

The setting in which I'm working is CFD, and code is based on unstructured finite volume discretization. Probably different preconditioners will be needed for momentum equation and transport equations for turbulence scalars.

A preconditioner, say M, is an approximation on the system matrix, say A that changes the problem into another problem with improved eigenvalue spectrum. A perfect preconditioner would be inverse of A i.e inv(M) = A.

Unfortunately, this inverse is normally not avaiable, too complicated to compute, requires more space to store because of the fill-in's introduced during the factorization and also might suffer from round-off errors. Hence, a preconditioner should be easy to compute and apply yet effective.

Besides the basic preconditioner like Jacobi or Gauss-Seidel (or SOR), one of the most frequrently preconditioners is ILU (IC in symmetric problems - you are working on CFD so the systems or non-symmetric)

Selection of the preconditioner normally depends on your problem. ILU has many variants like ILUT,ILUS,MILU etc. You can consult the literature I added at then end. For problems with mild difficulty, ILU(0) can be used but as the problems get harder i.e. Reynolds number is increasing more fill-ins (eg. ILU(1)) with thresholding strategies (ILUT) should be used. The problem is, advanced uses of ILU requires more memory and the determination of the sparsity pattern which is now different than your system matrix. In this case, you have to compute the spartisity pattern symbolically first and numerically later.

The are several ideas to reduce the computation work,

• use of lagged preconditioners at which you avoid recomputing the preconditioner even if the linear system varies.
• use of LU-SGS like preconditioner which might be implemented efficiently with flux splitting algorithms.
• use of matrix-free methods - the one I preferred in my PhD work. Newton-Krylov solvers where the jacobian is not needed expect for preconditioner which is normally calculated with a low-order approximation and probably with color-based algorithms (more difficult in unstructured problems, though).
• use of only diffusion operators like laplacian and avoiding convective terms (not efficient in reducing number of iterations)
• multigrid, where you use a simple smoother like w-Jacobi or SOR in a grid hierarchy. for unstructed problems you should use Algebraic multigrid (AMG) instead of geometric.
• and many others (multiply the number of my entries with 10)..

Since the problem is non-symmetric, there are mainly two solvers to use: GMRES or BiCGStab. (QMR or TFQMR are other alternative but I believe its performance is below those two). GMRES is normally a better solver if you have no storage problem yet because of the stored vectors a restart is needed - this is a problem is the preconditioner is poor or you have very large dof. BiCGStab requires only four Matrix-Vector product which is nice for large problems but normally inferior to GMRES. (I preferred GMRES but I like BiCGStab very much!)

All of this preconditioner, linear solver issue is way complex. I can suggest some books to read. Your starting point should be Templates for the solution of linear systems This is a free book. Smoothers both as standalone solvers and preconditioners on Krylov solvers is explained in this book. You can also consult to Yousef Saad's "Iterative Methods for Sparse Linear Systems". It is definitive in the library of your institution. First edition is also avaiable here.

Before concluding, I recommend you to look at frameworks like Petsc, Trilinos or even Hypre and also the files provided by 1. They provide preconditioners with some programming. There are actually more books to offer but also take a look in Ke Chen's "Matrix Preconditioning Techniques and Applications". Matlab codes are avaiable with the book.

Good luck in your journey, you'll need it.

• Thank you very much! I have both books and I'm still digging - this is really interesting topic! May 25, 2012 at 21:14

The book by Y. Saad is also one of the standard references for solvers and preconditioners.

• I understand by now that he is one of the heroes of Krylov space methods. I would probably bore him to death with questions if he was my advisor. May 26, 2012 at 7:09