Sparse-Grid Implementation of Fixed-Point Fast Sweeping WENO Schemes for Eikonal Equations

Fixed-point fast sweeping methods are a class of explicit iterative methods developed in the literature to efficiently solve steady-state solutions of hyperbolic partial differential equations(PDEs).As other types of fast sweeping schemes,fixed-point fast sweeping methods use the Gauss-Seidel iterations and alternating sweeping strategy to cover characteristics of hyperbolic PDEs in a certain direction simultaneously in each sweeping order.The resulting iterative schemes have a fast convergence rate to steady-state solutions.Moreover,an advantage of fixed-point fast sweeping methods over other types of fast sweeping methods is that they are explicit and do not involve the inverse operation of any nonlinear local system.Hence,they are robust and flexible,and have been combined with high-order accurate weighted essentially non-oscillatory(WENO)schemes to solve various hyperbolic PDEs in the literature.For multidimensional nonlinear problems,high-order fixed-point fast sweeping WENO methods still require quite a large amount of computational costs.In this technical note,we apply sparse-grid techniques,an effective approximation tool for multidimensional problems,to fixed-point fast sweeping WENO methods for reducing their computational costs.Here,we focus on fixed-point fast sweeping WENO schemes with third-order accuracy(Zhang et al.2006[41]),for solving Eikonal equations,an important class of static Hamilton-Jacobi(H-J)equations.Numerical experiments on solving multidimensional Eikonal equations and a more general static H-J equation are performed to show that the sparse-grid computations of the fixed-point fast sweeping WENO schemes achieve large savings of CPU times on refined meshes,and at the same time maintain comparable accuracy and resolution with those on corresponding regular single grids.

非结构网格上求解二维H-J方程的一种WENO格式

基于WENO(Weighted Essentially Non-Oscillatory)的思想,提出了一种在非结构网格上求解二维Hamilton-Jacobi(简称H-J)方程的数值方法.该方法利用Abgrall提出的数值通量,在每个三角形单元上构造三次加权插值多项式,得到了一个求解H-J方程的高阶精度格式.数值实验结果表明,该方法计算速度较快,具有较高的精度,而且对导数间断有较高的分辨率.

Hypersonic Shock Wave/Boundary Layer Interactions by a Third-Order Optimized Symmetric WENO Scheme

A novel third-order optimized symmetric weighted essentially non-oscillatory(WENO-OS3)scheme is used to simulate the hypersonic shock wave/boundary layer interactions.Firstly,the scheme is presented with the achievement of low dissipation in smooth region and robust shock-capturing capabilities in discontinuities.The Maxwell slip boundary conditions are employed to consider the rarefied effect near the surface.Secondly,several validating tests are given to show the good resolution of the WENO-OS3 scheme and the feasibility of the Maxwell slip boundary conditions.Finally,hypersonic flows around the hollow cylinder truncated flare(HCTF)and the25°/55°sharp double cone are studied.Discussions are made on the characteristics of the hypersonic shock wave/boundary layer interactions with and without the consideration of the slip effect.The results indicate that the scheme has a good capability in predicting heat transfer with a high resolution for describing fluid structures.With the slip boundary conditions,the separation region at the corner is smaller and the prediction is more accurate than that with no-slip boundary conditions.

Quinpi:Integrating Conservation Laws with CWENO Implicit Methods

Many interesting applications of hyperbolic systems of equations are stiff,and require the time step to satisfy restrictive stability conditions.One way to avoid small time steps is to use implicit time integration.Implicit integration is quite straightforward for first-order schemes.High order schemes instead also need to control spurious oscillations,which requires limiting in space and time also in the linear case.We propose a framework to simplify considerably the application of high order non-oscillatory schemes through the introduction of a low order implicit predictor,which is used both to set up the nonlinear weights of a standard high order space reconstruction,and to achieve limiting in time.In this preliminary work,we concentrate on the case of a third-order scheme,based on diagonally implicit Runge Kutta(DIRK)integration in time and central weighted essentially non-oscillatory(CWENO)reconstruction in space.The numerical tests involve linear and nonlinear scalar conservation laws.

Efficient Sparse-Grid Implementation of a Fifth-Order Multi-resolution WENO Scheme for Hyperbolic Equations

High-order accurate weighted essentially non-oscillatory(WENO)schemes are a class of broadly applied numerical methods for solving hyperbolic partial differential equations(PDEs).Due to highly nonlinear property of the WENO algorithm,large amount of computational costs are required for solving multidimensional problems.In our previous work(Lu et al.in Pure Appl Math Q 14:57–86,2018;Zhu and Zhang in J Sci Comput 87:44,2021),sparse-grid techniques were applied to the classical finite difference WENO schemes in solving multidimensional hyperbolic equations,and it was shown that significant CPU times were saved,while both accuracy and stability of the classical WENO schemes were maintained for computations on sparse grids.In this technical note,we apply the approach to recently developed finite difference multi-resolution WENO scheme specifically the fifth-order scheme,which has very interesting properties such as its simplicity in linear weights’construction over a classical WENO scheme.Numerical experiments on solving high dimensional hyperbolic equations including Vlasov based kinetic problems are performed to demonstrate that the sparse-grid computations achieve large savings of CPU times,and at the same time preserve comparable accuracy and resolution with those on corresponding regular single grids.

Gas kinetic flux solver based finite volume weighted essentially non-oscillatory scheme for inviscid compressible flows

A high-order gas kinetic flux solver(GKFS)is presented for simulating inviscid compressible flows.The weighted essentially non-oscillatory(WENO)scheme on a uniform mesh in the finite volume formulation is combined with the circular function-based GKFS(C-GKFS)to capture more details of the flow fields with fewer grids.Different from most of the current GKFSs,which are constructed based on the Maxwellian distribution function or its equivalent form,the C-GKFS simplifies the Maxwellian distribution function into the circular function,which ensures that the Euler or Navier-Stokes equations can be recovered correctly.This improves the efficiency of the GKFS and reduces its complexity to facilitate the practical application of engineering.Several benchmark cases are simulated,and good agreement can be obtained in comparison with the references,which demonstrates that the high-order C-GKFS can achieve the desired accuracy.

New High-Order Numerical Methods for Hyperbolic Systems of Nonlinear PDEs with Uncertainties

In this paper,we develop new high-order numerical methods for hyperbolic systems of nonlinear partial differential equations(PDEs)with uncertainties.The new approach is realized in the semi-discrete finite-volume framework and is based on fifth-order weighted essentially non-oscillatory(WENO)interpolations in(multidimensional)random space combined with second-order piecewise linear reconstruction in physical space.Compared with spectral approximations in the random space,the presented methods are essentially non-oscillatory as they do not suffer from the Gibbs phenomenon while still achieving high-order accuracy.The new methods are tested on a number of numerical examples for both the Euler equations of gas dynamics and the Saint-Venant system of shallow-water equations.In the latter case,the methods are also proven to be well-balanced and positivity-preserving.

对流扩散方程的基于加权本质非振荡插值的调整对流的修正特征差分解法

本文把 J.Douglas 提出的调整对流的修正特征差分法 (MMOCAA, Numer. Math., 1999,83:353- 369 ) 和加权本质非振荡 WENO 插值相结合,提出了求解对流扩散方程的 WENO - MMO- CAA 差分方法。此方法避免了原来基于高次 (≥ 2) Lagrange 插值的 MMOCAA 差分方法在解 的大梯度附近所产生的震荡。本文给出了格式的误差估计及数值例子。

Conservative high precision pseudo arc-length method for strong discontinuity of detonation wave

A hyperbolic conservation equation can easily generate strong discontinuous solutions such as shock waves and contact discontinuity.By introducing the arc-length parameter,the pseudo arc-length method(PALM)smoothens the discontinuous solution in the arc-length space.This in turn weakens the singularity of the equation.To avoid constructing a high-order scheme directly in the deformed physical space,the entire calculation process is conducted in a uniform orthogonal arc-length space.Furthermore,to ensure the stability of the equation,the time step is reduced by limiting the moving speed of the mesh.Given that the calculation does not involve the interpolation process of physical quantities after the mesh moves,it maintains a high computational efficiency.The numerical examples show that the algorithm can effectively reduce numerical oscillations while maintaining excellent characteristics such as high precision and high resolution.

Rotor wake capture improvement based on high-order spatially accurate schemes and chimera grids

A high-order upwind scheme has been developed to capture the vortex wake of a helicopter rotor in the hover based on chimera grids. In this paper, an improved fifth-order weighted essentially non-oscillatory （WENO） scheme is adopted to interpolate the higher-order left and right states across a cell interface with the Roe Riemann solver updating inviscid flux, and is compared with the monotone upwind scheme for scalar conservation laws （MUSCL）. For profitably capturing the wake and enforcing the period boundary condition, the computation regions of flows are discretized by using the struc- tured chimera grids composed of a fine rotor grid and a cylindrical background grid. In the background grid, the mesh cells located in the wake regions are refined after the so- lution reaches the approximate convergence. Considering the interpolation characteristic of the WENO scheme, three layers of the hole boundary and the interpolation boundary are searched. The performance of the schemes is investigated in a transonic flow and a subsonic flow around the hovering rotor. The results reveal that the present approach has great capabilities in capturing the vortex wake with high resolution, and the WENO scheme has much lower numerical dissipation in comparison with the MUSCL scheme.

WENO Interpolation-Based and Upwind-Biased Free-Stream Preserving Nonlinear Schemes

For flow simulations with complex geometries and structured grids,it is preferred for high-order difference schemes to achieve high accuracy.In order to achieve this goal,the satisfaction of free-stream preservation is necessary to reduce the numerical error in the numerical evaluation of grid metrics.For the linear upwind schemes with flux splitting the free-stream preserving property has been achieved in the early study[Q.Li et al.,Commun.Comput.Phys.,22(2017),pp.64–94].In the current paper,new series of nonlinear upwind-biased schemes through WENO interpolation will be proposed.In the new nonlinear schemes,the shock-capturing capability on distorted grids is achieved,which is unavailable for the aforementioned linear upwind schemes.By the inclusion of fluxes on the midpoints,the nonlinearity in the scheme is obtained through WENO interpolations,and the upwind-biased construction is acquired by choosing relevant grid stencils.New third-and fifth-order nonlinear schemes are developed and tested.Discussions are made among proposed schemes,alternative formulations of WENO and hybrid WCNS,in which a general formulation of center scheme with midpoint and nodes employed is obtained as a byproduct.Through the numerical tests,the proposed schemes can achieve the designed orders of accuracy and free-stream preservation property.In 1-D Sod and Shu-Osher problems,the results are consistent with the theoretical predictions.In 2-D cases,the vortex preservation,supersonic inviscid flow around cylinder at M¥=4,Riemann problem,and shock-vortex interaction problems have been tested.More specifically,two types of grids are employed,i.e.,the uniform/smooth grids and the randomized/locally-randomized grids.All schemes can get satisfactory results in uniform/smooth grids.On the randomized grids,most schemes have accomplished computations with reasonable accuracy,except the failure of one third-order scheme in Riemann problem and shock-vortex interaction.Overall,the proposed nonlinear schemes have the capability to solve flow problems on badly deformed grids,and the schemes can be used in the engineering applications.

非稳态Hamilton-Jacobi方程的7阶加权紧致非线性格式

Hamilton-Jacobi (HJ)方程是一类重要的非线性偏微分方程,在物理学、流体力学、图像处理、微分几何、金融数学、最优化控制理论等方面有着广泛的应用.由于HJ方程的弱解存在但不唯一,且解的导数可能出现间断,导致其数值求解具有一定的难度.本文提出了非稳态HJ方程的7阶精度加权紧致非线性格式(WCNS).该格式结合了Hamilton函数的Lax-Friedrichs型通量分裂方法和一阶空间导数左、右极限值的高阶精度混合节点和半节点型中心差分格式.基于7点全局模板和4个4点子模板推导了半节点函数值的高阶线性逼近和4个低阶线性逼近,以及全局模板和子模板的光滑度量指标.为避免间断附近数值解产生非物理振荡以及提高格式稳定性,采用WENO型非线性插值方法计算半节点函数值.时间离散采用3阶TVD型RungeKutta方法.通过理论分析验证了WCNS格式对于光滑解具有最佳的7阶精度.为方便比较,经典的7阶WENO格式也被推广用于求解HJ方程.数值结果表明,本文提出的WCNS格式能够很好地模拟HJ方程的精确解,且在光滑区域能够达到7阶精度;与经典的同阶WENO格式相比, WCNS格式在精度、收敛性和分辨率方面更优,计算效率略高.

Heterogeneous Parallel Algorithm Design and Performance Optimization for WENO on the Sunway TaihuLight Supercomputer

A Weighted Essentially Non-Oscillatory scheme(WENO) is a solution to hyperbolic conservation laws,suitable for solving high-density fluid interface instability with strong intermittency. These problems have a large and complex flow structure. To fully utilize the computing power of High Performance Computing(HPC) systems, it is necessary to develop specific methodologies to optimize the performance of applications based on the particular system’s architecture. The Sunway TaihuLight supercomputer is currently ranked as the fastest supercomputer in the world. This article presents a heterogeneous parallel algorithm design and performance optimization of a high-order WENO on Sunway TaihuLight. We analyzed characteristics of kernel functions, and proposed an appropriate heterogeneous parallel model. We also figured out the best division strategy for computing tasks,and implemented the parallel algorithm on Sunway TaihuLight. By using access optimization, data dependency elimination, and vectorization optimization, our parallel algorithm can achieve up to 172× speedup on one single node, and additional 58× speedup on 64 nodes, with nearly linear scalability.

HERMITE WENO SCHEMES WITH LAX-WENDROFF TYPE TIME DISCRETIZATIONS FOR HAMILTON-JACOBI EQUATIONS

In this paper, we use Hermite weighted essentially non-oscillatory （HWENO） schemes with a Lax-Wendroff time discretization procedure, termed HWENO-LW schemes, to solve Hamilton-Jacobi equations. The idea of the reconstruction in the HWENO schemes comes from the original WENO schemes, however both the function and its first derivative values are evolved in time and are used in the reconstruction. One major advantage of HWENO schemes is its compactness in the reconstruction. We explore the possibility in avoiding the nonlinear weights for part of the procedure, hence reducing the cost but still maintaining non-oscillatory properties for problems with strong discontinuous derivative. As a result, comparing with HWENO with Runge-Kutta time discretizations schemes （HWENO-RK） of Qiu and Shu [19] for Hamilton-Jacobi equations, the major advantages of HWENO-LW schemes are their saving of computational cost and their compactness in the reconstruction. Extensive numerical experiments are performed to illustrate the capability of the method.

On the Positivity of Linear Weights in WENO Approximations

High order accurate weighted essentially non-oscillatory （WENO） schemes have been used extensively in numerical solutions of hyperbolic partial differential equations and other convection dominated problems. However the WENO procedure can not be applied directly to obtain a stable scheme when negative linear weights are present. In this paper, we first briefly review the WENO framework and the role of linear weights, and then present a detailed study on the positivity of linear weights in a few typical WENO procedures, including WENO interpolation, WENO reconstruction and WENO approximation to first and second derivatives, and WENO integration. Explicit formulae for the linear weights are also given for these WENO procedures. The results of this paper should be useful for future design of WENO schemes involving interpolation, reconstruction, approximation to first and second derivatives, and integration procedures.

Interface flux reconstruction method based on optimized weight essentially non-oscillatory scheme

Aimed at the computational aeroacoustics multi-scale problem of complex configurations discretized with multi-size mesh, the flux reconstruction method based on modified Weight Essentially Non-Oscillatory（WENO） scheme is proposed at the interfaces of multi-block grids.With the idea of Dispersion-Relation-Preserving（DRP） scheme, different weight coefficients are obtained by optimization, so that it is in WENO schemes with various characteristics of dispersion and dissipation. On the basis, hybrid flux vector splitting method is utilized to intelligently judge the amplitude of the gap between grid interfaces. After the simulation and analysis of 1D convection equation with different initial conditions, modified WENO scheme is proved to be able to independently distinguish the gap amplitude and generate corresponding dissipation according to the grid resolution. Using the idea of flux reconstruction at grid interfaces, modified WENO scheme with increasing dissipation is applied at grid points, while DRP scheme with low dispersion and dissipation is applied at the inner part of grids. Moreover, Gauss impulse spread and periodic point sound source flow among three cylinders with multi-scale grids are carried out. The results show that the flux reconstruction method at grid interfaces is capable of dealing with Computational Aero Acoustics（CAA） multi-scale problems.

Third Order WENO Scheme on Three Dimensional Tetrahedral Meshes

We extend the weighted essentially non-oscillatory(WENO)schemes on two dimensional triangular meshes developed in[7]to three dimensions,and construct a third order finite volume WENO scheme on three dimensional tetrahedral meshes.We use the Lax-Friedrichs monotone flux as building blocks,third order reconstructions made from combinations of linear polynomials which are constructed on diversified small stencils of a tetrahedral mesh,and non-linear weights using smoothness indicators based on the derivatives of these linear polynomials.Numerical examples are given to demonstrate stability and accuracy of the scheme.

On the Order of Accuracy and Numerical Performance of Two Classes of Finite Volume WENO Schemes

In this paper we consider two commonly used classes of finite volume weighted essentially non-oscillatory(WENO)schemes in two dimensional Cartesian meshes.We compare them in terms of accuracy,performance for smooth and shocked solutions,and efficiency in CPU timing.For linear systems both schemes are high order accurate,however for nonlinear systems,analysis and numerical simulation results verify that one of them(Class A)is only second order accurate,while the other(Class B)is high order accurate.The WENO scheme in Class A is easier to implement and costs less than that in Class B.Numerical experiments indicate that the resolution for shocked problems is often comparable for schemes in both classes for the same building blocks and meshes,despite of the difference in their formal order of accuracy.The results in this paper may give some guidance in the application of high order finite volume schemes for simulating shocked flows.

A robust WENO scheme for nonlinear waves in a moving reference frame

For robust nonlinear wave simulation in a moving reference frame, we recast the free surface problem in Hamilton-Jacobi form and propose a Weighted Essentially Non-Oscillatory （WENO） scheme to automatically handle the upwinding of the convective term. A new automatic procedure for deriving the linear WENO weights based on a Taylor series expansion is introduced. A simplified smoothness indicator is proposed and is shown to perform well. The scheme is combined with high-order explicit Runge-Kutta time integration and a dissipative Lax-Friedrichs-type flux to solve for nonlinear wave propagation in a moving frame of reference. The WENO scheme is robust and less dissipative than the equivalent order upwind-biased finite difference scheme for all ratios of frame of reference to wave propagation speed tested. This provides the basis for solving general nonlinear wave-structure interaction problems at forward speed.

The Formulation of Finite Difference RBFWENO Schemes for Hyperbolic Conservation Laws:An Alternative Technique

To solve conservation laws,efficient schemes such as essentially nonoscillatory(ENO)and weighted ENO(WENO)have been introduced to control the Gibbs oscillations.Based on radial basis functions(RBFs)with the classical WENO-JS weights,a new type of WENO schemes has been proposed to solve conservation laws[J.Guo et al.,J.Sci.Comput.,70(2017),pp.551–575].The purpose of this paper is to introduce a new formulation of conservative finite difference RBFWENO schemes to solve conservation laws.Unlike the usual method for reconstructing the flux functions,the flux function is generated directly with the conservative variables.Comparing with Guo and Jung(2017),the main advantage of this framework is that arbitrary monotone fluxes can be employed,while in Guo and Jung(2017)only smooth flux splitting can be used to reconstruct flux functions.Several 1D and 2D benchmark problems are prepared to demonstrate the good performance of the new scheme.