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. Categories and Subject Descriptors: E.1 [Data Structures]; G.4 [Mathematical Software]; G.1.8 [Numerical Analysis]: Partial Differential Equations--Finite element methods General Terms: Algorithms, Design Additional Key Words and Phrases: Object orientation, data structures, software design, finite element software, hp finite element methods ACM Reference Format: Bangerth, W. and Kayser-Herold, O. 2009. Data structures and requirements for hp finite element software. ACM Trans. Math. Softw. 36, 1, Article 4 (March 2009), 31 pages. DOI = 10.1145/1486525.1486529 http://doi.acm.org/10.1145/1486525.1486529