Abstract
This paper is concerned with the accurate, conservative, and stable imposition of boundary conditions and inter-element coupling for multi-dimensional summation-by-parts (SBP) finite-difference operators. More precisely, the focus is on diagonal-norm SBP operators that are not based on tensor products and are applicable to unstructured grids composed of arbitrary elements. We show how penalty terms—simultaneous approximation terms (SATs)—can be adapted to discretizations based on multi-dimensional SBP operators to enforce boundary and interface conditions. A general SAT framework is presented that leads to conservative and stable discretizations of the variable-coefficient advection equation. This framework includes the case where there are no nodes on the boundary of the SBP element at which to apply penalties directly. This is an important generalization, because elements analogous to Legendre–Gauss collocation, i.e. without boundary nodes, typically have higher accuracy for the same number of degrees of freedom. Symmetric and upwind examples of the general SAT framework are created using a decomposition of the symmetric part of an SBP operator; these particular SATs enable the pointwise imposition of boundary and inter-element conditions. We illustrate the proposed SATs using triangular-element SBP operators with and without nodes that lie on the boundary. The accuracy, conservation, and stability properties of the resulting SBP–SAT discretizations are verified using linear advection problems with spatially varying divergence-free velocity fields.
Similar content being viewed by others
Avoid common mistakes on your manuscript.
1 Introduction
We are interested in high-order discretizations that obey the summation by parts (SBP) property. The SBP property mimics integration by parts, and it greatly facilitates the construction of high-order schemes that are conservative and provably stable (linearly and nonlinearly) [1,2,3]. We are, in addition, interested in the flexibility provided by SBP operators that do not have a standard polynomial basis representation. In principle, this flexibility can be used to optimize SBP operators in various ways. For example, their efficiency can be improved by reducing their spectral radius or decreasing the number of floating point operations per node.
SBP methods have predominantly been developed in the context of high-order finite difference methods [4, 5] where the nodal distribution in computational space is uniform; see the review papers [6, 7] and the references therein. While SBP methods have been extended in a number of ways, for example see [8,9,10,11], the majority of these developments have been limited to one-dimensional operators that are applied to multi-dimensional problems using tensor-product operators in computational space. An interesting exception is the work by Nordström et al. [12], which presents a vertex-centered second-order-accurate finite-volume scheme with the SBP property on unstructured grids.
The tensor-product approach, while adequate for many applications, has limitations when applied to complex geometries and in the context of localized, anisotropic mesh adaptation. This motivates our interest in generalizing SBP operators to more general multi-dimensional subdomains, i.e. elements.
Building on the generalization in [9], we presented an SBP definition in [13] (see also [14]) that is suitable for arbitrary, bounded subdomains with piecewise smooth, orientable boundaries. For diagonal-normFootnote 1 multi-dimensional SBP operators that are exact for polynomials of total degree p, it was shown that the norm and corresponding nodes define a strong cubature rule that is exact for polynomials of degree \(2p-1\). This connection to cubature rules greatly simplifies the construction of SBP operators, since many suitable cubature rules have already been identified in the literature [15]. In this paper, we will only consider diagonal-norm operators.
SBP derivative operators do not inherently enforce boundary conditions or inter-element coupling. The majority of SBP-based discretizations rely on simultaneous approximation terms (SATs) [16,17,18,19] to impose boundary conditions, as well as inter-element coupling when the solution space is discontinuous. SATs are terms that impose boundary data and inter-element coupling in a weak sense and lead to stable and conservative schemes without impacting the asymptotic order of the discretization.
In [13] we derived SATs for multidimensional diagonal-norm SBP operators and showed that the resulting discretizations are stable for the linear constant-coefficient advection equation. Indeed, for constant-coefficient advection these penalties are the strong-form equivalent of the boundary-integrated numerical flux functions used in [20]. The SATs described in [13] can theoretically accommodate variable-coefficient advection problems; however, they are not practical for this class of problem because new SBP operators would be needed whenever the variable coefficients change.
The multi-dimensional SBP operators in [13] were designed to have a unisolvent set of nodes on each face for the appropriate space of polynomials. This constraint was imposed, in part, to simplify the construction of pointwise SATs, but it increases the total number of nodes required for the SBP cubature. For example, the quadratic, cubic, and quartic SBP operators for the triangle require 7, 12, and 18 nodes, respectively, rather than the 6, 10, and 15 nodes necessary for a total-degree basis [13]. A similar trend is observed for tetrahedral elements. Given the quadratic complexity of matrix-vector multiplication, there is impetus to minimize the number of volume nodes. In addition, it is well known that strong cubature rules without boundary nodes tend to be more accurate than rules with boundary nodes for the same number of nodes [15].
In light of the limitations of the SATs used in [13], the objectives of the present work are to:
-
1.
generalize the SAT definition to accommodate multi-dimensional SBP operators that may not have a sufficient number of boundary nodes to construct adequate face cubature rules, including operators that have no boundary nodes, and;
-
2.
develop SATs that lead to provably stable and conservative schemes for variable coefficient partial differential equations (PDEs) in split form.
The remainder of the paper is organized as follows. After introducing some notation, Sect. 2 reviews the definition of multi-dimensional SBP operators from [13]. Section 3 demonstrates the decomposition of the symmetric component of the SBP-derivative operator by considering a set of auxiliary nodes on the boundary using interpolation/extrapolation operators and face cubature rules. In Sects. 4 and 5 the general framework for construction of stable and conservative SATs is presented and two examples of SATs are discussed. In order to illustrate SATs on a concrete example, Sect. 6 presents two families of SBP operators for the triangle and describes how SATs are constructed for these operators. A numerical verification using the linear advection equation with a spatially varying divergence-free velocity field is given in Sect. 7, and conclusions are provided in Sect. 8.
2 Notation and Review of Multi-dimensional Summation-by-Parts Operators
This work builds on [13], so similar notation is maintained for consistency. As in that work, we focus on two-dimensional operators to simplify the presentation. One notable difference between the present work and [13] is that we consider general (smooth) bijective mappings from physical to computational space. Domains and their boundaries in physical space are denoted with \(\varOmega \) and \(\varGamma \), respectively. The corresponding sets in computational space are given by \(\hat{\varOmega }\) and \(\hat{\varGamma }\). Physical-space coordinates are represented with \((x,y) \in \varOmega \), and the computational-space coordinates are given by \((\xi ,\eta ) \in \hat{\varOmega }\). While we concentrate on elements that are polygons in computational space, the ideas presented in this paper can be directly extended to three dimensions. Several definitions and theorems are limited to operators defined in the \(\xi \) coordinate direction, since operators defined in the other directions are analogous.
Functions are denoted with capital letters with a script type; e.g., \({\mathcal {U}}(\xi ,\eta ,t) \in L^{2}(\hat{\varOmega }\times [0,T])\) denotes a square-integrable function on the space-time domain \(\hat{\varOmega }\times [0,T]\). Functions and operators are discretized on a set of n nodes, \(S_{\hat{\varOmega }}=\left\{ (\xi _{i},\eta _{i})\right\} _{i=1}^{n} \subset \hat{\varOmega }\). The restriction of a function to the nodes is a column vector that is represented using lower-case bold font. For example, in the case of \({\mathcal {U}}\) we would write
A number of definitions and theorems rely on the monomial basis, defined below in (partial) order of nondecreasing degree.
The cardinality of the monomial basis of total degree p is denoted
where d is the spatial dimension; for \(d=2\) this gives \(N^{*}_{p} = (p+1)(p+2)/2\). The monomials and their derivatives evaluated at the nodes are represented by the n-vectors
We will need the degree p (rectangular) Vandermonde matrix
as well as the associated matrix containing the projection of the \(\xi \) derivatives of the monomials onto a set of nodes, which we denote by
In this paper, we use Matlab notation; for example, \(\mathsf {M}(i\!:\!j,l\!:\!m)\) denotes the submatrix constructed from the i through j rows and l through m columns of the matrix \(\mathsf {M}\). Similarly, we use the notation \(\mathsf {M}(:,i)\) and \(\mathsf {M}(j,:)\) to denote the \(i^{\text {th}}\) column and \(j^{\text {th}}\) row of the matrix \(\mathsf {M}\), respectively.
We can now state the following definition of a multi-dimensional SBP operator that was proposed in [13]:
Definition 1
Two-dimensional summation-by-parts operator: Consider an open and bounded domain \(\hat{\varOmega }\subset \mathbb {R}^{2}\) with a piecewise-smooth boundary \(\hat{\varGamma }\). The matrix \(\mathsf {D}_{\xi }\) is a degree p SBP approximation to the first derivative \(\frac{\partial }{\partial \xi }\) on the nodes \(S_{\hat{\varOmega }}=\left\{ (\xi _{i},\eta _{i})\right\} _{i=1}^{n}\) if
-
I.
\(\mathsf {D}_{\xi }\varvec{p}_{k}= \varvec{p}_{k}',\qquad \forall \; k \in \{ 1,2,\ldots ,N^{*}_{p} \}\);
-
II.
\(\mathsf {D}_{\xi }= \mathsf {H}^{-1}\mathsf {Q}_{\xi }\), where \(\mathsf {H}\) is symmetric positive-definite; and
-
III.
\(\mathsf {Q}_{\xi }= \mathsf {S}_{\xi }+ \frac{1}{2}\mathsf {E}_{\xi }\), where \(\mathsf {S}_{\xi }^{{{\mathrm {T}}}}=-\mathsf {S}_{\xi }\), \(\mathsf {E}_{\xi }^{{{\mathrm {T}}}}=\mathsf {E}_{\xi }\), and \(\mathsf {E}_{\xi }\) satisfies
$$\begin{aligned} \varvec{p}_{k}^{{{\mathrm {T}}}}\mathsf {E}_{\xi }\varvec{p}_{m}=\displaystyle \oint _{\hat{\varGamma }}{\mathcal {P}}_{k}{\mathcal {P}}_{m}n_{\xi }{{\mathrm {d}}}\hat{\varGamma },\qquad \forall \; k,m \in \{ 1,2,\ldots ,N^{*}_{r}\}, \end{aligned}$$
where \(r\ge p\), and \(n_{\xi }\) is the \(\xi \) component of \(\varvec{n}=\left[ n_{\xi },n_{\eta }\right] ^{{{\mathrm {T}}}}\), the outward pointing unit normal on \(\hat{\varGamma }\).
A diagonal-norm SBP operator is one where \(\mathsf {H}\) is a diagonal matrix. As mentioned in the Introduction, such diagonal-norm operators are closely linked to cubature rules and, under mild assumptions on a generalized Vandermonde matrix, the existence of a cubature implies the existence of an SBP operator [13]. Conversely, the norm matrix \(\mathsf {H}\) is a cubature rule satisfying
where, at a minimum, \(\mathsf {H}\) is of degree \(2p-1\), i.e. the above equality holds provided \({\mathcal {P}}_{k}{\mathcal {P}}_{m}\) is at most degree \(2p-1\). In addition, since \(\mathsf {H}\) is symmetric positive definite, it defines the finite-dimensional norm (hence the name, norm matrix) that is a degree \(2p-1\) approximation to the \(L^2\) norm:
We use this norm frequently in the following stability analysis.
3 Decomposition of \(\mathsf {E}_{\xi }\)
The pointwise nature of SATs complicates their direct application to multi-dimensional SBP operators, which may not have any nodes on the boundary of their domain. Fortunately, as we show in this section, the \(\mathsf {E}_{\xi }\) and \(\mathsf {E}_{\eta }\) matrices of many multi-dimensional SBP operators can be decomposed in terms of nodes that lie on the boundary of \(\hat{\varOmega }\). These auxiliary nodes provide a straightforward means of applying traditional SAT penalties.
In order to proceed, we introduce some assumptions regarding the reference element, \(\hat{\varOmega }\), and its boundary, \(\hat{\varGamma }\).
Assumption 1
The reference element \(\hat{\varOmega }\) is a polygon, and its boundary \(\hat{\varGamma }\) is piecewise linear with \(\hat{\varGamma }= \bigcup _{j=1}^{N_{\hat{\varGamma }}} \hat{\varGamma }_{j}\) and \(\bigcap _{j=1}^{N_{\hat{\varGamma }}} \hat{\varGamma }_{j} = \emptyset \). Furthermore, for each \(\hat{\varGamma }_{j}\) there exists a strong cubature rule, with nodes \(S_{\hat{\varGamma }_{j}} = \{ (\xi _{i}^{(j)},\eta _{i}^{(j)}) \}_{i=1}^{n_{j}}\) and weights \(\{b_{i}^{(j)}\}_{i=1}^{n_{j}}\), that exactly integrates polynomial integrands of degree \(q \ge 2r\), where r is the integer used in property III of Definition 1. Moreover, we assume that the volume nodes result in a degree r Vandermonde matrix, \(\mathsf {V}\), that has linearly independent columns.
Remark 1
The assumption that the reference element is a polygon is reasonable; for example, the most common finite elements are polytopes in computational space. The actual elements in physical space can have curved sides.
Assumption 1 ensures that we can evaluate element boundary fluxes with sufficient accuracy in computational space. For example, the cubature rule for each \(\hat{\varGamma }_{j}\) allows us to write
for all polynomials \({\mathcal {P}}_{k}\) of total degree q or less, where \(q \ge 2r\), and \(n_{\xi _{j}}\) is the \(\xi \) component of the outward pointing unit normal on \(\hat{\varGamma }_{j}\). A similar expression holds for fluxes in the \(\eta \) direction. Note that \(n_{\xi j}\) is constant over \(\hat{\varGamma }_{j}\), due to linearity, so it can be pulled outside the integral.
Our approach to imposing boundary and interface conditions pointwise is to interpolate/extrapolate the solution from the element nodes onto the cubature nodes \(S_{\hat{\varGamma }_{j}} = \{(\xi _{i}^{(j)},\eta _{i}^{(j)}\}_{i=1}^{n_{j}}\) using operators \(\mathsf {R}_{j}\). To decompose \(\mathsf {E}_{\xi }\) and \(\mathsf {E}_{\eta }\) , these interpolation/extrapolation operators must be sufficiently accurate. Specifically,
where \(r \ge p\). The restriction on the volume nodes in Assumption 1 ensures that we can construct the \(\mathsf {R}_{j}\), which we show shortly.
We first prove that we can construct \(\mathsf {E}_{\xi }\) that satisfy the requirements of Definition 1 using the interpolation/extrapolation operators, \(\mathsf {R}\), and the face-cubature rules from Assumption 1.
Theorem 1
Let Assumption 1 hold and let \(S_{\hat{\varOmega }}=\left\{ \left( \xi _{i},\eta _{i}\right) \right\} _{i=1}^{n}\) be a given nodal distribution on the domain \(\hat{\varOmega }\). Then, a matrix \(\mathsf {E}_{\xi }\) that satisfies the requirements of Definition 1 can be constructed as
where \(\mathsf {B}_{j} = {{\mathrm{diag}}}\left( b_{1}^{(j)},b_{2}^{(j)},\ldots ,b_{n_{j}}^{(j)}\right) \) is a diagonal matrix holding the cubature weights for \(\hat{\varGamma }_{j}\). The matrix \(\mathsf {V}_{\hat{\varOmega }}\) is the degree r Vandermonde matrix on the volume nodes, \(\mathsf {V}_{\hat{\varGamma }}\) is the degree p Vandermonde matrix on the nodes of \(\hat{\varGamma }_{j}\), and \(\left( \mathsf {A}\right) ^{\dagger }\) denotes the Moore-Penrose pseudo inverse. Furthermore, \(\mathsf {R}_{j} \in \mathbb {R}^{n_{j} \times n}\) is a degree \(r \ge p\) interpolation/extrapolation operator from the nodes \(S_{\hat{\varOmega }}\) to the nodes of the reference boundary domain, \(S_{\hat{\varGamma }_{j}}\).
Proof
The terms \(\mathsf {R}_{j}^{{{\mathrm {T}}}}\mathsf {B}_{j} \mathsf {R}_{j}\) are symmetric by construction. Moreover, as constructed, the \(\mathsf {R}_{j}\) satisfy the accuracy conditions (1); this can be seen by examining the conditions in matrix form, i.e.
Furthermore, this construction of the \(\mathsf {R}_{j}\) is guaranteed to exist because the columns of \(\mathsf {V}_{\hat{\varOmega }}\) are linearly independent, by assumption. Therefore, we need only show that the accuracy conditions of Property III hold. Since the \(\mathsf {R}_{j}\) are exact for degree \(r \ge p\) polynomials, we have, \(\forall \; k,m \in \{ 1,2,\ldots ,N^{*}_{r} \}\),
where we have used the fact that the unit normal is constant on each \(\hat{\varGamma }\) (see Assumption 1) and the fact that the product \({\mathcal {P}}_{k}{\mathcal {P}}_{m}\) has total degree less than or equal to \(2r\le q\). The result follows by the additive property of integrals.\(\square \)
Next, we prove that we can construct a multi-dimensional SBP operator \(\mathsf {D}_{\xi }\) from a given, sufficiently accurate, strong cubature rule and an \(\mathsf {E}_{\xi }\) matrix that satisfies the requirements of Definition 1.
Theorem 2
Let the diagonal elements of \(\mathsf {H}\) and the nodes \(S_{\hat{\varOmega }}=\left\{ \left( \xi _{i},\eta _{i}\right) \right\} _{i=1}^{n}\) define a degree \(2p-1\) strong cubature rule on the domain \(\hat{\varOmega }\). If the Vandermonde matrix, \(\mathsf {V}\), associated with the nodes \(S_{\hat{\varOmega }}\) has full column rank, and \(\mathsf {E}_{\xi }\in \mathbb {R}^{n\times n}\) is symmetric and satisfies Property III of Definition 1, then there exists at least one degree p SBP operator, \(\mathsf {D}_{\xi }= \mathsf {H}^{-1}(\mathsf {S}_{\xi }+ \frac{1}{2}\mathsf {E}_{\xi })\), based on the given nodes \(S_{\hat{\varOmega }}\) and matrices \(\mathsf {H}\) and \(\mathsf {E}_{\xi }\).
Proof
We must show that, for the given \(\mathsf {H}\) and \(\mathsf {E}_{\xi }\), we can find a skew symmetric \(\mathsf {S}_{\xi }\) that satisfies the accuracy conditions I. The SBP accuracy conditions can be recast as the following set of matrix conditions:
where \(\mathsf {W}\) is a set of linearly independent vectors, of size \(n\times (n-N^{*}_{p})\), such that \(\tilde{\mathsf {V}}\) is invertible, e.g., a basis for the null space of \(\mathsf {V}\). The matrix \(\mathsf {W}_{\xi }\) is of size \(n\times (n-N^{*}_{p})\) and is to be determined. Using (3) and the multi-dimensional SBP definition, we can solve for \(\mathsf {S}_{\xi }\) as
What remains to be shown is that \(\mathsf {S}_{\xi }\) can be constructed to be skew symmetric using \(\mathsf {W}_{\xi }\). Rather than doing so directly, we show that an associated matrix is skew symmetric; left and right multiplying (4) by \(\tilde{\mathsf {V}}^{{{\mathrm {T}}}}\) and \(\tilde{\mathsf {V}}\), respectively, results in
If we can show that \(\tilde{\mathsf {S}}_{\xi }\) is skew symmetric, this will imply skew symmetry for \(\mathsf {S}_{\xi }\).
We first show that the block \(\tilde{\mathsf {S}}_{\xi }(1:N^{*}_{p},1:N^{*}_{p})\) is skew symmetric;
where we have used the compatibility conditions \(\mathsf {V}^{{{\mathrm {T}}}}\mathsf {H}\mathsf {V}_{\xi }+\mathsf {V}_{\xi }^{{{\mathrm {T}}}}\mathsf {H}\mathsf {V}= \mathsf {V}^{{{\mathrm {T}}}}\mathsf {E}_{\xi }\mathsf {V}\) [4, 5, 9, 13].
Next, notice that the entries in the lower-left block \(\tilde{\mathsf {S}}_{\xi }(N^{*}_{p}+1:n,1:N^{*}_{p})\) are fully specified by \(\mathsf {V}\), \(\mathsf {W}\), and \(\mathsf {V}_{\xi }\). To make the rest of \(\tilde{\mathsf {S}}_{\xi }\) skew symmetric, we specify the columns of \(\mathsf {W}_{\xi }\) in order to match the upper-right block to the (negative transposed) lower-left block and a zero lower-right block. In other words, for skew-symmetry we require that
Rearranging we have
which we can solve for \(\mathsf {W}_{\xi }\), because \(\tilde{\mathsf {V}}^{{{\mathrm {T}}}}\mathsf {H}\) is invertible. This particular \(\mathsf {W}_{\xi }\) ensures that \(\tilde{\mathsf {S}}_{\xi }\) is skew symmetric, and, therefore, guarantees that \(\mathsf {S}_{\xi }\) is skew symmetric. \(\square \)
Theorems 1 and 2 imply the following:
Corollary 1
If the hypotheses of Theorems 1 and 2 are met, then there exists at least one degree p SBP operator whose \(\mathsf {E}_{\xi }\) has the decomposition (2).
Remark 2
The implication of Corollary 1 is that \(\mathsf {D}_{\xi }\) exist for which \(\mathsf {E}_{\xi }\) is constructed as the sum of matrices, each of which is associated with a face \(\hat{\varGamma }_{j}\); more importantly, it expresses these constituent matrices in terms of the face cubature points and the \(\mathsf {R}_{j}\) operators, facilitating pointwise imposition of SATs.
4 Linear Variable-Coefficient PDEs
While the ideas presented in this paper can be used to construct SATs for PDEs in various forms, one of our goals is to develop SATs suitable for split forms of nonlinear PDEs. Such split forms can be used to prove nonlinear stability, for example of the Burgers equation, and more generally are related to the entropy stability theory in Refs. [1,2,3, 21, 22]. Moreover, such split-forms can be advantageous in improving robustness [23]. Therefore, in this section, we develop a general framework for constructing SATs to impose boundary and inter-element conditions weakly for multi-dimensional SBP operators in split form. We do so by examining the variable-coefficient linear advection equation in two dimensions in skew-symmetric form. We review the use of the energy method to prove stability for the continuous problem and then apply the same ideas to prove stability of the semi-discrete equations. The goal of this section is to determine a set of conditions that, if satisfied, lead to stable and conservative semi-discrete forms.
4.1 Stability and Conservation of the Variable-Coefficient Linear Advection Equation
Consider the divergence and skew-symmetric forms of the linear advection equation with a spatially varying velocity field, \(\varvec{\lambda }=\left[ \lambda _{x},\lambda _{y}\right] ^{{{\mathrm {T}}}}\):
for all \((x,y)\in \varOmega \) and \(t\ge 0\). The initial and boundary conditions are
respectively, where \(\varGamma \) is subdivided into the inflow boundary,
and the outflow boundary, \(\varGamma ^{+}=\varGamma \backslash \varGamma ^{-}\).
We use the energy method—applying a similar analysis to that in Ref. [24] to our two-dimensional problem—to prove that the problem defined by (6) and (7) is stable; those interested in further details are referred to the texts [25, 26]. Multiplying the divergence form of (6) by \({\mathcal {U}}\) and integrating in space results in
Equation (8) can be expressed in two alternative forms: i) using the Leibniz rule on the left-hand side and the product rule on the right-hand side, or; ii) using the Leibniz rule on the left-hand side and expanding the derivative terms on the right-hand side. Adding these two alternative expressions leads to
Using integration by parts on the first two terms of the right-hand side of (9) leads to
Assuming that the divergence of \(\varvec{\lambda }\) is bounded, that is
we have that
The following inequality results from breaking up the surface integral in (10) into integrals over \(\varGamma ^{+}\) and \(\varGamma ^{-}\), inserting the boundary condition, and making use of the above bound:
We integrate (11) in time and apply the initial condition (see [25] pg. 94), resulting in the estimate
Thus, we see that the problem defined by (6) and (7) is stable in the sense of Hadamard, that is, the solution depends continuously on the data [25].
Remark 3
In the numerical experiments presented later, we consider the special case of (6) where the velocity is divergence free, \(\nabla \cdot \varvec{\lambda }=0\), and the boundary conditions are periodic. Under these assumptions, starting from (9), the energy method results in
which shows that the energy is constant.
In addition to stability, we are interested in constructing schemes that are conservative. To understand the discrete conditions that will be imposed, it is useful to delineate the conditions on the continuous problem. The PDE (6) has an integral form representation given as
where (12) holds for all arbitrary subdomains \(\tilde{\varOmega }\subseteq \varOmega \) with piecewise smooth, orientable boundaries \(\tilde{\varGamma }\). Typically, the strong form (6) is discretized using SBP-SAT schemes; nevertheless, we would like our schemes to mimic (12) discretely on arbitrary domains composed of one or more elements.
4.2 The Generic SBP-SAT Semi-discretization
In this section, we present a generic SBP-SAT semi-discretization of (6), and then determine the general conditions on the SATs necessary to obtain an energy-stable, accurate, and conservative scheme. We focus on SATs for inter-element coupling—weak enforcement of boundary conditions is similar.
The domain \(\varOmega \) is partitioned into E nonoverlapping elements: \(\varOmega = \bigcup _{e = 1}^{E}\varOmega _{e}\). On each element \(\varOmega _{e}\), the PDE (6) is mapped from physical coordinates to computational, or reference, coordinates. For a time-invariant transformation, this results in the following skew-symmetric form:
where
To present and analyze the SATs, we consider the interface between two generic elements, labeled “left” and “right,” having solutions \(\varvec{u}_{L}\) and \(\varvec{u}_{R}\), respectively; see Fig. 1. Suppose the left and right elements have \(\left( N_{\hat{\varGamma }}\right) _{L}\) and \(\left( N_{\hat{\varGamma }}\right) _{R}\) faces, respectively. Then, without loss of generality, we can index the non-shared faces such that the \(\mathsf {E}_{\xi L}\) and \(\mathsf {E}_{\xi R}\) decompositions can be written as (see Theorem 1)
where the terms \(n_{\xi L}\mathsf {R}_{L}^{{{\mathrm {T}}}}\mathsf {B}_{L}\mathsf {R}_{L}\) and \(n_{\xi R}\mathsf {R}_{R}^{{{\mathrm {T}}}}\mathsf {B}_{R}\mathsf {R}_{R}\) correspond to the shared face. Similar expressions hold for \(\mathsf {E}_{\eta L}\) and \(\mathsf {E}_{\eta R}\). In the following, we will focus on the shared face and will drop contributions from the remaining \(\left( N_{\hat{\varGamma }}\right) _{L}-1\) faces on the left and \(\left( N_{\hat{\varGamma }}\right) _{R}-1\) faces on the right, unless otherwise noted.
Illustration of two generic SBP elements and their common interface used for the analysis of SATs. The circles denote the volume nodes at which the solutions \(\varvec{u}_{L}\) and \(\varvec{u}_{R}\) are stored, and the black squares denote cubature nodes for the face; the latter are introduced in Sect. 3
The SBP-SAT semi-discretization of (13) is given by
on the left element and
on the right element. These discretizations introduce several new matrices and vectors. For instance,
are diagonal matrices, where \(n_{L}\) is the number of nodes in the left element. Similar definitions hold for \(\mathsf {\Lambda }_{\eta L}\), \(\mathsf {\Lambda }_{\xi R}\), \(\mathsf {\Lambda }_{\eta R}\), \(\mathsf {U}_{R}\), and \(\mathsf {J}_{R}\). In addition, \(\varvec{1}_{L}\in \mathbb {R}^{n_L}\) and \(\varvec{1}_{R}\in \mathbb {R}^{n_R}\) are constant vectors with entries equal to one.
The matrices \(\mathsf {M}^{\lambda _{\xi }}_{LL}\in \mathbb {R}^{n_L \times n_L}\), \(\mathsf {M}^{\lambda _{\xi }}_{LR}\in \mathbb {R}^{n_L \times n_R}\), \(\mathsf {M}^{\lambda _{\xi }}_{RR}\in \mathbb {R}^{n_R \times n_R}\), and \(\mathsf {M}^{\lambda _{\xi }}_{RL}\in \mathbb {R}^{n_R \times n_L}\) depend on the spatially varying field \(\varvec{\lambda }_{\xi } = [\lambda _{\xi },\lambda _{\eta }]^{{{\mathrm {T}}}}\), in general, and this dependence is reflected in the notation. It is these four SAT matrices that we seek to constrain using stability, accuracy, and conservation conditions.
4.2.1 Stability
We begin by determining the condition imposed by stability on the SAT matrices. The energy method applied to (14) and (15) consists of multiplying the equations by \(\varvec{u}_{L}^{{{\mathrm {T}}}}\mathsf {H}_{L}\) and \(\varvec{u}_{R}^{{{\mathrm {T}}}}\mathsf {H}_{R}\), respectively, and adding the resulting expressions. After cancellation, and using the fact that \(\varvec{u}^{{{\mathrm {T}}}}\mathsf {H}\frac{{{\mathrm {d}}}\mathsf {J}\varvec{u}}{{{\mathrm {d}}}t}=\frac{1}{2}\frac{{{\mathrm {d}}}\varvec{u}^{{{\mathrm {T}}}}\mathsf {H}\mathsf {J}\varvec{u}}{{{\mathrm {d}}}t}\), we find
where
As explained earlier, we have retained only those boundary matrices corresponding to the common face shared by the left and right elements. The terms corresponding to the remaining faces have been dropped to simplify the presentation.
We treat the first terms on the right, i.e. the terms on the second line of (16), in much the same way as we did for the continuous analysis. In particular, assuming the coordinate transformation is differentiable and has a bounded and nonzero Jacobian, we have
where
and we have defined new norms \(\tilde{\mathsf {H}}_{L}= \mathsf {H}_{L}\mathsf {J}_{L}\), \(\tilde{\mathsf {H}}_{R}=\mathsf {H}_{R}\mathsf {J}_{R}\). Using these bounds in (16), and grouping the terms involving the SAT matrices, we obtain
for \(C = \max (\gamma _{L},\gamma _{R})\).
In order to bound the solution in terms of the initial and boundary conditions, the matrix in the right-hand side must be negative semi-definite. This motivates the first condition on the SAT matrices.
Condition 1
(Stability) The matrices \(\mathsf {M}^{\lambda _{\xi }}_{LL}\), \(\mathsf {M}^{\lambda _{\xi }}_{LR}\), \(\mathsf {M}^{\lambda _{\xi }}_{RR}\), and \(\mathsf {M}^{\lambda _{\xi }}_{RL}\) must be such that
is positive semi-definite for all \(\mathsf {\Lambda }_{L}\) and \(\mathsf {\Lambda }_{R}\).
4.2.2 Accuracy
In order to maintain the accuracy of the base scheme, the SATs must add terms that are of the order of the discretization. The required conditions are therefore given by
Condition 2
(Accuracy) The matrices \(\mathsf {M}^{\lambda _{\xi }}_{LL}\), \(\mathsf {M}^{\lambda _{\xi }}_{LR}\), \(\mathsf {M}^{\lambda _{\xi }}_{RR}\), and \(\mathsf {M}^{\lambda _{\xi }}_{RL}\) must be such that
where h is an appropriate measure for the linear dimension of the shared face, and \(\varvec{v}_{L}\) and \(\varvec{v}_{R}\) are the projection, onto the nodes of the left and right domains in physical space, of some continuous function \({\mathcal {V}}(x,y)\), and \(\tilde{p}\ge p\).
We will have more to say about the above accuracy condition in the context of specific examples of SATs in Sect. 5.
4.2.3 Conservation
In order to determine the constraints on the SAT matrices such that the scheme is conservative, we multiply (14) by \(\varvec{1}_{L}^{{{\mathrm {T}}}}\mathsf {H}_{L}\), and (15) by \(\varvec{1}_{R}^{{{\mathrm {T}}}}\mathsf {H}_{R}\) and sum the expressions; this operation is the discrete analogue of integrating the PDE over the volume consisting of both elements, i.e. \(\tilde{\varOmega }\) in (12). Simplifying the result we obtain
For conservation, we want the right-hand side to vanish for arbitrary \(\varvec{u}_{L}\) and \(\varvec{u}_{R}\). Thus, after rearranging the right-hand side, we arrive at the third, and final, condition on the SAT matrices.
Condition 3
(Conservation) The matrices \(\mathsf {M}^{\lambda _{\xi }}_{LL}\), \(\mathsf {M}^{\lambda _{\xi }}_{LR}\), \(\mathsf {M}^{\lambda _{\xi }}_{RR}\), and \(\mathsf {M}^{\lambda _{\xi }}_{RL}\) must be such that
for all \(\varvec{u}_{L}\), \(\varvec{u}_{R}\), \(\mathsf {\Lambda }_{L}\), \(\mathsf {\Lambda }_{R}\).
In the above condition, we have left the conservation conditions coupled and dependent on the solution as this is the typical situation for numerical fluxes used for nonlinear problems. We elaborate further on the conservation condition below.
4.3 Divergence-Free Advection Field
We conclude Sect. 4 by investigating the special case of a divergence-free advection field in the variable-coefficient problem (6), i.e., \(\nabla \cdot \varvec{\lambda } = 0\). This case is of practical interest, because it arises in the incompressible Navier–Stokes and Maxwell’s equations. We also use this case to verify the theory for scalar variable-coefficient equations in Sect. 7.
In the divergence-free case, the skew-symmetric form of the PDE (6) simplifies to
and the SBP-SAT semi-discretization of (18) on the left element becomes
The semi-discretization on the right element is similar.
It is straightforward to show that the stability and accuracy conditions remain the same in the divergence-free case. However, the conservation condition is modified:
Condition 3’
(Divergence-Free Conservation) For the SBP-SAT semi-discretization of (18), the matrices \(\mathsf {M}^{\lambda _{\xi }}_{LL}\), \(\mathsf {M}^{\lambda _{\xi }}_{LR}\), \(\mathsf {M}^{\lambda _{\xi }}_{RR}\), and \(\mathsf {M}^{\lambda _{\xi }}_{RL}\) must be such that
for all \(\varvec{u}_{L}\), \(\varvec{u}_{R}\), \(\mathsf {\Lambda }_{\xi L}\), \(\mathsf {\Lambda }_{\eta L}\), \(\mathsf {\Lambda }_{\xi R}\), and \(\mathsf {\Lambda }_{\eta R}\).
Note that the right-hand side of the divergence-free conservation condition involves \(\mathsf {Q}_{\xi }\) and \(\mathsf {Q}_{\eta }\).
5 Concrete Examples of SATs: Symmetric and Upwind SATs
The SATs presented in Sect. 4 offer significant generality, but they are also somewhat abstract. In this section, we present two concrete examples of SATs—symmetric and upwind—for multidimensional SBP discretizations, and we show that these SATs satisfy Conditions 1–3 for stability, conservation, and accuracy.
The proposed symmetric and upwind SATs require the following assumption that constrains the face-cubature rules and coordinate transformations of adjacent elements.
Assumption 2
The cubature rule of the face shared by adjacent elements has the same number of nodes, \(\nu \), in both reference spaces. In addition, the coordinate transformations in the adjacent elements continuously map their respective face-cubature nodes to the same locations in physical space. For example, in the case of the left and right elements we have
where \(\left( \xi _{L,i},\eta _{L,i}\right) \) and \(\left( \xi _{R,i},\eta _{R,i}\right) \) denote the ith face-cubature points on the left and right elements, respectively. Furthermore, the scaled face-normal vectors, based on the coordinate transformations along the shared face, are equal and opposite at the cubature nodes:
where \(b_{L,i}\) and \(b_{R,i}\) denote the ith face-cubature weights on the left and right elements, respectively.
Remark 4
In principle, the cubature rules for the shared face could use a different number of nodes on the left and right elements, but this case is beyond the scope of the current work.
Remark 5
Equation (20) is satisfied by isoparametric and subparametric coordinate transformations that use the same (possibly scaled) cubature rule on each face.
Let \(\lambda _{n} = \lambda _{\xi } n_{\xi } + \lambda _{\eta } n_{\eta }\) be the advection velocity normal to the shared face. Then, assuming that \(\lambda _{x}\) and \(\lambda _{y}\) are continuous, one can use (20) and the definitions of \(\lambda _{\xi }\) and \(\lambda _{\eta }\) to show that
In other words, the cubature-scaled advection velocity normal to the face is equal in magnitude and opposite in direction at the coincident nodes along the face. We use (21) to define the diagonal \(\nu \times \nu \) matrix
where
\(\mathsf {B}_{\lambda }\) will play a central role in defining the symmetric and upwind SATs below.
Remark 6
Using (21) to define \(\mathsf {B}_{\lambda }\) simplifies the proof of accuracy for the symmetric and upwind SATs, but it is important to emphasize that neither (21) nor (20) are necessary for stability, accuracy, or conservation. Conditions 1–3 will still hold as long as \(\mathsf {B}_{\lambda }\) agrees with (21) on the order of the discretization and satisfies (25) below. This is important, because nonlinear problems may not satisfy (21) due to jumps in \(\lambda _{x}\) and \(\lambda _{y}\) across elements.
5.1 Symmetric SATs
Symmetric SATs are constructed by defining
Based on these matrices, symmetric SATs for (14) and (15) are given by
Theorem 3
The symmetric SATs (24) satisfy the stability and accuracy Conditions 1 and 2. In addition, they satisfy the conservation Condition 3 provided
for all \(\varvec{u}_{L}\), \(\varvec{u}_{R}\), \(\mathsf {\Lambda }_{L}\), \(\mathsf {\Lambda }_{R}\), where \(\varvec{1}_{\hat{\varGamma }}\) is a vector of ones of length \(\nu \).
Proof
It is easy to see that the symmetric SAT matrices (23) lead to a skew-symmetric matrix in Condition 1, which implies that the SATs (24) are stable.
To prove that the symmetric SATs satisfy the accuracy condition, we show that they vanish for all polynomial face-normal fluxes, \(\left( \lambda _{\xi }n_{\xi } + \lambda _{\eta } n_{\eta }\right) {\mathcal {U}}\), of total degree p or less on the reference domain. We do this for the left-element SAT only, since the proof is analogous for the right-element SAT.
Let \(\mathsf {\Lambda }_{L}\varvec{u}_{L}\equiv \varvec{p}_{k,L}\) be the face-normal polynomial flux evaluated at the SBP nodes of the left element (in reference space)—where we consider all \(\mathsf {\Lambda }_{L}\) and \(\varvec{u}_{L}\) that satisfy this definition—and let \(\varvec{p}_{k,\hat{\varGamma }_{L}}\) be the same polynomial evaluated at the face-cubature points on the left element. Then, we consider those states on the right element such that
Note that such states \(\varvec{u}_{R}\) exist provided \(\mathsf {\Lambda }_{\hat{\varGamma },L} \mathsf {R}_{R}\) is full rank. The vector \(\varvec{p}_{k,\hat{\varGamma }_{L}}\) defines the “boundary” flux for which we must show the left SAT vanishes. We have
where we have used \(\mathsf {B}_{\lambda }= \mathsf {B}_{L}\mathsf {\Lambda }_{\hat{\varGamma },L}\) and the fact that \(\mathsf {R}_{L}\) is exact for polynomials of degree r or less, where \(r\ge p\). Thus, the SAT is zero for all polynomial face-normal fluxes of total degree p or less.
Finally, we substitute the \(\mathsf {M}\) matrices into the equation in Condition 3 and find
which is precisely (25). Therefore, if this constraint is satisfied, the symmetric SATs are conservative.\(\square \)
Equation (25) can be viewed as a constraint on the variable coefficient matrices \(\mathsf {\Lambda }_{L}\), \(\mathsf {\Lambda }_{R}\), and \(\mathsf {B}_{\lambda }\). There are a few ways this constraint can be satisfied:
-
For scalar variable-coefficient advection, we can apply a preprocessing step to enforce discrete continuity of the face-normal velocities, that is \(\mathsf {B}_{L}\mathsf {R}_{L}\mathsf {\Lambda }_{L}\varvec{1}_{L}= -\mathsf {B}_{R}\mathsf {R}_{R}\mathsf {\Lambda }_{R}\varvec{1}_{R}= \mathsf {B}_{\lambda }\varvec{1}_{\hat{\varGamma }}\); we use a similar preprocessing step for the divergence-free variable-coefficient advection case presented in the results.
-
For nonlinear systems of PDEs, such as the Euler equations of gas dynamics, the variable coefficients are functions of the solution and the coordinate transformation. In this case, it is more convenient to consider pointwise conditions on a numerical flux Jacobian. To illustrate, in the scalar case we would have
$$\begin{aligned} \bar{\lambda }_{i}\left[ \left( \mathsf {R}_{L}\varvec{u}_{L}\right) _{i} {-} \left( \mathsf {R}_{R}\varvec{u}_{R}\right) _{i}\right] {=} F\left[ \left( \mathsf {R}_{L}\varvec{u}_{L}\right) _{i},\varvec{n}_{i,L}\right] {+} F\left[ \left( \mathsf {R}_{R}\varvec{u}_{R}\right) _{i},\varvec{n}_{i,R}\right] , \quad \forall \; i{=}1,2,\ldots ,\nu , \end{aligned}$$where \(F[u,\varvec{n}]\) is the nonlinear flux in the direction \(\varvec{n}\), and \(\bar{\lambda }_{i}\) is the numerical flux Jacobian at the ith common face node. Note that the pointwise conditions define a secant-like equation for the numerical flux Jacobian, which is a common condition for numerical fluxes used in nonlinear hyperbolic systems.
5.2 Upwind SATs
To construct upwind SATs, we define
Therefore, upwind SATs for (14) and (15) are given by
where \(|{\mathsf {B}_{\lambda }}|\equiv \text {diag} \bigg [ |({{\mathsf {B}}_{\lambda }})_{1,1}|, \ldots ,|({{\mathsf {B}}_{\lambda }})_{v,v}|\bigg ]\).
Theorem 4
The upwind SATs (27) satisfy the stability and accuracy Conditions 1 and 2. In addition, they satisfy the conservation Condition 3 provided
for all \(\varvec{u}_{L}\), \(\varvec{u}_{R}\), \(\mathsf {\Lambda }_{L}\), \(\mathsf {\Lambda }_{R}\), where \(\varvec{1}_{\hat{\varGamma }}\) is a vector of ones of length \(\nu \).
Proof
The matrix in Condition (1) is positive semi-definite using the upwind SAT matrices (26) if
for all nonzeros \(\varvec{u}_{L}\) and \(\varvec{u}_{R}\). This is satisfied, because the matrix \(\left[ {\begin{matrix} |\mathsf {B}_{\lambda }| &{} -|\mathsf {B}_{\lambda }| \\ -|\mathsf {B}_{\lambda }| &{} |\mathsf {B}_{\lambda }| \end{matrix}} \right] \) has non-negative eigenvalues.
The proof that the upwind SATs satisfy the accuracy Condition 2 is similar to the accuracy proof of the symmetric SATs, so we omit it for brevity.
Substituting the upwind SAT matrices (26) into the conservation condition, Condition 3, we obtain the same constraint on the variable coefficients as for the symmetric SATs, namely (25).\(\square \)
5.3 Divergence-Free Advection Field with Upwind SATs
We consider the use of the upwind SATs in the SBP-SAT discretization of the divergence-free variable-coefficient problem, (18), because this is the PDE and the SATs we employ in the results presented below. As remarked previously, the divergence-free case does not alter the stability or accuracy of the discretization. Thus, we need only address the conservation condition.
With upwind SATs, the equation in Condition 4.3 reduces to
where we have made use of \(\mathsf {R}_{L}\varvec{1}_{L}= \mathsf {R}_{R}\varvec{1}_{R}= \varvec{1}_{\hat{\varGamma }}\). Unlike the non-divergence-free situation, the conservation condition (28) is no longer local to the common face.
One way to satisfy conservation in this case is to define the discrete divergence-free condition in such a way that (28) is satisfied. In particular, we require that \(\mathsf {\Lambda }_{\xi }\), \(\mathsf {\Lambda }_{\eta }\) and \(\mathsf {B}_{\lambda ,j}\) satisfy
on all elements, where \(\mathsf {\Lambda }_{j} = n_{\xi j} \mathsf {\Lambda }_{\xi }+ n_{\eta j} \mathsf {\Lambda }_{\eta }\), and \(\mathsf {B}_{\lambda ,j}\) is analogous to \(\mathsf {B}_{\lambda }\) for face j. The left-hand side of (29) is a direct SBP discretization of the divergence-free condition, while the right-hand side is a SAT-like penalty. Our approach to satisfying (29) is described in the Appendix.
If (29) is satisfied, it follows from the properties of SBP operators that
Using identity (30) in (28)—and neglecting SATs on the non-shared faces as usual—we find that the conservation condition is satisfied.
Remark 7
Divergence-free equations also arise in the so-called metric invariants that are needed for “free-stream” preservation; see, for example, [27]. These metric invariants can also be satisfied using the approach described in the Appendix, by setting \(\left[ \lambda _{x},\lambda _{y}\right] ^{{{\mathrm {T}}}}= [1,0]^{{{\mathrm {T}}}}\) and \([0,1]^{{{\mathrm {T}}}}\), in turn.
6 Example Operators on the Triangle
In this section, we describe the construction of multi-dimensional SBP operators on triangular elements in conjunction with the matrices \(\mathsf {R}\) and \(\mathsf {B}\) that define the SATs. We present two families of SBP operators for the triangle. The first family was presented previously in [13]. This family consists of operators with \(p+1\) nodes on each face and will be referred to as the SBP-\(\varGamma \) family. Figure 2 shows the \(p=1\) through \(p=4\) operators from this family. The second family of triangular-element SBP operators has strictly interior nodes. This family will be referred to as the SBP-\(\varOmega \) family, and the first four operators in this familyFootnote 2 are shown in Fig. 3.
The algorithmic steps involved in constructing the operators are listed below. The process is similar to that outlined in [13] for SBP-\(\varGamma \), with a few minor changes that are highlighted.
Nodes of the SBP-\(\varGamma \) family of operators that include \(p+1\) nodes on each face. The open circles denote the SBP operator nodes, while the black squares denote the face cubature points used for the SATs.
Nodes of the SBP-\(\varOmega \) family of operators whose nodes are strictly interior to \(\varOmega \). The open circles denote the SBP operator nodes, while the black squares denote the face cubature points used for the SATs.
-
1.
For a given design accuracy p, a symmetric cubature rule is selected or constructed that is exact for polynomials of total degree \(2p-1\) and has at least \(N^{*}_{p}\) nodes. The nodes for the SBP-\(\varOmega \) family are required to be strictly interior, and the SBP-\(\varGamma \) family is required to have \(p+1\) nodes on each face, including the vertices. For all SBP-\(\varOmega \) operators considered here (\(p=1,\ldots ,4\)), there are exactly \(N^{*}_{p}\) cubature nodes, whereas the SBP-\(\varGamma \) operators generally have more nodes for the same value of p.
-
2.
A Legendre–Gauss quadrature rule with \(p+1\) nodes is used to define \(\mathsf {B}_{\nu }\) on all faces, i.e. the same quadrature rule is used for all three sides, although this is not strictly necessary.
-
3.
Let \(\hat{\varGamma }_{j}\) denote one of the faces of the triangle. Then the volume-to-face interpolation/extrapolation operator for this face is defined by \(\mathsf {R}= \mathsf {V}_{\hat{\varGamma }_{j}} (\mathsf {V}_{\hat{\varOmega }})^{\dagger }\), where \(\mathsf {V}_{\hat{\varGamma }_{j}}\) denotes an orthogonal polynomial basis evaluated at the quadrature nodes of \(\hat{\varGamma }_{j}\), and the superscript \(\dagger \) denotes the Moore-Penrose pseudoinverse. The definition of \(\mathsf {V}_{\hat{\varOmega }}\) depends on whether we are constructing the SBP-\(\varGamma \) or SBP-\(\varOmega \) family. For the latter, \(\mathsf {V}_{\hat{\varOmega }}\) is an orthogonal polynomial basis evaluated at all of the nodes in the volume. In contrast, for the SBP-\(\varGamma \) family, \(\mathsf {V}_{\hat{\varOmega }}\) is the basis evaluated at the \(p+1\) volume nodes that lie on face \(\hat{\varGamma }_{j}\).
Although we have considered only the face \(\hat{\varGamma }_{j}\), symmetry allows the same \(\mathsf {R}\) matrix to be used on all three faces simply by permuting indices of the volume nodes.
-
4.
The boundary operator \(\mathsf {E}_{\xi }\) is constructed from the face cubature \(\mathsf {B}\) and interpolation operator \(\mathsf {R}\) using (2). An analogous equation is used for \(\mathsf {E}_{\eta }\).
-
5.
The skew-symmetric operators \(\mathsf {S}_{\xi }\) and \(\mathsf {S}_{\eta }\) are determined using the accuracy conditions, Property I of Definition 1. For the SBP-\(\varOmega \) operators considered here, the \(\mathsf {S}_{\xi }\) and \(\mathsf {S}_{\eta }\) operators are fully determined by the accuracy conditions; in contrast, the SBP-\(\varGamma \) operators are underdetermined by the accuracy conditions, so the minimum-norm solution is used for those operators.
Table 1 summarizes the accuracy and node-set properties of both the SBP-\(\varOmega \) and SBP-\(\varGamma \) families. Beyond the fact that SBP-\(\varGamma \) includes boundary nodes and SBP-\(\varOmega \) excludes boundary nodes, a few other differences between the families are worth highlighting. First, the SBP-\(\varGamma \) family generally requires more nodes than the SBP-\(\varOmega \) family for the same design accuracy p; this translates into \(\mathsf {D}_{\xi }\) and \(\mathsf {D}_{\eta }\) operators that require more storage and computation, at least for hyperbolic problems. Second, the cubature accuracy is higher for the SBP-\(\varOmega \) family; the \(p=1\) and \(p=2\) operators have cubatures that are exact to degree 2p, rather than \(2p-1\), and the \(p=3\) and \(p=4\) operators have smaller error constants. Finally, the volume-to-face interpolation operators used by the SBP-\(\varGamma \) operators have fewer entries, giving them a computational advantage when it comes to evaluating the SATs. The operators presented in this paper are available as a Matlab\(^{\textregistered }\) function file, SBP_operators.m, on line as an electronic supplement to the paper.
7 Numerical Verifications
In this section, we use numerical experiments to demonstrate the accuracy, conservation, and stability properties of multi-dimensional SBP-SAT discretizations. These experiments are intended to verify the theory developed in Sects. 4 and 5. Before presenting the individual verifications, we first describe their common features.
Each experiment is based on the linear advection PDE with a divergence-free velocity field, Equation (18). In all cases the domain is the unit square, \(\varOmega = [0,1]^2\), and the boundary conditions are periodic: \({\mathcal {U}}(0,y,t) = {\mathcal {U}}(1,y,t)\) and \({\mathcal {U}}(x,0,t) = {\mathcal {U}}(x,1,t)\).
For each SBP element, we introduce a curvilinear coordinate transformation\((x(\xi ,\eta ),y(\xi ,\eta ))\). Under this transformation, it is straightforward to show that (18) is equivalent to
Thus, the transformed velocity field is divergence-free in the space \((\xi ,\eta )\).
The SBP-SAT spatial discretization of the PDE (31) is given by (19) with the SAT matrices defined by the upwind scheme in Sect. 5.2. As explained in Sect. 5.3, the discretization (19) must satisfy (28) to achieve discrete conservation. To this end, we project the analytical advection field onto a discrete field that satisfies (29), the discrete divergence-free equation. The details of this projection can be found in the Appendix.
The SBP-SAT semi-discretizations are advanced in time using the classical 4th-order Runge–Kutta scheme with a sufficiently small time step to ensure that the error is dominated by the spatial discretization. In particular, the time step is one half the maximally stable value permitted by the Courant number for a given SBP element, where the Courant number is defined as
for a time step of \(\Delta t\) and a nominal node spacing of \(h\Delta r\). Here, \(\Delta r\) is the minimum distance between cubature nodes on a right triangle with vertices at (0, 0), (1, 0) and (0, 1). Table 2 lists \(\Delta r\) and the maximally stable Courant numbers for the SBP-\(\varGamma \) and SBP-\(\varOmega \) elements when applied to constant-coefficient advection with \(\lambda _{x}=\lambda _{y}\). The maximum Courant numbers were determined using Golden-section method optimization.
7.1 Constant-Coefficient Advection with a Curvilinear Coordinate Mapping
As our first verification of the SBP-SAT discretizations, we conduct a mesh refinement study and discretize the constant-coefficient advection equation with \(\varvec{\lambda }= \left[ 1,1\right] ^{{{\mathrm {T}}}}\). While this PDE does not have a spatially varying velocity field, we employ a monolithic, i.e. over the whole domain, curvilinear coordinate transformation given by
where \((\xi ,\eta ) \in [0,1]^{2}\). Consequently, the transformed PDE, (31), does have a spatially-varying velocity field even though the physical-space PDE does not.
Let N denote the number of element edges along the \(\xi \) and \(\eta \) coordinates. The vertices of the elements are located at \((\xi _{i},\eta _{j}) = (ih, jh), \; \forall i,j = 0,1,\ldots ,N\), where \(h = 1/N\). For each of the \(N^{2}\) quadrilaterals, two right triangles are generated from the vertices
The nodes associated with these right triangles are then mapped to physical space using the analytical coordinate transformation above.
The sequence of grids for the mesh refinement study is generated using \(N \in \{12, 24, 36, 48, 60, 72\}\). The initial condition for this study is a bell-shaped function centered at \(\left( \frac{1}{2},\frac{1}{2}\right) \) with compact support:
where \(\rho (x,y) \equiv \sqrt{(x-\frac{1}{2})^2 + (y-\frac{1}{2})^2}\). The solution is advanced one time unit, which returns the bell-shaped initial condition to its initial position.
7.1.1 Accuracy
To assess the accuracy of the discrete solutions, we evaluate the SBP-based \(L^{2}\) norm of the difference between the numerical solution and the exact solution. We then normalize by the norm of the exact solution; that is,
where \(\varvec{u}\) is the discrete solution at the final time, and \(\varvec{u}_{e}\) is the exact solution evaluated at the mesh nodes at time \(t=1\). The matrix \(\mathsf {H}_{g}\) is the global SBP-norm assembled from the local element SBP-norm matrices scaled by the appropriate mapping Jacobian determinant on each element, i.e. it is the diagonal mass matrix.
The accuracy results of the mesh refinement study are shown in Fig. 4 for discretizations based on the SBP-\(\varGamma \) and SBP-\(\varOmega \) families of operators. The expected asymptotic convergence rate for the errors is \(\text {O}(h^{p+1})\), and all of the schemes exhibit this convergence rate or higher—the SBP-\(\varOmega \) \(p=1\) scheme exhibits an \(\text {O}(h^{p+1.5})\) rate.
For the same h and p, the two SBP families produce notably different absolute errors. The difference is especially significant for the \(p=1\) and \(p=2\) schemes. On the finest grid, the error in the SBP-\(\varOmega \) \(p=1\) solution is 14.6 times smaller than the corresponding error in the SBP-\(\varGamma \) \(p=1\) solution. The solution errors of the \(p=2\) schemes differ by a factor of 3.46 on the finest grid. We believe this difference is related to the increased accuracy of the SBP cubature rules associated with the SBP-\(\varOmega \) schemes.
Normalized error, measured in the SBP-norm, between the discrete and exact solutions to (31) for different mesh spacing and SBP operators. a SBP-\(\varGamma \) family, b SBP-\(\varOmega \) family
7.1.2 Conservation
The integral of the analytical solution of (31) is constant in time, because the PDE is conservative and the boundary conditions are periodic. Based on the analysis in Sect. 4, the SBP-SAT discretization should mimic this property, and the schemes should be conservative to machine precision.
Discrete conservation is assessed using the following metric:
where \(\varvec{u}_{0}\) is the initial condition evaluated at the nodes and, as before, \(\varvec{u}\) is the discrete solution at \(t=1\). Figure 5 plots this metric for the SBP-\(\varGamma \) and SBP-\(\varOmega \) discretizations on each of the grids in the mesh refinement study. These results provide strong evidence that the SBP-SAT discretizations are conservative. Note that the SBP-\(\varOmega \) \(p=3\) scheme produces a double-precision zero for the conservation metric on the third grid, which cannot be represented on the logarithmic scale.
7.1.3 Stability
The \(L^2\) norm of the analytical solution to (31) is also constant in time; however, in contrast with conservation, the energy of the SBP-SAT discrete solution is only guaranteed to be non-increasing when upwind SATs are used, in general. To assess the various schemes’ ability to conserve energy, we evaluate the energy error for each mesh and operator:
The energy errors are included in Fig. 5 above the conservation metrics. Since the energy error is the signed difference between the initial and final values, it offers some evidence that the energy is non-increasing; stronger evidence is provided below in Sect. 7.3.
Remark 8
The rate of convergence of the energy error is approximately 2p for the SBP-\(\varGamma \) schemes and \(2p+1\) for the SBP-\(\varOmega \) schemes. This is an example of functional superconvergence, which has also been observed and explained for tensor-product SBP schemes [28].
Conservation and energy errors for different mesh spacing and SBP operators. a SBP-\(\varGamma \) family, b SBP-\(\varOmega \) family
7.2 Accuracy on a Non-smooth Grid
The mesh refinement study in Sect. 7.1 used a smooth coordinate transformation over the entire domain, and such meshes are not representative of the grids used in practice. Therefore, in this section, we perform a mesh refinement study on a non-smooth set of grids in order to verify that the rate of convergence produced by the SBP-SAT discretization is not unique to smooth grids.
To construct the non-smooth grids, we use a hierarchical construction with a “kernel” mesh.Footnote 3 The kernel mesh used in this study is the mesh inside the thick-lined triangle in Fig. 6a, and the entire mesh in this figure is the level 1 grid, i.e. the coarsest grid. To obtain the level k mesh from the level \(k-1\) mesh, each triangle is subdivided based on the barycentric coordinates and connectivity of the kernel. The level 2 and level 3 meshes that result from this process are illustrated in Fig. 6b, c, respectively. The nominal element size on the level k grid is \(h=1/3^k\).
Kernel-based grids used in the non-smooth mesh refinement study; the thick gray line in (a) shows the kernel mesh used in the hierarchical construction. a Level 1, b level 2, c level 3
We adopt the same initial condition and velocity field as used in Sect. 7.1. Figure 7 displays the accuracy results of the mesh refinement study and shows that the trends are consistent with the error observed on the smooth mesh; see Fig. 4.
Normalized error, measured in the SBP-norm, between the discrete and exact solutions to (31) for different mesh spacing and SBP operators on the kernel-based grids. a SBP-\(\varGamma \) family, b SBP-\(\varOmega \) family
7.3 Robustness of SBP-SAT Discretizations: Advection in a Confined Domain
For the second numerical experiment, we consider a challenging test of the numerical stability of the SBP-SAT discretizations. The test case is challenging, because the advection field,
is parallel to the boundary of the domain and produces no boundary flux; thus, the solution, and its energy, are confined to the domain. In addition, the nonpolynomial velocity and solution produce aliasing errors that the numerical scheme must handle “gracefully.”
The initial condition is given by \({\mathcal {U}}(x,y,0) = \exp (xy)\), and the solution is advanced for 10 nondimensional time units on a uniform grid with \(N=12\) edges in each direction, i.e. there are \(2N^2 = 288\) elements in total. As before, the time step is set such that the Courant number is one half the value of \(\mathsf {CFL}_{\max }\) listed in Table 2; however, we emphasize that we are only interested in assessing the stability of the methods with this experiment, and the discrete solutions after 10 time units are not accurate for the coarse grids considered. To give some indication of the solution behavior and the time duration, Fig. 8 shows the initial solution and the exact solution after only one unit of time.
Initial condition, left, and exact solution at \(t=1\) for robustness test
Normalized change in energy versus time. Every 100th time-step is marked with a symbol. a SBP-\(\varGamma \) family, b SBP-\(\varOmega \) family, c SBP-\(\varGamma \) with divergence formationn
To demonstrate that the SBP-SAT discretizations are energy stable, Fig. 9 shows the change in normalized energy as the discrete solutions evolve from \(t=0\) to \(t=10\). The normalized change in energy is given by
where \(\varvec{u}(t)\) denotes the discrete solution at time t. As with the conservation metric, we consider a uniform triangulation with \(N=12\) edges in each direction and 288 elements total.
Figure 9a, b show the change in energy for the SBP-\(\varGamma \) and SBP-\(\varOmega \) families applied to the skew-symmetric discretization (19) with upwind SATs. The plots show that the SBP-SAT discretizations have nonincreasing energies, as expected from the analysis in Sects. 4 and 5.2. In contrast, Fig. 9c shows the change in energy for the SBP-\(\varGamma \) family applied to the “divergence” form of the discretization, namely
As the plots show, only the skew-symmetric discretizations have bounded energies.Footnote 4
8 Conclusions
Multi-dimensional SBP operators offer time-stable, high-order, and conservative discretizations on complex domains, but only if boundary conditions and inter-element coupling can be imposed in a suitable manner. To this end, we have proposed a general framework for the development of SATs that lead to accurate, stable, and conservative schemes. We focused on developing a set of SATs that are simple to construct and that allow for the pointwise imposition of boundary conditions and inter-element coupling. This was accomplished by using interpolation/extrapolation operators and face-based cubatures to construct the coupling terms in the SATs. A key insight of this paper is that the \(\mathsf {E}\) matrices and the coupling terms in the SATs can be decomposed in the same way; this insight significantly simplifies the development of this class of SATs.
Using these SATs, we showed how to derive conservative and time-stable discretizations for multi-dimensional SBP operators in the context of the linear advection equation with a spatially varying velocity field. In this context, conservation requires a particular relationship between the interpolated/extrapolated fluxes and the SATs. For a divergence-free problem, we satisfied this conservation condition by projecting the analytical advection field onto a field that satisfies a discrete form of the divergence-free equation. For nonlinear hyperbolic systems of PDEs, numerical flux functions can be used to satisfy the conservation condition.
The SAT methodology was illustrated using SBP operators on triangular elements. Two SBP families were considered: the SBP-\(\varGamma \) family with \(p+1\) nodes on each face and the SBP-\(\varOmega \) family with strictly interior nodes.
The accuracy, conservation, and stability properties of the SBP-SAT discretizations were verified using the linear advection equation with divergence-free velocity fields. Both the SBP-\(\varOmega \) and SBP-\(\varGamma \) schemes were shown to be conservative to machine precision, and both produced non-increasing energy. Comparable convergence rates were found on smooth and nonsmooth meshes. Moreover, for the same operator degree p, the SBP-\(\varOmega \) scheme was found to be more accurate. Finally, we numerically demonstrated that the SBP-SAT discretizations presented result in superconvergent functional estimates.
Notes
The norm matrix can be viewed as a mass matrix.
We do not consider the \(p=0\) operator in this work
Our approach to the kernel grid is motivated by Ref. [2] and we thank Mark Carpenter for informative discussions on this topic
For this problem the discretization of the divergence form leads to increasing energy, but this is not always the case. Indeed, when solving the constant-coefficient, curvilinear-coordinate problem we did not encounter increasing energy.
References
Parsani, M., Carpenter, M.H., Nielsen, E.J.: Entropy stable wall boundary conditions for the three-dimensional compressible Navier–Stokes equations. J. Comput. Phys. 292(C), 88–113 (2015)
Carpenter, M.H., Fisher, T.C., Nielsen, E.J., Frankel, S.H.: Entropy stable spectral collocation schemes for the Navier–Stokes equations: discontinuous interfaces. SIAM J. Sci. Comput. 36(5), B835–B867 (2014)
Fisher, T.C., Carpenter, M.H.: High-order entropy stable finite difference schemes for nonlinear conservation laws: finite domains. J. Comput. Phys. 252(1), 518–557 (2013)
Kreiss, H.-O., Scherer, G.: Finite element and finite difference methods for hyperbolic partial differential equations. In: de Boor, C. (ed.) Mathematical Aspects of Finite Elements in Partial Differential Equations, pp. 195–212. Academic Press, New York (1974)
Strand, B.: Summation by parts for finite difference approximations for d/dx. J. Comput. Phys. 110(1), 47–67 (1994)
Del Rey Fernández, D.C., Hicken, J.E., Zingg, D.W.: Review of summation-by-parts operators with simultaneous approximation terms for the numerical solution of partial differential equations. Comput. Fluids 95(22), 171–196 (2014)
Svärd, M., Nordström, J.: Review of summation-by-parts schemes for initial-boundary-value-problems. J. Comput. Phys. 268(1), 17–38 (2014)
Del Rey Fernández, D.C., Zingg, D.W.: Generalized summation-by-parts operators for the second derivative with a variable coefficient. SIAM J. Sci. Comput. 37(6), A2840–A2864 (2015)
Del Rey Fernández, D.C., Boom, P.D., Zingg, D.W.: A generalized framework for nodal first derivative summation-by-parts operators. J. Comput. Phys. 266(1), 214–239 (2014)
Gassner, G.J.: A skew-symmetric discontinuous Galerkin spectral element discretization and its relation to SBP-SAT finite difference methods. SIAM J. Sci. Comput. 35(3), A1233–A1253 (2013)
Carpenter, M.H., Gottlieb, D.: Spectral methods on arbitrary grids. J. Comput. Phys. 129(1), 74–86 (1996)
Nordström, J., Forsberg, K., Adamsson, C., Eliasson, P.: Finite volume methods, unstructured meshes and strict stability for hyperbolic problems. Appl. Numer. Math. 45, 453–473 (2003)
Hicken, J.E., Del Rey Fernández, D.C., Zingg, D.W.: Multi-dimensional summation-by-parts operators: general theory and application to simplex elements. SIAM J. Sci. Comput. 38(4), A1935–A1958 (2016)
Hicken, J.E., Del Rey Fernández, D.C., Zingg, D.W.: Opportunities for efficient high-order methods based on the summation-by-parts property. In: 22nd AIAA Computational Fluid Dynamics Conference, No. AIAA–2015–3198, Dallas, Texas (2015)
Cools, R.: Monomial cubature rules since “Stroud”: a compilation—part 2. J. Comput. Appl. Math. 112(1–2), 21–27 (1999)
Carpenter, M.H., Gottlieb, D., Abarbanel, S.: Time-stable boundary conditions for finite-difference schemes solving hyperbolic systems: methodology and application to high-order compact schemes. J. Comput. Phys. 111(2), 220–236 (1994)
Carpenter, M.H., Nordström, J., Gottlieb, D.: A stable and conservative interface treatment of arbitrary spatial accuracy. J. Comput. Phys. 148(2), 341–365 (1999)
Nordström, J., Carpenter, M.H.: Boundary and interface conditions for high-order finite-difference methods applied to the Euler and Navier–Stokes equations. J. Comput. Phys. 148(2), 621–645 (1999)
Nordström, J., Carpenter, M.H.: High-order finite-difference methods, multidimensional linear problems, and curvilinear coordinates. J. Comput. Phys. 173(1), 149–174 (2001)
Hesthaven, J.S., Warburton, T.: Nodal Discontinuous Galerkin Methods: Algorithms, Analysis, and Applications. Springer, New York (2008)
Harten, A.: On the symmetric form of systems of conservation laws with entropy. J. Comput. Phys. 49(1), 151–164 (1983)
Hughes, T.J.R., Franca, L.P., Mallet, M.: A new finite element formulation for computational fluid dynamics: I. Symmetric forms of the compressible Navier–Stokes equations and the second law of thermodymaics. Comput. Methods Appl. Mech. Eng. 54(2), 223–234 (1986)
Gassner, G.J., Winters, A.R., Kopriva, D.A.: Split form nodal discontinuous Galerkin schemes with summation-by-parts property for the compressible Euler equations, pp. 28–50. arXiv:1604.06618v2 [math.NA] (2016)
Kopriva, D.A., Gassner, G.J.: An energy stable discontinuous Galerkin spectral element discretization for variable coefficient advection problems. SIAM J. Sci. Comput. 4(36), A2076–A2099 (2014)
Gustafsson, B., Kreiss, H.-O., Oliger, J.: Time-Dependent Problems and Difference Methods. Pure and Applied Mathematics, 2nd edn. Wiley, New York (2013)
Kreiss, H.-O., Lorenz, J.: Initial-Boundary Value Problems and the Navier–Stokes Equations, Vol. 47 of Classics in Applied Mathematics. SIAM, New Delhi (2004)
Thomas, P.D., Lombard, C.K.: Geometric conservation law and its application to flow computations on moving grids. AIAA J. 17(10), 1030–1037 (1979)
Hicken, J.E., Zingg, D.W.: Superconvergent functional estimates from summation-by-parts finite-difference discretizations. SIAM J. Sci. Comput. 33(2), 893–922 (2011)
Author information
Authors and Affiliations
Corresponding author
Additional information
Some of the material presented in this article has also appeared in: Hicken J. E., Del Rey Fernández D. C and Zingg D. W. Simultaneous Approximation Terms for Multi-dimensional Summation-by-parts Operators, AIAA Aviation Conference (2016).
Electronic supplementary material
Below is the link to the electronic supplementary material.
Appendix: Satisfaction of the Discrete Divergence-Free Equation
Appendix: Satisfaction of the Discrete Divergence-Free Equation
In general, the analytical velocity, which we will denote here as \(\hat{\varvec{\lambda }}_{\xi }\), does not satisfy the discretized divergence-free condition, (29). Therefore, we seek a discrete vector field that satisfies the discrete divergence-free condition and is as close as possible, in some norm, to the analytical field. This appendix describes how find such a discrete vector field.
First we solve for the face-normal velocities, \((\lambda _n)_{i} = \left( \lambda _{\xi } n_{\xi } + \lambda _{\eta } n_{\eta }\right) _{i}\), that appear in the elements of the \(\mathsf {B}_{\lambda }\) matrices. A constraint on the \((\lambda _n)_{i}\) for each element is obtained by substituting \(\varvec{v} = \varvec{1}\) into the identity (30):
where the last equality follows from \(\mathsf {Q}_{\xi }\varvec{1} = \mathsf {Q}_{\eta }\varvec{1} = \varvec{0}\). This constraint is simply a discretization of \(\int _{\hat{\varGamma }} \varvec{\lambda }\cdot \varvec{n}\, {{\mathrm {d}}}\hat{\varGamma }= 0\) on each element. There are fewer elements than face-normal velocities, so we solve a quadratic optimization problem that minimizes the Cartesian norm between the discrete and analytical values at the face nodes, \((\lambda _{n}^{(j)})_{i}\) and \((\hat{\lambda }_{n}^{(j)})_{i}\), respectively, subject to the above constraint.
Once the \(\mathsf {B}_{\lambda }\) matrices are determined, we solve for the diagonal matrices \(\Lambda _{\xi }\) and \(\Lambda _{\eta }\). We follow a procedure analogous to the one used for \(\mathsf {B}_{\lambda }\); in this case we minimize the Cartesian norm between the discrete and analytical values at the SBP nodes and (29) becomes the constraint. The optimization problems on each element are decoupled.
For the cases considered here, we verified that the \(L^2\) error in the discrete velocity field is at least an order of magnitude smaller than the \(L^2\) error in the scalar field \({\mathcal {U}}\). Moreover, the error in the velocity field decreases with h, the average mesh spacing, at a faster rate than the error in \(\varvec{u}\), and the error in the velocity field has an insignificant impact on the solution error.
Rights and permissions
About this article
Cite this article
Del Rey Fernández, D.C., Hicken, J.E. & Zingg, D.W. Simultaneous Approximation Terms for Multi-dimensional Summation-by-Parts Operators. J Sci Comput 75, 83–110 (2018). https://doi.org/10.1007/s10915-017-0523-7
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10915-017-0523-7