A nearly optimal preconditioning based on recursive red-black orderings

Considering matrices obtained by the application of a five-point stencil on a 2D rectangular grid, we analyse a preconditioning method introduced by Axelsson and Eijkhout, and by Brand and Heinemann. In this method, one performs a (modified) incomplete factorization with respect to a so-called ‘repeated’ or ‘recursive’ red–black ordering of the unknowns while fill-in is accepted provided that the red unknowns in a same level remain uncoupled. Considering discrete second order elliptic PDEs with isotropic coefficients, we show that the condition number is bounded by 𝒪(n) where n is the total number of unknowns (½ log2(√(5) − 1) = 0.153), and thus, that the total arithmetic work for the solution is bounded by 𝒪(n1.077). Our condition number estimate, which turns out to be better than standard 𝒪(log2 n) estimates for any realistic problem size, is purely algebraic and holds in the presence of Neumann boundary conditions and/or discontinuities in the PDE coefficients. Numerical tests are reported, displaying the efficiency of the method and the relevance of our analysis.