Hybrid $V$-cycle algebraic multilevel preconditioners

Abstract:

We consider an algebraic derivation of multilevel preconditioners which are based on a sequence of finite element stiffness matrices. They correspond to a sequence of triangulations obtained by successive refinement and the associated finite element discretizations of second-order self adjoint elliptic boundary value problems. The stiffness matrix at a given discretization level is partitioned into a natural hierarchical two-level two-by-two block form. Then it is factored into block triangular factors. The resulting Schur complement is then replaced (approximated) by the stiffness matrix on the preceding (coarser) level. This process is repeated successively for a fixed number ${k_0} \geq 1$ of steps. After each ${k_0}$ steps, the preconditioner so derived is corrected by a certain polynomial approximation, a properly scaled and shifted Chebyshev matrix polynomial which involves the preconditioner and the stiffness matrix at the considered level. The hybrid V-cycle preconditioner thus derived is shown to be of optimal order of complexity for 2-D and 3-D problem domains. The relative condition number of the preconditioner is bounded uniformly with respect to the number of levels and with respect to possible jumps of the coefficients of the considered elliptic bilinear form as long as they occur only across edges (faces in 3-D) of elements from the coarsest triangulation. In addition, an adaptive implementation of our hybrid V-cycle preconditioners is proposed, and its practical behavior is demonstrated on a number of test problems.