Y. Notay et Zo. Amar, A NEARLY OPTIMAL PRECONDITIONING BASED ON RECURSIVE RED-BLACK ORDERINGS, Numerical linear algebra with applications, 4(5), 1997, pp. 369-391
Considering matrices obtained by the application of a five-point stenc
il on a 2D rectangular grid, we analyse a preconditioning method intro
duced by Axelsson and Eijkhout, and by Brand and Heinemann. In this me
thod, one performs a (modified) incomplete factorization with respect
to a So-called 'repeated' or 'recursive' red-black ordering of the unk
nowns while fill-in is accepted provided that the red unknowns in a sa
me level remain uncoupled. Considering discrete second order elliptic
PDEs with isotropic coefficients, we show that the condition number is
bounded by O(n1/2 (log2(root 5-1))) where n is the total number of un
knowns(1/2 log(2)(root 5-1) = 0.153), and thus, that the total arithme
tic work for the solution is bounded by O(n(1.077)). Our condition num
ber estimate, which turns out to be better than standard O(log(2) n) e
stimates 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. (C) 1997
by John Wiley & Sons, Ltd.