2
$\begingroup$

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?

Improve this question
$\endgroup$
7
  • 2
    $\begingroup$ 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 $\endgroup$
    – Charlie S
    Nov 24, 2020 at 3:52
  • 1
    $\begingroup$ 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. $\endgroup$
    – Abdullah Ali Sivas
    Nov 24, 2020 at 8:18
  • $\begingroup$ 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? $\endgroup$
    – gTcV
    Nov 24, 2020 at 8:56
  • 1
    $\begingroup$ If you're interested in Poisson, use multi-grid. $\endgroup$
    – Bill Barth
    Nov 24, 2020 at 16:29
  • 1
    $\begingroup$ 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. $\endgroup$
    – Abdullah Ali Sivas
    Nov 26, 2020 at 5:08

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.