The hp -adaptive finite element method—where one independently chooses the mesh size ( h ) and polynomial degree ( p ) to be used on each cell—has long been known to have better theoretical convergence properties than either h - or p -adaptive methods alone. However, it is not widely used, owing at least in part to the difficulty of the underlying algorithms and the lack of widely usable implementations. This is particularly true when used with continuous finite elements. Herein, we discuss algorithms that are necessary for a comprehensive and generic implementation of hp -adaptive finite element methods on distributed-memory, parallel machines. In particular, we will present a multistage algorithm for the unique enumeration of degrees of freedom suitable for continuous finite element spaces, describe considerations for weighted load balancing, and discuss the transfer of variable size data between processes. We illustrate the performance of our algorithms with numerical examples and demonstrate that they scale reasonably up to at least 16,384 message passage interface processes. We provide a reference implementation of our algorithms as part of the open source library deal.II .

The traditional workflow in continuum mechanics simulations is that a geometry description —for example obtained using Constructive Solid Geometry (CSG) or Computer Aided Design (CAD) tools—forms the input for a mesh generator. The mesh is then used as the sole input for the finite element, finite volume, and finite difference solver, which at this point no longer has access to the original, “underlying” geometry. However, many modern techniques—for example, adaptive mesh refinement and the use of higher order geometry approximation methods—really do need information about the underlying geometry to realize their full potential. We have undertaken an exhaustive study of where typical finite element codes use geometry information, with the goal of determining what information geometry tools would have to provide. Our study shows that nearly all geometry-related needs inside the simulators can be satisfied by just two “primitives”: elementary queries posed by the simulation software to the geometry description. We then show that it is possible to provide these primitives in all of the frequently used ways in which geometries are described in common industrial workflows, and illustrate our solutions using a number of examples.

Finite element codes typically use data structures that represent unstructured meshes as collections of cells, faces, and edges, each of which require associated coordinate systems. One then needs to store how the coordinate system of each edge relates to that of neighboring cells. However, we can simplify data structures and algorithms if we can a priori orient coordinate systems in such a way that the coordinate systems on the edges follow uniquely from those on the cells by rule. Such rules require that every unstructured mesh allow the assignment of directions to edges that satisfy the convention in adjacent cells. We show that the convention chosen for unstructured quadrilateral meshes in the deal.II library always allows to orient meshes. It can therefore be used to make codes simpler, faster, and less bug prone. We present an algorithm that orients meshes in O ( N ) operations. We then show that consistent orientations are not always possible for 3D hexahedral meshes. Thus, cells generally need to store the direction of adjacent edges, but our approach also allows the characterization of cases where this is not necessary. The 3D extension of our algorithm either orients edges consistently, or aborts, both within O ( N ) steps.

Many operations that need to be performed in modern finite element codes can be described as an operation that needs to be done independently on every cell, followed by a reduction of these local results into a global data structure. For example, matrix assembly, estimating discretization errors, or converting nodal values into data structures that can be output in visualization file formats all fall into this class of operations. Using this realization, we identify a software design pattern that we call WorkStream and that can be used to model such operations and enables the use of multicore shared memory parallel processing. We also describe in detail how this design pattern can be efficiently implemented, and we provide numerical scalability results from its use in the deal .II software library.

Today's largest supercomputers have 100,000s of processor cores and offer the potential to solve partial differential equations discretized by billions of unknowns. However, the complexity of scaling to such large machines and problem sizes has so far prevented the emergence of generic software libraries that support such computations, although these would lower the threshold of entry and enable many more applications to benefit from large-scale computing. We are concerned with providing this functionality for mesh-adaptive finite element computations. We assume the existence of an “oracle” that implements the generation and modification of an adaptive mesh distributed across many processors, and that responds to queries about its structure. Based on querying the oracle, we develop scalable algorithms and data structures for generic finite element methods. Specifically, we consider the parallel distribution of mesh data, global enumeration of degrees of freedom, constraints, and postprocessing. Our algorithms remove the bottlenecks that typically limit large-scale adaptive finite element analyses. We demonstrate scalability of complete finite element workflows on up to 16,384 processors. An implementation of the proposed algorithms, based on the open source software p4est as mesh oracle, is provided under an open source license through the widely used deal.II finite element software library.

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.

An overview of the software design and data abstraction decisions chosen for deal.II, a general purpose finite element library written in C++, is given. The library uses advanced object-oriented and data encapsulation techniques to break finite element implementations into smaller blocks that can be arranged to fit users requirements. Through this approach, deal.II supports a large number of different applications covering a wide range of scientific areas, programming methodologies, and application-specific algorithms, without imposing a rigid framework into which they have to fit. A judicious use of programming techniques allows us to avoid the computational costs frequently associated with abstract object-oriented class libraries. The paper presents a detailed description of the abstractions chosen for defining geometric information of meshes and the handling of degrees of freedom associated with finite element spaces, as well as of linear algebra, input/output capabilities and of interfaces to other software, such as visualization tools. Finally, some results obtained with applications built atop deal.II are shown to demonstrate the powerful capabilities of this toolbox.