We construct new families of
This content will become publicly available on April 1, 2023
 Publication Date:
 NSFPAR ID:
 10354701
 Journal Name:
 Numerische Mathematik
 Volume:
 150
 Issue:
 4
 Page Range or eLocationID:
 929 to 974
 ISSN:
 0029599X
 Sponsoring Org:
 National Science Foundation
More Like this

Abstract direct serendipity anddirect mixed finite elements on general planar, strictly convex polygons that areH ^{1}andH (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 defineddirectly on 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. 
We present an implementation of the trimmed serendipity finite element family, using the opensource 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.

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 (nontrimmed) serendipity family developed by Arnold and Awanou [Math. Comp. 83(288) 2014] is analogous to the relation between the trimmed and (nontrimmed) 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 r1 polynomial differential forms.

Abstract We consider the problem of covering multiple submodular constraints. Given a finite ground set
N , a weight function ,$$w: N \rightarrow \mathbb {R}_+$$ $w:N\to {R}_{+}$r monotone submodular functions over$$f_1,f_2,\ldots ,f_r$$ ${f}_{1},{f}_{2},\dots ,{f}_{r}$N and requirements the goal is to find a minimum weight subset$$k_1,k_2,\ldots ,k_r$$ ${k}_{1},{k}_{2},\dots ,{k}_{r}$ such that$$S \subseteq N$$ $S\subseteq N$ for$$f_i(S) \ge k_i$$ ${f}_{i}\left(S\right)\ge {k}_{i}$ . We refer to this problem as$$1 \le i \le r$$ $1\le i\le r$MultiSubmodCover and it was recently considered by HarPeled and Jones (Few cuts meet many point sets. CoRR.arxiv:abs1808.03260 HarPeled and Jones 2018) who were motivated by an application in geometry. Even with$$r=1$$ $r=1$MultiSubmodCover generalizes the wellknown Submodular Set Cover problem (SubmodSC ), and it can also be easily reduced toSubmodSC . A simple greedy algorithm gives an approximation where$$O(\log (kr))$$ $O(log(kr\left)\right)$ and 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 for$$k = \sum _i k_i$$ $k={\sum}_{i}{k}_{i}$MultiSubmodCover that covers each constraint to within a factor of while incurring an approximation of$$(11/e\varepsilon )$$ $(11/e\epsilon )$ in the cost. Second, we consider the special case when each$$O(\frac{1}{\epsilon }\log r)$$ $O(\frac{1}{\u03f5}logr)$ is a obtained from a truncated coverage function and obtain an algorithm that generalizes previous work on partial set cover ($$f_i$$ ${f}_{i}$PartialSC ), covering integer programs (CIPs ) and multiple vertex cover constraintsmore » 
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 PetrovGalerkin (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 partiallytensorized prism shape functions achieve the same (p7) complexity as sum factorization on fullytensorized hexahedra shape functions (as products of 1D interval shape functions) presented in Ref. [10]. Throughout this work we adhere to the theory ofmore »