Two-Dimensional RBF-ENO Method on Unstructured Grids

Solving systems of hyperbolic conservation laws with high-order methods continues to attract substantial interest. In two dimensions, the system of conservation law on differential form is given aswith the conserved variables \(u:\mathbb {R}^2\times \mathbb {R}_{+} \rightarrow \mathbb {R}^N\), the flux \(f_i:\mathbb {R}^N\rightarrow \mathbb {R}^N\) and the initial condition \(u_0\). A well-known method to solve hyperbolic conservation laws is the class of finite volume methods. It is based on a discretization of the domain into control volumes and an approximation of the flux through its boundaries. Van Leer [33] introduced the MUSCL approach which is based on an high-order approximation of the flux through the boundaries. A well-known challenge for high-order methods is the property of the conservation laws to form discontinuities from smooth initial data [26]. Thus, solutions need to be defined in the weak (distributional) sense. To prevent stability issues, caused by the discontinuous solutions, Harten et al. [17] proposed the principle of essentially non-oscillatory (ENO) methods. A powerful extension of the ENO method is the weighted ENO (WENO) method [30]. Alternative methods to avoid stability problems and unphysical oscillations are based on adding artificial viscosity [34] or on the use of limiters [18]. A generalization of the finite volume method is the class of Discontinuous Galerkin (DG) finite element methods [7], for which it is necessary to add limiters to ensure non-oscillatory approximations [22]. There exist several approaches that combine RBFs with finite volume methods, e.g. a high-order WENO approach based on polyharmonics [1], a high-order WENO approach based on multiquadratics [6], a high-order RBF based CWENO method [21] and an entropy stable RBF based ENO method [20]. However, most of these are suitable only for one-dimensional grids or are at most second order accurate. We seek to overcome these limitations with a new RBF-ENO method on two dimensional general grids.

In Sect. 2, we introduce the finite volume scheme based on the MUSCL approach [33] and describe the basics of RBF interpolation in Sect. 3. Sections 4 and 5 contain the main contribution. In Sect. 4 we introduce a stable evaluation method for RBF interpolation with a polynomial augmentation, which circumvents the known error stagnation. In the same section we include a general proof of the order of convergence for RBFs augmented with polynomials. In Sect. 5, we introduce a smoothness indicator for RBFs, based on the sign-stable one-dimensional approach developed in [20]. We combine these results to construct an arbitrarily high-order RBF based ENO finite volume method. In Sect. 6, we demonstrate the robustness of the numerical scheme with a variety of numerical examples, while Sect. 7 offers a few concluding remarks.

We assume a triangular grid of \(\varOmega \subset \mathbb {R}^2\), consisting of triangular cells \(C_i = (x_i ,x_k, x_j)\) as illustrated in Fig. 1. The finite volume method is based on cell averages \(U_i = \frac{1}{|C_i|}\int _{C_i} u(x) \mathrm {d}x\) over the cell \(C_i\). By integrating (1) over the cell and dividing it by its size \(|C_i|\) we recover after applying the divergence theorem the semi-discrete schemewith the numerical flux \(F_{il_{e}} = F_{il_{e}}(U_i,U_{il_{e}},\mathbf{n }_{il_{e}})\) with the accuracy conditionwhere \(\mathbf{f} = (f_1,f_2)\), \(S_{il_{e}} = \partial C_i \cap \partial C_{il_{e}}\), \(U_{il_{e}}\) is the cell average of \(C_{il_{e}}\) and \(\mathbf{n }_{il_{e}}\) is the outward pointing normal vector. The numerical flux \(F_{il_{e}}\) can be expressed using an (approximate) Riemann solver. A common choice is the Rusanov fluxwithHere, \(\lambda _{max}(A)\) is the biggest eigenvalue of A and \(\mathbf{n }_{il_{e}}\) the normal vector to the interface \(S_{il_{e}}\).

A high-order boundary integral approximation of (3) and a high-order accurate (polynomial) reconstruction s of the local solution can be used to evaluate the first order flux \(F(U,V,{\mathbf{n }_{il_{e}}})\) on the quadrature points. This high-order flux can be written aswith the quadrature weights \(\omega _k\), the quadrature points \(\mathbf{x} _k\) for \(k = 1,\dots ,n_Q\) with \(n_Q\in \mathbb {N}\) the number of quadrature points and the high-order accurate reconstructions \(s_i\) of the solution in cell \(C_i\). The high-order reconstruction \(s_i\) is based on a stencil of cells which includes \(C_i\). In all cases, we can apply an arbitrary time discretization technique to recover a fully discrete scheme, e.g., an SSPRK method [14].

The use of radial basis function for scattered data interpolation has a long history. Their mesh-free property and flexibility for high-dimensional data makes them advantageous when compared to polynomials.

As mentioned in Sect. 3, the ill-conditioning of the RBF interpolation is a well-known challenge. However, RBFs within finite volume methods are of a slightly different nature. In general, the RBF approximation achieves exponential order of convergence for smooth functions by increasing the number of interpolation nodes in a certain domain. The setting for finite volume methods is different since the number of interpolation points remains fixed at a rather low number of nodes and only the fill-distance is reduced.

Based on [11, 12] it is known that the combination of polyharmonics and Gaussians with polynomials overcomes the stagnation error. Bayona [3] shows that under certain assumptions the order of convergence is ensured by the polynomial part.

We propose to use multiquadratic rather than polyharmonic or Gaussian RBFs to enable the use of the smoothness indicator, developed in [20]. Since the RBFs are only used to ensure solvability of the linear system, we can useas the shape parameter with the separation distance \(\varDelta x :=\min _{i\ne j}{\Vert \mathbf{x} _i-\mathbf{x} _j\Vert }\) for the interpolation nodes \(\mathbf{x} _1,\dots , \mathbf{x} _n\) with \(n\in \mathbb {N}\). To control the conditioning of the polynomial part we use the basisfor \(i = 1,\dots , m\) with \(\tilde{p}_i\in \{\mathbb {R}^d\rightarrow \mathbb {R}, \mathbf{x} \mapsto x_1^{\alpha _1}\dots x_d^{\alpha _d}| \; \sum _{i=1}^d \alpha _i < l, \alpha _i\in \mathbb {N}\}\), \(\text {deg}(\tilde{p}_i) \leqslant \text {deg}(\tilde{p}_{i+1})\) and \({\tilde{\mathbf{x}}}\in \{\mathbf{x }_1\dots ,\mathbf{x }_n\}\). The best choice for \({\tilde{\mathbf{x}}}\) would be the barycenter of the stencil. However, to use the same polynomials for different stencils in the ENO scheme we choose the central one.

In this section, we introduce a new RBF-ENO method on two-dimensional general grids that can be generalized to higher dimensions. The method is based on the MUSCL approach described in Sect. 2, the RBF-ENO reconstruction introduced in [20], and the evaluation technique discussed in Sect. 4.

The finite volume method relies on the high-order flux (6) based on the boundary integral of the Rusanov flux (4) which is approximated by the Gauss-Legendre quadrature [2]. For the evaluation of the high-order flux we use the RBF reconstruction (14) and to compute the cell average we use a cubature rule for triangles [10]. The ENO reconstruction (Algorithm 1) is based on the one introduced by Harten et al. [17]. Thus, we recursively add one cell to the stencil \(S_i\) and all its neighbors to a list of possible choices \(N_i\) for the next step. In each step, we add the cell in \(N_i\) which results in the stencil that has the smallest smoothness indicator IS, indicating the smoothness of the solution on a stencil. It is well-known that this strategy comes with high costs, but is also very robust. As the smoothness indicator we choose a generalization of the one-dimensional indicator introduced in [20]for the reconstruction \(s(\mathbf{x} ) = \sum _{i=1}^n a_i\lambda _{C_i}^{\xi }\phi (\mathbf{x} -\xi ) + \sum _{j=1}^m b_j p_j(\mathbf{x} )\).

It is important to choose the right degree of the polynomial for each stencil. For a polynomial of degree l we need at least \(n = \frac{(l+2)(l+1)}{2}\) cells, and thus \( l = -1.5 + \frac{1}{2}\sqrt{1 + 8n}\). To reduce the probability of \(\{\lambda _{C_{i_j}}\}_{j = 1}^n\) having no \(\varPi _{l}(\mathbb {R}^d)\)-unisolvent subset, we chooseFurthermore, we use multiquadratics with a shape parameter based on (16) and the polynomials (17). Since the order of convergence is not influenced by the order of the multiquadratics and following the observations in Sect. 4.4, we choose first order multiquadratics.

We need to slightly adapt the evaluation method from Sect. 4 to use it for the RBF-ENO method. The coefficients \(a_i\) depend on the shape parameter. Thus, we must compare the smoothness indicator (54) with respect to the same shape parameter. By assuming approximately uniform equilateral triangles, we approximate \(\varDelta x\) aswith the radius \(r_{j,inscr}\) of the inscribed circle of the jth cell and \(|C_i|\) is the area of the ith cell. The last estimate comes fromwhere we assume \(C_i\) to be an equilateral triangle. Hence, we choose the shape parameterwith the polynomial basis (17).

The advantage of RBFs over polynomials is the ability to deal with a stencil with a variable number of elements. The condition for RBFs to have a well-defined system of equations is the existence of a subset which is \(\varPi _{l}(\mathbb {R}^d)\)-unisolvent and l must be larger than the order of the RBF. Thus, we can use a bigger stencil than the dimension of \(\varPi _{l}(\mathbb {R}^d)\) to circumvent cell constellations that are ill-conditioned. To keep the stencil compact we classify each cell around the central one, depending on its distance \(d\in \mathbb {N}\), such thatand introduce \(d_{max}\) as the maximal distance. A stable configuration for second to fourth order methods is given in Table 3.

Note that (55) does not coincide with the values from Table 3. However, from numerical experiments this combination seems superior.

Summary of the RBF-ENO method

In this chapter, we demonstrate the robustness of the second and third order RBF-ENO method on general grids. For the time discretization we use a third order SSPRK method [14]. The grids are generated by distmesh2d(), which is based on the Delaunay algorithm [27].

In this work, we propose a new RBF-ENO method for multi-dimensional problems on general grids. We introduced a stable evaluation method for RBFs, augmented with polynomials and a stencil selection algorithm based on [20]. We showed that the algorithm preserves the expected accuracy and we demonstrated its robustness for challenging test cases, including two classic Riemann problems, the shock-vortex interaction and the double Mach reflection problem.

However, it is well-known that the strategy of the stencil selection algorithm is coming with high costs. As shown for the Burgers equation the method is working also in the 4th order setup, but due to the high number of cells in the stencil it is extremely costly.

In the future, we will combine the stable and flexible RBF-ENO method with the standard (polynomial) WENO method on structured grids, to offset some of the computational cost of the RBF-ENO scheme.