Algebraic multigrid methods based on element preconditioning

This paper presents a new algebraic multigrid (AMG) solution strategy for large linear systems with a sparse matrix arising from a finite element discretization of some self-adjoint, second order, scalar, elliptic partial differential equation. The AMG solver is based on Ruge/Stuben's method. Ruge/Stuben's algorithm is robust for M-matrices, but unfortunately the "region of robustness" between symmetric positive definite M-matrices and general symmetric positive definite matrices is very fuzzy. For this reason the so-called element preconditioning technique is introduced in this paper. This technique aims at the construction of an M-matrix that is spectrally equivalent to the original stiffness matrix. This is done by solving small restricted optimization problems. AMG applied to the spectrally equivalent M-matrix instead of the original stiffness matrix is then used as a preconditioner in the conjugate gradient method for solving the original problem. The numerical experiments show the efficiency and the robustness of the new preconditioning method for a wide class of problems including problems with anisotropic elements.