Optimal Order Preconditioning of Finite Difference Matrices

Yvon Notay
Universite Libre de Bruxelles
Service de Metrologie Nucleaire (CP 165)
50 av. F.D.Roosevelt
B-1050 Bruxelles


A new multilevel preconditioner is proposed for the iterative solution of two dimensional discrete second order elliptic PDEs. It is based a recursive block incomplete factorization of the system matrix partitioned in a two-by-two block form, in which the submatrix related to the first block of unknowns is approximated by a MILU(0) factorization, and the Schur complement computed from a diagonal approximation of the latter submatrix.

It is shown that this technique, combined with a simple W cycle scheme, leads to optimal order preconditioning of five point finite difference matrices. This result holds independently of possible anisotropy or jumps in the PDE coefficients as long as the latter are piecewise constant on the coarsest mesh. Numerical results illustrate the efficiency and the robustness of the proposed method.

Contributed April 2, 1998.