ALGEBRAIC MULTIGRID FOR MODERATE ORDER FINITE ELEMENTS

We investigate the use of algebraic multigrid (AMG) methods for the solution of large sparse linear systems arising from the discretization of scalar elliptic partial differential equations with Lagrangian finite elements of order at most 4. The resulting system matrices do not have the M-matrix property that is required by standard analyses of classical AMG and aggregation-based AMG methods. A unified approach is presented that allows us to extend these analyses. It uses an intermediate M-matrix and highlights the role of the spectral equivalence constant that relates this matrix to the original system matrix. This constant is shown to be bounded independently of the problem size and jumps in the coefficients of the partial differential equations, provided that jumps are located at elements ’ boundaries. For two-dimensional problems, it is further shown to be uniformly bounded if the angles in the triangulation also satisfy a uniform bound. This analysis validates the application of the AMG methods to the considered problems. On the other hand, because the intermediate M-matrix can be computed automatically, an alternative strategy is to define the AMG preconditioners from this matrix, instead of defining them from the original matrix. Numerical experiments are presented that assess both strategies using publicly available state-of-the-art implementations of classical AMG and aggregation-based AMG methods