A NEARLY OPTIMAL PRECONDITIONING BASED ON RECURSIVE RED-BLACK ORDERINGS

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.