# Does incomplete LU preconditioning improve the asymptotic scaling of Krylov subspace methods?

It is well known that unpreconditioned Krylov subspace methods applied to the finite-difference-discretised Poisson equation with $$n$$ grid points per direction require $$O(n \, |\log(\varepsilon)|)$$ iterations to reduce the error in the initial guess by a factor $$\varepsilon \in (0,1)$$. This is typically a prohibitively large number of iterations; hence it is often suggested to reduce the number of iterations through incomplete LU (ILU) preconditioning.

My question is: does ILU reduce the $$\text{# iterations} = O(n \,|\log(\varepsilon)|)$$ estimate asymptotically (e.g. to $$\text{# iterations} = O(\sqrt{n} \,|\log(\varepsilon)|)$$), or does it merely reduce the prefactor implied by the big-O notation?

My own experiments seem to suggest that ILU preconditioning only improves the prefactor, but maybe I am not using the method properly?

• According to the below reference, "the speed of convergence of conjugate gradients is proportional to the square root of the condition number". Perhaps your system's condition number is growing faster than your preconditioner is reducing it. sciencedirect.com/science/article/pii/S0377042702005344 – Charlie S Nov 24 '20 at 3:52
• ILU is not even guaranteed to improve the condition number. It just sometimes works, or in your words, reduces the prefactor. If you are only interested in the Poisson equation, something like ADI will both be equally simple and more efficient. – Abdullah Ali Sivas Nov 24 '20 at 8:18
• ADI sounds like a good idea! I wonder why standard textbooks like Saad (2003) or Demmel (1997) do not mention it. Maybe that is because ADI cannot be generalised to general triangular / tetrahedral meshes? – gTcV Nov 24 '20 at 8:56
• If you're interested in Poisson, use multi-grid. – Bill Barth Nov 24 '20 at 16:29
• ADI does not generalize well, it is also somehow outdated. There are some uses for it with advection-diffusion equations. However, in that case, ADI preconditioners become pretty expensive. I suggested ADI over multi-grid, because IMO, multi-grid is rather involved for most general topic classes. However, if you want to teach preconditioning, it is definitely the way to go. I would suggest you to take a look at Chapter 2 of "Finite Elements and Fast Iterative Solvers" by Elman, Silvester and Wathen. They both cover convergence results for CG and optimality of multi-grid. – Abdullah Ali Sivas Nov 26 '20 at 5:08