Data Structures and Requirements for hp Finite Element Software

Finite element methods approximate solutions of partial differential equations by restricting the problem to a finite dimensional function space. In hp adaptive finite element methods, one defines these discrete spaces by choosing different polynomial degrees for the shape functions defined on a locally refined mesh. Although this basic idea is quite simple, its implementation in algorithms and data structures is challenging. It has apparently not been documented in the literature in its most general form. Rather, most existing implementations appear to be for special combinations of finite elements, or for discontinuous Galerkin methods. In this article, we discuss generic data structures and algorithms used in the implementation of hp methods for arbitrary elements, and the complications and pitfalls one encounters. As a consequence, we list the information a description of a finite element has to provide to the generic algorithms for it to be used in an hp context. We support our claim that our reference implementation is efficient using numerical examples in two dimensions and three dimensions, and demonstrate that the hp-specific parts of the program do not dominate the total computing time. This reference implementation is also made available as part of the Open Source deal. II finite element library.