Review of summation-by-parts operators with simultaneous approximation terms for the numerical solution of partial differential equations

Highlights

• History of SBP operators and SATs, with a focus on the Navier–Stokes (NS) equations.

• Methodology for deriving SBP operators for 1st and 2nd derivatives.

• Implementation of SBP-SATs for the numerical solution of the NS equations.

• Review of recent developments, including functional superconvergence.

Abstract

Summation-by-parts (SBP) operators have a number of properties that make them an attractive option for higher-order spatial discretizations of partial differential equations. In particular, they enable the derivation of higher-order boundary closures leading to provable time stability. When implemented on multi-block structured meshes in conjunction with simultaneous approximation terms (SATs)—penalty terms that impose boundary and interblock-coupling conditions in a weak sense—they offer additional properties of value, even for second-order accurate schemes and steady problems. For example, they involve low communication overhead for efficient parallel algorithms and relax the continuity requirements of both the mesh and the solution across block interfaces. This paper provides a brief history of seminal contributions to, and applications of, SBP-SAT methods followed by a description of their properties and a methodology for deriving SBP operators for first derivatives and second derivatives with variable coefficients. A procedure for deriving SATs is also provided. Practical aspects are discussed, including artificial dissipation, transformation to curvilinear coordinates, and application to the Navier–Stokes equations. Recent developments are reviewed, including a variational interpretation, the connection to quadrature rules, functional superconvergence, error estimates, and dual consistency. Finally, the connection to quadrature rules is exploited to provide a generalization of the SBP concept to a broader class of operators, enabling a unification and rigorous development of SATs for operators such as nodal-based pseudo-spectral and some discontinuous Galerkin operators.

Introduction

In the numerical solution of partial differential equations (PDEs), the potential improvements in efficiency from higher-order methods have long been recognized [1], [2]. Their advantage increases as the error tolerance of a computation becomes more stringent. In computational fluid dynamics, higher-order methods are often applied to time-dependent problems requiring high resolution. Despite evidence that they can also be more efficient than second-order methods for steady turbulent flows represented by the Reynolds-averaged Navier–Stokes equations [3], their use in this context is less common. This arises in part because the numerical accuracy requirement in such problems is often less stringent due to the fact that there can be a significant physical-model error associated with, for example, the turbulence model. A second issue impacting the effectiveness of higher-order methods when applied to practical problems is that such problems are often characterized by singularities and discontinuities of various types, such as shock waves. This can impair the ability of the higher-order method to achieve its design order, as the theory typically assumes a sufficiently smooth solution. Further study is needed to determine how this can be addressed. Nevertheless, there is growing interest in solving practical aerodynamic problems to a high degree of accuracy, and higher-order methods are being increasingly applied to such problems [4], [5].

As a result of several advantageous properties, summation-by-parts (SBP) finite-difference operators with simultaneous approximation terms (SATs) for enforcing boundary and mesh interface conditions have emerged as one of several viable higher-order spatial discretizations for PDEs, for example the Navier–Stokes (NS) equations governing the flow of a continuum fluid. The use of finite-difference methods typically involves the use of multi-block structured meshes as opposed to fully unstructured meshes, which can be easier to generate about complex geometries. Nevertheless, for geometries where a multi-block structured mesh can be readily generated, including many complex geometries of practical interest [6], finite-difference discretizations can be the most efficient option [7]. In particular, higher-order finite-difference methods can be very efficiently implemented on structured meshes [8], [3]. Moreover, the SBP-SAT approach on multi-block meshes has proven to be advantageous even in a second-order implementation. For example, Hicken and Zingg [9] and Osusky and Zingg [6] have developed efficient flow solution methodologies combining the SBP-SAT approach with a Newton–Krylov–Schur parallel implicit algorithm for the Euler and Reynolds-averaged Navier–Stokes equations, respectively, that have been applied to various complex geometries, including full aircraft configurations [10].

We begin this review with an introduction to the basic concepts underpinning SBP-SAT schemes in the context of the linear convection equation with a unit wave speed in one dimension discretized on a uniform mesh. This is intended for the reader who is new to SBP-SAT schemes. The reader who is already familiar with the basic concepts can skip past (26).

With a positive unit wave speed, the linear advection equation is given by

$$\frac{\partial \mathcal{U}}{\partial t}+\frac{\partial \mathcal{U}}{\partial x}=0$$

on the domain $x_L⩽x⩽x_R$ with the boundary condition $\mathcal{U}(0\text{,}t)={\mathcal{U}}_L(t)$.

Time stability of the partial differential equation with ${\mathcal{U}}_L=0$ is readily shown. The time rate of change of the energy in the domain is

$$\begin{array}{cc}\hfill \frac{\mathrm{d}}{\mathrm{d}t}{\int }_{x_L}^{x_R}{\mathcal{U}}^2\mathrm{d}x& ={\int }_{x_L}^{x_R}\frac{\partial {\mathcal{U}}^2}{\partial t}\mathrm{d}x\hfill \\ \hfill & ={\int }_{x_L}^{x_R}2\mathcal{U}\frac{\partial \mathcal{U}}{\partial t}\mathrm{d}x\hfill \\ \hfill & =-2{\int }_{x_L}^{x_R}\mathcal{U}\frac{\partial \mathcal{U}}{\partial x}\mathrm{d}x\text{.}\hfill \end{array}$$

Applying integration by parts we find

$$\frac{\mathrm{d}}{\mathrm{d}t}{\int }_{x_L}^{x_R}{\mathcal{U}}^2\mathrm{d}x=-\left({\mathcal{U}}_R^2-{\mathcal{U}}_L^2\right)\text{,}$$

which is nonpositive when ${\mathcal{U}}_L=0$.

Next consider a discretization in space on a mesh with $N+1$ equally spaced nodes indexed from 0 to N such that $\mathbf{u}={[u_0\text{,}{u}_1\text{,}\dots \text{,}{u}_N]}^T$. We define an SBP finite-difference operator for a first derivative ${\mathsf{D}}_1$ as

$${\mathsf{HD}}_1\mathbf{u}=\mathsf{Q}\mathbf{u}\text{,}\mathrm{i}.\mathrm{e}.\frac{\partial \mathcal{U}}{\partial x}\approx {\mathsf{H}}^{-1}\mathsf{Q}\mathbf{u}\text{,}$$

where $\mathsf{H}$ is a diagonal positive definite matrix that defines an inner product, norm, and quadrature by

$$\begin{array}{cc}\hfill & {(\mathbf{u}\text{,}\mathbf{v})}_{\mathsf{H}}={\mathbf{u}}^T\mathsf{H}\mathbf{v}\text{,}\Vert \mathbf{u}{\Vert }_{\mathsf{H}}^2={\mathbf{u}}^T\mathsf{H}\mathbf{u}\text{,}\hfill \\ \hfill & {\int }_{x_L}^{x_R}\mathcal{UV}\mathrm{d}x\approx {\mathbf{u}}^T\mathsf{H}\mathbf{v}\text{,}\hfill \end{array}$$

and

$$\mathsf{Q}+{\mathsf{Q}}^T={\mathsf{E}}_N-{\mathsf{E}}_0=\mathrm{diag}[0\text{,}\dots \text{,}0\text{,}1]-\mathrm{diag}[1\text{,}0\text{,}\dots \text{,}0]=\left[\begin{array}{ccccc}\hfill -1\hfill & \hfill \hfill & \hfill \hfill & \hfill \hfill & \hfill \hfill \\ \hfill \hfill & \hfill 0\hfill & \hfill \hfill & \hfill \hfill & \hfill \hfill \\ \hfill \hfill & \hfill \hfill & \hfill \ddots \hfill & \hfill \hfill & \hfill \hfill \\ \hfill \hfill & \hfill \hfill & \hfill \hfill & \hfill 0\hfill & \hfill \hfill \\ \hfill \hfill & \hfill \hfill & \hfill \hfill & \hfill \hfill & \hfill 1\hfill \end{array}\right]\text{.}$$

We will see later that the restriction to a diagonal $\mathsf{H}$ is not necessary, but it simplifies our initial introduction to SBP schemes.

With these definitions the discrete SBP operator mimics the integration by parts result obtained in the continuous case:

$${(\mathbf{u}\text{,}{\mathsf{H}}^{-1}\mathsf{Q}\mathbf{v})}_{\mathsf{H}}={\mathbf{u}}^T({\mathsf{E}}_N-{\mathsf{E}}_0)\mathbf{v}-{({\mathsf{H}}^{-1}\mathsf{Q}\mathbf{u}\text{,}\mathbf{v})}_{\mathsf{H}}\text{.}$$

This enables the following energy estimate (ignoring the boundary condition for now):

$$\frac{\mathrm{d}{\mathbf{u}}^T\mathsf{H}\mathbf{u}}{\mathrm{d}t}={\mathbf{u}}^T\mathsf{H}\frac{\mathrm{d}\mathbf{u}}{\mathrm{d}t}+\frac{\mathrm{d}{\mathbf{u}}^T}{\mathrm{d}t}\mathsf{H}\mathbf{u}={\mathbf{u}}^T\mathsf{H}(-{\mathsf{H}}^{-1}\mathsf{Q})\mathbf{u}+{\mathbf{u}}^T(-{\mathsf{Q}}^T{\mathsf{H}}^{-1})\mathsf{H}\mathbf{u}=-{\mathbf{u}}^T\mathsf{Q}\mathbf{u}-{\mathbf{u}}^T{\mathsf{Q}}^T\mathbf{u}=-{\mathbf{u}}^T(\mathsf{Q}+{\mathsf{Q}}^T)\mathbf{u}=-{\mathbf{u}}^T({\mathsf{E}}_N-{\mathsf{E}}_0)\mathbf{u}=-\left(u_N^2-u_0^2\right)\text{,}$$

which mimics the continuous case (3).

Before moving on to SATs, we consider an example of an SBP operator. The parameter p defines the scheme’s order of accuracy. For a first derivative, with diagonal $\mathsf{H}$, the scheme has interior order 2p, boundary order p, and global order $p+1$. For example, with $p=2$ we have interior order 4 and global order 3. With $p=2$ the matrices $\mathsf{H}$ and $\mathsf{Q}$ have the following form:

$$\mathsf{H}=\mathrm{\Delta }x\left[\begin{array}{cccccc}\hfill h_{11}\hfill & \hfill \hfill & \hfill \hfill & \hfill \hfill & \hfill \hfill & \hfill \hfill \\ \hfill \hfill & \hfill h_{22}\hfill & \hfill \hfill & \hfill \hfill & \hfill \hfill & \hfill \hfill \\ \hfill \hfill & \hfill \hfill & \hfill h_{33}\hfill & \hfill \hfill & \hfill \hfill & \hfill \hfill \\ \hfill \hfill & \hfill \hfill & \hfill \hfill & \hfill h_{44}\hfill & \hfill \hfill & \hfill \hfill \\ \hfill \hfill & \hfill \hfill & \hfill \hfill & \hfill \hfill & \hfill 1\hfill & \hfill \hfill \\ \hfill \hfill & \hfill \hfill & \hfill \hfill & \hfill \hfill & \hfill \hfill & \hfill \ddots \hfill \end{array}\right]\text{,}$$

$$\mathsf{Q}=\left[\begin{array}{cccc}\hfill -\frac{1}{2}\hfill & \hfill {\theta }_{12}\hfill & \hfill {\theta }_{13}\hfill & \hfill {\theta }_{14}\hfill \\ \hfill -{\theta }_{12}\hfill & \hfill 0\hfill & \hfill {\theta }_{23}\hfill & \hfill {\theta }_{24}\hfill \\ \hfill -{\theta }_{13}\hfill & \hfill -{\theta }_{23}\hfill & \hfill 0\hfill & \hfill {\theta }_{34}\hfill & \hfill -\frac{1}{12}\hfill \\ \hfill -{\theta }_{14}\hfill & \hfill -{\theta }_{24}\hfill & \hfill -{\theta }_{34}\hfill & \hfill 0\hfill & \hfill \frac{8}{12}\hfill & \hfill -\frac{1}{12}\hfill \\ \hfill 0\hfill & \hfill 0\hfill & \hfill \frac{1}{12}\hfill & \hfill -\frac{8}{12}\hfill & \hfill 0\hfill & \hfill \frac{8}{12}\hfill & \hfill -\frac{1}{12}\hfill \\ \hfill \hfill & \hfill \hfill & \hfill \hfill & \hfill \ddots \hfill & \hfill \ddots \hfill & \hfill \ddots \hfill & \hfill \ddots \hfill & \hfill \ddots \hfill \end{array}\right]\text{,}$$

where both matrices have corresponding entries in the lower right-hand corner. In the interior of the domain, the operator is the standard fourth-order centered difference operator. The various unspecified entries in $\mathsf{H}$ and $\mathsf{Q}$ must be determined to satisfy the order of accuracy requirements; this is further discussed in Section 4. The SBP property is obtained by construction (the entries in $\mathsf{H}$ must be positive).

SATs are penalty terms that impose boundary conditions in a weak sense. For our simple example, we have

$$\mathsf{H}\frac{\mathrm{d}\mathbf{u}}{\mathrm{d}t}=-\mathsf{Q}\mathbf{u}-\sigma (u_0-{\mathcal{U}}_L){\mathbf{e}}_0\text{,}$$

where $\sigma$ is a parameter, and ${\mathbf{e}}_0={[1\text{,}0\text{,}\dots \text{,}0]}^T$. With the SAT term included we get the following energy estimate (with ${\mathcal{U}}_L=0$):

$$\frac{\mathrm{d}{\mathbf{u}}^T\mathsf{H}\mathbf{u}}{\mathrm{d}t}={\mathbf{u}}^T\mathsf{H}\frac{\mathrm{d}\mathbf{u}}{\mathrm{d}t}+\frac{\mathrm{d}{\mathbf{u}}^T}{\mathrm{d}t}\mathsf{H}\mathbf{u}=-{\mathbf{u}}^T(\mathsf{Q}+{\mathsf{Q}}^T)\mathbf{u}-2{\mathbf{u}}^T\sigma u_0{\mathbf{e}}_0=-{\mathbf{u}}^T({\mathsf{E}}_N-{\mathsf{E}}_0)\mathbf{u}-2{\mathbf{u}}^T\sigma u_0{\mathbf{e}}_0=-u_N^2+u_0^2-2\sigma u_0^2\text{,}$$

which is nonnegative for $\sigma ⩾1/2$.

In order to demonstrate that an SBP operator is conservative, we must show that Gauss’s theorem

$${\displaystyle \underset{S}{\oint }}\mathbf{n}·\mathbf{F}\mathrm{d}S={\int }_V\nabla ·\mathbf{F}\mathrm{d}V\text{,}$$

is satisfied discretely. For the one-dimensional linear advection equation we require:

$$\mathcal{U}(x_R)-\mathcal{U}(x_L)={\int }_{x_L}^{x_R}\frac{\partial \mathcal{U}}{\partial x}\mathrm{d}x\text{.}$$

The discrete expression for the integral on the right-hand side is:

$${\mathbf{1}}^T{\mathsf{HD}}_1\mathbf{u}={\mathbf{1}}^T{\mathsf{HH}}^{-1}\mathsf{Q}\mathbf{u}={\mathbf{1}}^T\mathsf{Q}\mathbf{u}={\mathbf{1}}^T[({\mathsf{E}}_N-{\mathsf{E}}_0)-{\mathsf{Q}}^T]\mathbf{u}={\mathbf{1}}^T[({\mathsf{E}}_N-{\mathsf{E}}_0)]\mathbf{u}=u_N-u_0\text{,}$$

where we have used ${\mathbf{1}}^T{\mathsf{Q}}^T={({\mathsf{D}}_1\mathbf{1})}^T\mathsf{H}=\mathbf{0}$. Adding in the SAT penalty term gives:

$${\mathbf{1}}^T\mathsf{H}\frac{\mathrm{d}\mathbf{u}}{\mathrm{d}t}=-{\mathbf{1}}^T\mathsf{Q}\mathbf{u}-\sigma (u_0-{\mathcal{U}}_L)$$

$$=-(u_N-u_0)-\sigma (u_0-{\mathcal{U}}_L)$$

$$=-(u_N-{\mathcal{U}}_L)\text{,}\mathrm{if}\sigma =1\text{.}$$

The choice $\sigma =1$ therefore satisfies both conservation and time stability.

The same approach to the selection of the penalty parameter enables conservation at block interfaces even though the solution is multi-valued there as a result of the weak enforcement of the interface condition. Abutting or patched multi-block grids are often used for geometries where a single simply-connected structured grid cannot be generated. As a simple example, consider a block interface in the middle of the above domain. Discretizing in space with $N_L$ cells to the left of the interface and $N_R$ cells to the right of the interface, we have two solution vectors as follows:

$$\begin{array}{cc}\hfill & {\mathbf{u}}_L={\left[u_0^L\text{,}{u}_1^L\text{,}\dots \text{,}{u}_{N_L}^L\right]}^T\text{,}\hfill \\ \hfill & {\mathbf{u}}_R={\left[u_0^R\text{,}{u}_1^R\text{,}\dots \text{,}{u}_{N_R}^R\right]}^T\text{.}\hfill \end{array}$$

Note that the last node in the left block is coincident with the first node of the right block, yet $u_{N_L}^L\ne u_0^R$, i.e. the numerical solution is multi-valued at the interface. Introducing a SAT term into the semi-discrete form for the right domain, we have:

$$\begin{array}{cc}\hfill & {\mathsf{H}}_L\frac{\mathrm{d}{\mathbf{u}}_L}{\mathrm{d}t}=-{\mathsf{Q}}_L{\mathbf{u}}_L-{\sigma }_L\left(u_0^L-{\mathcal{U}}_L\right){\mathbf{e}}_0\text{,}\hfill \\ \hfill & {\mathsf{H}}_R\frac{\mathrm{d}{\mathbf{u}}_R}{\mathrm{d}t}=-{\mathsf{Q}}_R{\mathbf{u}}_R-{\sigma }_R\left(u_0^R-u_{N_L}^L\right){\mathbf{e}}_0\text{.}\hfill \end{array}$$

Note that we have taken advantage of the fact that our wave speed is positive; hence a SAT is needed only at the left side of each block. Additional SATs are required if the sign of the wave speed is not known or for a system where waves propagate in both directions. The penalty parameters ${\sigma }_L$ and ${\sigma }_R$ must be selected to maintain both stability and conservation.

Considering conservation first, we see immediately from (15) that the choice ${\sigma }_L=1$ ensures that

$${\mathbf{1}}^T{\mathsf{H}}_L\frac{\mathrm{d}{\mathbf{u}}_L}{\mathrm{d}t}=-\left(u_{N_L}^L-{\mathcal{U}}_L\right)\text{.}$$

For the right-hand block we have

$${\mathbf{1}}^T{\mathsf{H}}_R\frac{\mathrm{d}{\mathbf{u}}_R}{\mathrm{d}t}=-{\mathbf{1}}^T{\mathsf{Q}}_R{\mathbf{u}}_R-{\sigma }_R\left(u_0^R-u_{N_L}^L\right)=-\left(u_{N_R}^R-u_0^R\right)-{\sigma }_R\left(u_0^R-u_{N_L}^L\right)=-\left(u_{N_R}^R-u_{N_L}^L\right)\text{,}\mathrm{if}{\sigma }_R=1\text{.}$$

Hence with ${\sigma }_L={\sigma }_R=1$ we obtain

$$\frac{\mathrm{d}}{\mathrm{d}t}\left[{\mathbf{1}}^T{\mathsf{H}}_L{\mathbf{u}}_L+{\mathbf{1}}^T{\mathsf{H}}_R{\mathbf{u}}_R\right]=-\left(u_{N_R}^R-{\mathcal{U}}_L\right)\text{,}$$

and the block interface is conservative.

For time stability we must have

$$\frac{\mathrm{d}}{\mathrm{d}t}\left({({\mathbf{u}}_L)}^T{\mathsf{H}}_L{\mathbf{u}}_L+{({\mathbf{u}}_R)}^T{\mathsf{H}}_R{\mathbf{u}}_R\right)⩽0\text{,}$$

when ${\mathcal{U}}_L=0$. For the left-hand block we have from (11) with ${\sigma }_L=1$:

$$\frac{\mathrm{d}{({\mathbf{u}}_L)}^T{\mathsf{H}}_L{\mathbf{u}}_L}{\mathrm{d}t}=-{\left(u_{N_L}^L\right)}^2-{\left(u_0^L\right)}^2\text{.}$$

For the right-hand block, we obtain with ${\sigma }_R=1$:

$$\frac{\mathrm{d}{({\mathbf{u}}_R)}^T{\mathsf{H}}_R{\mathbf{u}}_R}{\mathrm{d}t}=-{\left(u_{N_R}^R\right)}^2-{\left(u_0^R\right)}^2+2u_0^R{u}_{N_L}^L\text{.}$$

Summing (24), (25) we find

$$\frac{\mathrm{d}}{\mathrm{d}t}\left({({\mathbf{u}}_L)}^T{\mathsf{H}}_L{\mathbf{u}}_L+{({\mathbf{u}}_R)}^T{\mathsf{H}}_R{\mathbf{u}}_R\right)=-{\left(u_0^L\right)}^2-{\left(u_{N_R}^R\right)}^2-{\left(u_{N_L}^L\right)}^2-{\left(u_0^R\right)}^2+2u_0^R{u}_{N_L}^L=-{\left(u_0^L\right)}^2-{\left(u_{N_R}^R\right)}^2-{\left(u_{N_L}^L-u_0^R\right)}^2\text{,}$$

which is nonpositive, as required for time stability.

With this background we can now introduce some of the useful properties of the SBP-SAT approach. To date much of the use of SBP-SAT schemes has been in a finite-difference context, generally requiring rectilinear grids or curvilinear grids with a coordinate transformation. However, many of the associated concepts apply more generally, as will be discussed below. One of the main purposes of the SBP-SAT formulation is to facilitate the derivation of higher-order spatial discretizations that are provably time stable based on the energy method. Development of numerical boundary schemes for higher-order methods that are provably stable and of a suitable order of accuracy can be a challenging task; applying the energy method provides a relatively straightforward approach. Another useful property of SBP-SAT schemes is in the handling of interfaces between blocks. The approximation of the derivative in each of two neighboring blocks is completely determined by the solution in that block. This means that the amount of information passed between blocks is minimized, which is helpful for parallel algorithms, and independent of the order of the scheme. Moreover, neither the grid nor the solution need be continuous across the interface. This is particularly useful for problems where there can be different material properties on either side of the interface, such as conjugate heat transfer or electromagnetics. However, this can be advantageous in CFD as well, by relaxing the requirement of grid smoothness across the block interface. Furthermore, a block interface can intentionally be placed at a known discontinuity such as a geometric discontinuity.

The objective of this paper is to provide the reader with a thorough understanding of the SBP-SAT methodology, with a particular emphasis on the derivation of operators; several examples of operators are given. For a detailed review of theoretical aspects of SBP schemes the reader is referred to the excellent paper by Svärd and Nordström [11]. A brief history of key contributions is provided in the next section along with a description of some applications. This is followed by a detailed treatment of SBP operators for first derivatives and second derivatives with variable coefficients, including a methodology for deriving them. Simultaneous approximation terms are then described in the context of the linear convection–diffusion equation. This is followed by a section discussing application to the Navier–Stokes equations, including SATs, numerical dissipation and the transformation to curvilinear coordinates. Next a variational interpretation of SBP schemes is provided, showing the connection to, for example, discontinuous Galerkin finite-element methods. The variational interpretation and dual consistency also enable proofs of functional superconvergence and error estimates. We then describe a further generalization of the SBP concept that further reinforces the link to quadrature rules and enables unification of many operators under the SBP umbrella. This is followed by a few additional topics and conclusions.