PaperlayerView exact revision on arXiv

Source-linked AI summary

Adaptive Mesh Refinement for Hyperbolic Systems based on Third-Order Compact WENO Reconstruction

M. Semplice, A. Coco, G. Russo

arXiv:1407.4296v2math.NAcs.NA

TL;DR

Adaptive-grid WENO reconstruction can require wide stencils and mesh-dependent weights, complicating its use on changing grids. This paper extends Compact WENO to nonuniform quad-tree meshes and builds an adaptive third-order scheme around it. Tests report third-order error decay in one dimension and rates slightly higher than predicted in two dimensions, including with shocks.

  • Problem

    Compact stencils are desirable for adaptive refinement because gathering distant-neighbor data can be difficult as local grid topology changes.

    Source: §1 · p. 3

  • Method

    The paper extends Compact WENO to nonuniform quad-tree meshes using central-cell interpolation and least-squares fits for neighboring averages.

    Source: §1 · p. 4, §6 · p. 30

  • Results

    The adaptive third-order scheme outperforms second-order schemes and yields smaller meshes refined narrowly around shocks; tests show predicted third-order error decay in one dimension and slightly higher-than-predicted rates in two dimensions.

    Source: §6 · p. 32

  • Takeaways & Limitations

    The reconstruction's linear weights do not depend on neighboring cell sizes, avoiding the need to handle many local grid geometries in its two-dimensional generalization.

    Source: §6 · p. 31

    The scheme uses a global CFL time step; local time stepping for third-order schemes is left for future work.

    Source: §3 · p. 13

Abstract

from arXiv · show

In this paper we generalize to non-uniform grids of quad-tree type the Compact WENO reconstruction of Levy, Puppo and Russo (SIAM J. Sci. Comput., 2001), thus obtaining a truly two-dimensional non-oscillatory third order reconstruction with a very compact stencil and that does not involve mesh-dependent coefficients. This latter characteristic is quite valuable for its use in h-adaptive numerical schemes, since in such schemes the coefficients that depend on the disposition and sizes of the neighboring cells (and that are present in many existing WENO-like reconstructions) would need to be recomputed after every mesh adaption. In the second part of the paper we propose a third order h-adaptive scheme with the above-mentioned reconstruction, an explicit third order TVD Runge-Kutta scheme and the entropy production error indicator proposed by Puppo and Semplice (Commun. Comput. Phys., 2011). After devising some heuristics on the choice of the parameters controlling the mesh adaption, we demonstrate with many numerical tests that the scheme can compute numerical solution whose error decays as $\langle N\rangle^{-3}$, where $\langle N\rangle$ is the average number of cells used during the computation, even in the presence of shock waves, by making a very effective use of h-adaptivity and the proposed third order reconstruction.

1 Introduction

The introduction motivates a compact, non-oscillatory reconstruction for adaptive finite-volume schemes, where high-order WENO on non-Cartesian grids can require many geometry-dependent coefficients and wide stencils. The paper extends Compact WENO to nonuniform meshes, using a single reconstruction polynomial and linear weights across quadrature nodes and grid configurations.

1 Introduction

  • Higher-order flux quadrature on non-Cartesian grids increases the number of linear weights needed for boundary integration.The introduction contrasts this with midpoint quadrature, which suffices only through second order.Source: §1 · pp. 2–3
  • Arbitrary-triangle WENO can require storing 90 linear weights and 180 smoothness-indicator constants per triangle, with recomputation after mesh changes.The cited construction also does not guarantee positive linear weights.Source: §1 · p. 3
  • Compact stencils matter because adaptive-grid topology can change each timestep, making distant-neighbor information harder to gather efficiently.The introduction identifies this as a challenge for achieving order k + 1 on smooth solutions.Source: §1 · p. 3
  • CWENO combines a central degree-2 polynomial with directional degree-1 polynomials to control oscillations while retaining a compact stencil.The directional polynomials interpolate cell averages in sectors of the central stencil.Source: §1 · pp. 3–4
  • The nonlinear CWENO weights provide third-order accuracy in smooth regions and reduce the reconstruction to linear near discontinuities.The paper uses α0 = 1/2 throughout; higher values are reported as beneficial only without discontinuities.Source: §1 · p. 4
  • The reconstruction produces one polynomial evaluable throughout the cell with uniform accuracy, using a single set of linear weights across quadrature nodes.The paper notes this is useful for adaptive grids and for well-balanced source-term quadrature [30].Source: §1 · p. 4
  • The paper extends CWENO to nonuniform meshes; in multiple dimensions, it enforces exact interpolation in the central cell and least-squares fitting in the remaining stencil.It also studies adaptive-mesh parameter choices and reports numerical tests in one and two dimensions.Source: §1 · p. 4

2 Third order, compact stencil reconstruction

The section constructs compact WENO reconstructions for nonuniform quad-tree grids, extending the one-dimensional procedure and adapting the two-dimensional stencils to variable neighbor counts. Its reconstruction uses least-squares fits for neighboring cell averages and supports boundary treatment with one ghost-cell layer.

2 Third order, compact stencil reconstruction

  • The grid uses cubic cells that can be recursively split into 2^d equal parts and represented by binary, quad-, or oct-trees.This restricts the adaptive grids to a structured refinement of Cartesian cells.Source: §2 · pp. 4–5

2.1 One space dimension

  • In one dimension, the optimal quadratic interpolates the central cell average and its two neighbors, while directional linear polynomials provide the compact CWENO alternatives.The method uses α0 = 1/2 and α1 = α2 = 1/4; the nonlinear weights use smoothness indicators, and the paper finds ϵ ∝ h works best experimentally.Source: §2.1 · pp. 5–6

2.2 Higher space dimension

  • In two dimensions, quad-tree refinement starts from a uniform Cartesian grid and recursively splits selected cells into four equal squares.The resulting hierarchy is stored as a quad-tree.Source: §2.2.1 · p. 7, Figure 1 · p. 7

2.2.2 CWENO reconstruction in 2D adaptive grid

  • A cell's quadratic optimal polynomial fits its neighbor averages in least squares; every quad-tree cell has at least five neighbors, enough for the five quadratic coefficients.The minimum-neighbor configuration is illustrated in Fig. 2.Source: §2.2.2 · p. 8, Figure 2 · p. 8
  • The directional linear stencils are modified when adaptive refinement would leave a stencil with only one cell, ensuring at least two cells per stencil for a well-determined least-squares fit.The four stencils follow the central cell's vertex directions; their linear polynomials match the central average exactly and fit selected neighbor averages in least squares.Source: §2.2.2 · pp. 9–10
  • The adaptive-grid reconstruction differs from the uniform-grid CWENO in: each directional plane comes from an overdetermined four-equation system rather than three imposed conditions.The two-dimensional reconstruction uses α0 = 1/2 and αγ = 1/8 for γ = 1,...,4.Source: §2.2.2 · p. 10

2.3 Treatment of the boundaries

  • One layer of ghost cells, sized to match adjacent physical cells, suffices for reconstruction near the boundary.Boundary conditions set ghost-cell averages and are applied again to obtain the exterior value needed for numerical fluxes.Source: §2.3 · p. 11

3 Fully discrete scheme and adaptivity

The fully discrete scheme computes numerical fluxes at Gauss quadrature nodes and uses a global time step satisfying the CFL condition across the domain. Mesh refinement and coarsening are driven by numerical entropy production, with local recomputation after refinement.

3 Fully discrete scheme and adaptivity

  • Gauss quadrature computes numerical fluxes on each boundary segment, and each flux is shared by its two adjacent cells to preserve conservation.The reconstruction in the two cells supplies the interior and exterior states at each node.Source: §3 · pp. 11–12
  • The scheme uses a global time step satisfying the CFL condition everywhere; local time stepping is left for future work.The authors say third-order local time stepping is non-trivial.Source: §3 · p. 13

3.1 Error estimators/indicators

  • Numerical entropy production is the refinement indicator because it is available for conservation laws with an entropy inequality, scales like truncation error in regular regions, and distinguishes contacts from shocks.The indicator is formed using an entropy pair and a compatible numerical entropy flux.Source: §3.1 · p. 13
  • In smooth regions, the indicator scales as O(h^r), while it scales as O(h) at contact discontinuities and O(1/h) at shocks.The smooth-region order r is the minimum of the scheme order and the quadrature order used for cell-average entropy.Source: §3.1 · p. 13
  • Cells exceeding the refinement threshold are split unless they already meet the maximum level, and the timestep is recomputed only in the split cell's numerical domain of dependence.New-cell averages come from averaging the reconstruction; coarsening replaces children whose entropy production falls below its threshold with their ancestor.Source: §3.1 · pp. 14–15
  • The implementation uses DUNE interfaces and supports adaptive schemes in one or two dimensions with spatial and temporal order up to three.The components for time stepping, fluxes, adaptivity, reconstruction, and error indicators can be interchanged.Source: §3.1 · p. 15

4 Order of accuracy

The section analyzes how error and cell counts scale for regular and piecewise-smooth solutions, including the effects of refinement near discontinuities.

4 Order of accuracy

  • For regular solutions, the expected error scales as N^(-r/d), with r the space-and-time order and d the number of space dimensions; h-adaptivity refines smaller-scale regions.Source: §4 · p. 15

4.1 One dimensional case

  • h = O(H^r) balances first-order error near a singularity against O(H^r) truncation error in smooth regions, so the singularity does not degrade expected O(H^r) accuracy there.The authors expect this accuracy after finite time with global time stepping Δt = O(h), as well as with local stepping where Δtmax = O(H).Source: §4.1 · p. 16
  • In the one-dimensional Burgers standing-shock test, refined cells cluster around the shock; the number involved is approximately L plus a number of smallest cells that grows mildly with L.Source: §4.1 · p. 16, Figure 5 · p. 17

4.2 Higher dimensional case

  • For a line discontinuity with h = cH^r, NTOT ≈ CI/(cH^r) + CR/H^2; regular-region cells dominate for r < 2, the counts scale alike at r = 2, and singular-line cells dominate for r > 2.Source: §4.2 · p. 18
  • O(1/NTOT) is the suggested asymptotic error limit with discontinuities in two dimensions, although higher-order reconstruction can achieve the same error with fewer cells.The paper also notes that, for a fixed coarsest mesh, higher-order reconstruction may yield a considerably smaller error.Source: §4.2 · p. 18

5 Numerical tests

The numerical tests assess reconstruction accuracy on non-uniform grids and the efficiency of h-adaptivity, including how refinement levels and thresholds affect convergence. They also compare third- and second-order schemes and uniform-grid schemes for shock-bubble interaction in terms of solution sharpness, cell use, and computation time.

Reconstruction tests

  • With ϵ = h, reconstruction errors were lower on smooth tests, convergence was robust on non-uniform grids, and discontinuity errors were comparable to ϵ = 10−6 except when aligned with a grid interface.On adaptive grids, average orders were 3.00 for ∥E∥1 and 3.19 for ∥E∥∞ with ϵ = h, versus 2.68 and 1.87 with ϵ = 10−6.Source: §5 · pp. 19–20, Table 6 · p. 21

One-dimensional linear transport test (2)

  • For the high-frequency transport test, all adaptive sequences improved on uniform grids, and s = 8 gave third-order convergence rates of 1.06, 2.62, 2.99, and 2.97.Uniform-grid runs did not show convergence until N0 ≥128; the adaptive solution showed no spurious oscillations at grid discontinuities.Source: §5 · pp. 23–24, Figure 7 · p. 23

A two-dimensional scalar test with smooth solution

  • In the smooth two-dimensional test, the third-order scheme achieved lower errors with fewer cells, and its adaptive mesh concentrated small cells in narrower regions.The third-order adaptive scheme also had a lower error constant than its uniform-grid counterpart.Source: §5 · p. 24, Figure 8 · p. 25

One dimensional Burgers equation

  • For standing Burgers shocks, growing refinement levels yielded EOC 2.0, while third-order runs adding two levels per refinement reached 2.7; s = 4 gave poorer work-precision performance than s = 2.For moving shocks, adaptive EOCs were 1.7 and 2.6 with s = 2.Source: §5 · pp. 25–27, Figure 9 · p. 26, Figure 10 · p. 26

One dimensional gas-dynamics: shock-acoustic interaction

  • In the shock-acoustic interaction, the third-order h-adaptive scheme showed improved error decay; for L=6++, s=4, its EOCs for the two plotted segments were 1.6 and 3.0.Uniform-grid methods showed convergence only when using more than 1000 cells, lacking the spatial resolution to resolve smooth waves in x ∈[0.65, 0.85] below that threshold.Source: §5 · pp. 27–28

2D Riemann problem

  • An error in the 10^-3 range required 6.18 × 10^4 cells for third-order adaptivity, versus 1.05 × 10^6 uniform-grid and 6.14 × 10^5 second-order adaptive cells.This comparison is for the two-dimensional Riemann problem; the third-order adaptive scheme also had a faster EOC than the second-order adaptive scheme in the reported series.Source: §5 · p. 29, Figure 12 · p. 29

Shock-bubble interaction in 2D gas-dynamics

  • The test models a right-moving shock impinging on a low-pressure stationary gas bubble in the 2D Euler equations, computed on a symmetric half-domain.The domain is [−0.1, 1.6] × [−0.5, 0.5], with reflecting conditions at y = 0 and y = ±0.5; the computation used coarse grids and h-adaptation.Source: §5 · pp. 29–30
  • 141539 versus 71895 cells on average and 2214934 versus 123114 at final time were used by the second- and third-order schemes, respectively.The third-order solution was sharper, especially near the upper boundary, behind the main shock, and around the vortex; CPU times were comparable at 18h44m for r = 2 and 18h35m for r = 3.Source: §5 · p. 30
  • The computation times compared favourably with uniform-grid schemes.Table 7 compares norm-1 errors and CPU times for the shock-bubble problem; the passage gives no specific uniform-grid values.Source: §5 · p. 30, Table 7 · p. 30

6 Conclusions

The paper extends Compact WENO to non-uniform quad-tree meshes and uses it in an entropy-production-indicator h-adaptive scheme; tests report third-order error decay and smaller, shock-focused meshes.

6 Conclusions

  • The extended reconstruction uses quad-tree meshes, gives uniformly accurate reconstruction across the cell, and uses linear weights independent of neighboring cell sizes.Source: §6 · pp. 30–31
  • The third-order scheme produces smaller per-cell errors than second-order schemes and, with h-adaptivity, much smaller meshes refined only near shocks.Source: §6 · p. 32
  • In one dimension, adaptive tests show the predicted third-order error decay rate; in two dimensions, rates are slightly higher than the heuristics predict.Source: §6 · p. 32
  • Future work includes deeper analysis of ε in the nonlinear weights, extension to barycentrically split triangular quad-trees, and third-order local timestepping.Source: §6 · p. 32
Loading 1407.4296v2…