Premium
A nearly optimal preconditioning based on recursive red–black orderings
Author(s) -
Notay Yvan,
Amar Zakaria Ould
Publication year - 1997
Publication title -
numerical linear algebra with applications
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.02
H-Index - 53
eISSN - 1099-1506
pISSN - 1070-5325
DOI - 10.1002/(sici)1099-1506(199709/10)4:5<369::aid-nla105>3.0.co;2-a
Subject(s) - mathematics , combinatorics , algorithm
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 ½ log 2 (√(5) −1)) where n is the total number of unknowns (½ log 2 (√(5) − 1) = 0.153), and thus, that the total arithmetic work for the solution is bounded by ( n 1.077 ). Our condition number estimate, which turns out to be better than standard (log 2 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. © 1997 John Wiley & Sons, Ltd.