William F Mitchell
The hp-Multigrid Method Applied to hp-Adaptive Finite Elements

100 Bureau Dr Stop 8910
NIST
Gaithersburg
MD 20899-8910
william.mitchell@nist.gov

Recently the $hp$ version of the finite element method has received increasing attention. This is an adaptive finite element approach in which adaptivity occurs in both the size, $h$, of the elements (spacial or $h$ adaptivity) and in the order, $p$, of the approximating piecewise polynomials (order or $p$ adaptivity). The objective is to determine a distribution of $h$ and $p$ that minimizes the error using the least amount of work in some measure. The main attraction of $hp$ adaptivity is that, in theory, the discretization error can decrease exponentially with the number of degrees of freedom, $n$, even in the presence of singularities, and this rate of convergence has been observed in practice.

It is desirable to combine this optimal order discretization method with an optimal order algebraic solution method, such as multigrid. Most published work in $hp$ adaptive methods to date has focused on domain decomposition and preconditioned conjugate gradient type solvers or used direct solvers. In this presentation we present the $hp$-multigrid method for high order finite elements and $hp$-adaptive grids.

An intriguing notion is to use the values of $p$ as the levels of a multilevel method. This was first proposed in 1985 for the $p$-version of the finite element method by Craig and Zienkiewicz [1]. Several other researchers developed multilevel methods based on $p$ in the later half of the 1980's, with Babuka et al. [2] coining the term multi-$p$ (as opposed to multigrid) method. Theoretical $p$-independent (or nearly independent) convergence was established in the 1990's by Maday, Muñoz, Patera and Rønquist [3] and by Hu, Guo and Katz [4]. In the later 1990's and early 2000's the term $p$-multigrid was adopted, and it was mostly used in conjunction with the discontinuous Galerkin method for hyperbolic conservation laws.

The basic idea of the $p$-multigrid method is to use the $p$-hierarchical basis for the finite element space and perform a classic V-cycle in which the $k^{th}$ level consists of all the bases up to degree $k$. The system of equations on level 1, i.e. the linear basis functions, is solved with a direct method. Nastase and Mavriplis [5] replaced the direct solver with a classic $h$-multigrid method, and coined the term $hp$-multigrid method.

Most of the results presented with $p-$ and $hp$-multigrid methods has been with spectral element methods and discontinuous Galerkin methods. Although some of the papers mention $hp$-adaptivity, to the author's knowledge no papers have presented results using $hp$-adaptively refined meshes. In this talk we define the $hp$-multigrid method in the context of $hp$-adaptive finite elements for bisected triangular elements in 2D, and present numerical convergence results using elliptic problems with singular and nearly singular solutions. The results exhibit residual contraction factors that are independent of both $h$ and $p$.

References

[1] Craig, A.W. and Zienkiewicz, O.C., A multigrid algorithm using a hierarchical finite element basis, in Multigrid Methods for Integral and Differential Equations, D.J. Paddon and Holstein (eds.), Clarendon Press, Oxford, 1985, pp. 310-312.

[2] Babuska, I., Griebel, M. and Pitkaranta, J., The problem of selecting the shape functions for a p-type finite element, Internat. J. Numer. Methods Engng., 28, (1989), pp. 1891-1908.

[3] Maday, Y., Muñoz, R., Patera, A.T. and Rønquist, E.M., Spectral element multigrid methods, in Proc. of the IMACS Int. Symposium on Iterative Methods in Linear Algebra, P. de Groen and R. Beauwens (eds.), Elsevier, Amsterdam, 1992, pp. 191-201.

[4] Hu, N., Guo, X.-Z. and Katz, I., Multi-$p$ preconditioners, SIAM J. Sci. Comput., 18, (1997), pp. 1676-1697.

[5] Nastase, C.R. and Mavriplis, D.J., High-order discontinuous Galerkin methods using an $hp$-multigrid approach, J. Comput. Phys., 213, (2006), pp. 330-357.