skip to main content

This content will become publicly available on April 1, 2023

Title: Direct serendipity and mixed finite elements on convex quadrilaterals
Abstract The classical serendipity and mixed finite element spaces suffer from poor approximation on nondegenerate, convex quadrilaterals. In this paper, we develop families of direct serendipity and direct mixed finite element spaces, which achieve optimal approximation properties and have minimal local dimension. The set of local shape functions for either the serendipity or mixed elements contains the full set of scalar or vector polynomials of degree r , respectively, defined directly on each element (i.e., not mapped from a reference element). Because there are not enough degrees of freedom for global $$H^1$$ H 1 or $$H(\text {div})$$ H ( div ) conformity, exactly two supplemental shape functions must be added to each element when $$r\ge 2$$ r ≥ 2 , and only one when $$r=1$$ r = 1 . The specific choice of supplemental functions gives rise to different families of direct elements. These new spaces are related through a de Rham complex. For index $$r\ge 1$$ r ≥ 1 , the new families of serendipity spaces $${\mathscr {DS}}_{r+1}$$ DS r + 1 are the precursors under the curl operator of our direct mixed finite element spaces, which can be constructed to have reduced or full $$H(\text {div})$$ H ( more » div ) approximation properties. One choice of direct serendipity supplements gives the precursor of the recently introduced Arbogast–Correa spaces (SIAM J Numer Anal 54:3332–3356, 2016. 10.1137/15M1013705 ). Other fully direct serendipity supplements can be defined without the use of mappings from reference elements, and these give rise in turn to fully direct mixed spaces. Our development is constructive, so we are able to give global bases for our spaces. Numerical results are presented to illustrate their properties. « less
; ;
Award ID(s):
2111159 1720349 1418752
Publication Date:
Journal Name:
Numerische Mathematik
Page Range or eLocation-ID:
929 to 974
Sponsoring Org:
National Science Foundation
More Like this
  1. Abstract

    We construct new families ofdirectserendipity anddirectmixed finite elements on general planar, strictly convex polygons that areH1andH(div) conforming, respectively, and possess optimal order of accuracy for any order. They have a minimal number of degrees of freedom subject to the conformity and accuracy constraints. The name arises because the shape functions are defineddirectlyon the physical elements, i.e., without using a mapping from a reference element. The finite element shape functions are defined to be the full spaces of scalar or vector polynomials plus a space of supplemental functions. The direct serendipity elements are the precursors of the direct mixed elements in a de Rham complex. The convergence properties of the finite elements are shown under a regularity assumption on the shapes of the polygons in the mesh, as well as some mild restrictions on the choices one can make in the construction of the supplemental functions. Numerical experiments on various meshes exhibit the performance of these new families of finite elements.

  2. We present an implementation of the trimmed serendipity finite element family, using the open-source finite element package Firedrake. The new elements can be used seamlessly within the software suite for problems requiring H 1 , H (curl), or H (div)-conforming elements on meshes of squares or cubes. To test how well trimmed serendipity elements perform in comparison to traditional tensor product elements, we perform a sequence of numerical experiments including the primal Poisson, mixed Poisson, and Maxwell cavity eigenvalue problems. Overall, we find that the trimmed serendipity elements converge, as expected, at the same rate as the respective tensor product elements, while being able to offer significant savings in the time or memory required to solve certain problems.
  3. We introduce the family of trimmed serendipity finite element differential form spaces, defined on cubical meshes in any number of dimensions, for any polynomial degree, and for any form order. The relation between the trimmed serendipity family and the (non-trimmed) serendipity family developed by Arnold and Awanou [Math. Comp. 83(288) 2014] is analogous to the relation between the trimmed and (non-trimmed) polynomial finite element differential form families on simplicial meshes from finite element exterior calculus. We provide degrees of freedom in the general setting and prove that they are unisolvent for the trimmed serendipity spaces. The sequence of trimmed serendipity spaces with a fixed polynomial order r provides an explicit example of a system described by Christiansen and Gillette [ESAIM:M2AN 50(3) 2016], namely, a minimal compatible finite element system on squares or cubes containing order r-1 polynomial differential forms.
  4. Abstract

    We consider the problem of covering multiple submodular constraints. Given a finite ground setN, a weight function$$w: N \rightarrow \mathbb {R}_+$$w:NR+,rmonotone submodular functions$$f_1,f_2,\ldots ,f_r$$f1,f2,,froverNand requirements$$k_1,k_2,\ldots ,k_r$$k1,k2,,krthe goal is to find a minimum weight subset$$S \subseteq N$$SNsuch that$$f_i(S) \ge k_i$$fi(S)kifor$$1 \le i \le r$$1ir. We refer to this problem asMulti-Submod-Coverand it was recently considered by Har-Peled and Jones (Few cuts meet many point sets. CoRR.arxiv:abs1808.03260Har-Peled and Jones 2018) who were motivated by an application in geometry. Even with$$r=1$$r=1Multi-Submod-Covergeneralizes the well-known Submodular Set Cover problem (Submod-SC), and it can also be easily reduced toSubmod-SC. A simple greedy algorithm gives an$$O(\log (kr))$$O(log(kr))approximation where$$k = \sum _i k_i$$k=ikiand this ratio cannot be improved in the general case. In this paper, motivated by several concrete applications, we consider two ways to improve upon the approximation given by the greedy algorithm. First, we give a bicriteria approximation algorithm forMulti-Submod-Coverthat covers each constraint to within a factor of$$(1-1/e-\varepsilon )$$(1-1/e-ε)while incurring an approximation of$$O(\frac{1}{\epsilon }\log r)$$O(1ϵlogr)in the cost. Second, we consider the special case when each$$f_i$$fiis a obtained from a truncated coverage function and obtain an algorithm that generalizes previous work on partial set cover (Partial-SC), covering integer programs (CIPs) and multiple vertex cover constraintsmore »Bera et al. (Theoret Comput Sci 555:2–8 Bera et al. 2014). Both these algorithms are based on mathematical programming relaxations that avoid the limitations of the greedy algorithm. We demonstrate the implications of our algorithms and related ideas to several applications ranging from geometric covering problems to clustering with outliers. Our work highlights the utility of the high-level model and the lens of submodularity in addressing this class of covering problems.

    « less
  5. Higher order finite element (FE) methods provide significant advantages in a number of applications such as wave propagation, where high order shape functions help to mitigate pollution (dispersion) error. However, classical assembly of higher order systems is computationally burdensome, requiring the evaluation of many point quadrature schemes. When the Discontinuous Petrov-Galerkin (DPG) FE methodology is employed, the use of an enriched test space further increases the computational burden of system assembly, increasing the relevance of improved assembly techniques. Sum factorization—a technique that exploits the tensorproduct structure of shape functions to accelerate numerical integration—was proposed in Ref. [10] for the assembly of DPG matrices on hexahedral elements that reduced the computational complexity from order (p9) to (p7) (where p denotes polynomial order). In this work we extend the concept of sum factorization to the construction of DPG matrices on prismatic elements by expressing prism shape functions as tensor products of 2D simplex and 1D interval shape functions. Unexpectedly, the resulting sum factorization routines on partially-tensorized prism shape functions achieve the same (p7) complexity as sum factorization on fully-tensorized hexahedra shape functions (as products of 1D interval shape functions) presented in Ref. [10]. Throughout this work we adhere to the theory ofmore »exact sequence energy spaces, proposing sum factorization routines for each of the 3D FE exact sequence energy spaces—H1, H(curl), H(div), and L2. Computational results for construction of the DPG Gram matrix on a prismatic element in each exact sequence energy space are presented, corroborating the expected (p7) complexity. Additionally, construction of the DPG system for an ultraweak Maxwell problem on a prismatic element is considered and a partially-tensorized sum factorization for hexahedral elements is proposed to improve implementational compatibility between hexahedral and prismatic elements.« less