Fast and Robust Sixth Order Multigrid Computation for 3D Convection Diffusion Equation

We present a sixth-order explicit compact finite difference scheme to solve the three-dimensional (3D) convection-diffusion equation. We first use a multiscale multigrid method to solve the linear systems arising from a 19-point fourth-order discretization scheme to compute the fourth-order solutions on both a coarse grid and a fine grid. Then an operator-based interpolation scheme combined with an extrapolation technique is used to approximate the sixth-order accurate solution on the fine grid. Since the multigrid method using a standard point relaxation smoother may fail to achieve the optimal grid-independent convergence rate for solving convection-diffusion equations with a high Reynolds number, we implement the plane relaxation smoother in the multigrid solver to achieve better grid independency. Supporting numerical results are presented to demonstrate the efficiency and accuracy of the sixth-order compact (SOC) scheme, compared with the previously published fourth-order compact (FOC) scheme.     

High-order accurate monotone compact running scheme for multidimensional hyperbolic equations

A high-order accurate monotone compact difference scheme proposed earlier by the author for one-dimensional nonstationary hyperbolic equations is extended to multidimensional equations. The resulting scheme is fourth-order accurate in space on a compact stencil and third-order accurate in time. Additionally, the scheme is conservative, absolutely stable, and efficient and can be solved using the running calculation method in space. By computing initial-boundary value problems for the linear advection equation and the nonlinear Hopf equation on refined meshes, it is shown that the orders of grid convergence of the multidimensional scheme are close to the corresponding orders of accuracy in independent variables. For the propagation of a two-dimensional rectangular pulse and the Hopf equation with a discontinuous solution, the multidimensional scheme is shown to inherit the monotonicity of its one-dimensional counterpart.     

三维泊松方程基于Richardson外推法的高阶紧致差分方法

基于Richardson外推法提出了数值求解三维泊松方程的高阶紧致差分方法.方法通过利用四阶和六阶紧致差分格式,分别在细网格和粗网格上求解,然后利用Richardson外推技术和算子插值方法,得到三维泊松方程在细网格上的六阶和八阶精度的数值解.数值实验结果验证了该方法的精确性和有效性.     

Compact difference scheme for two-dimensional fourth-order nonlinear hyperbolic equation

High-order compact finite difference method for solving the two-dimensional fourth-order nonlinear hyperbolic equation is considered in this article. In order to design an implicit compact finite difference scheme, the fourth-order equation is written as a system of two second-order equations by introducing the second-order spatial derivative as a new variable. The second-order spatial derivatives are approximated by the compact finite difference operators to obtain a fourth-order convergence. As well as, the second-order time derivative is approximated by the central difference method. Then, existence and uniqueness of numerical solution is given. The stability and convergence of the compact finite difference scheme are proved by the energy method. Numerical results are provided to verify the accuracy and efficiency of this scheme.     

Comparison of higher-order accurate schemes for solving the two-dimensional unsteady Burgers' equation

This paper is devoted to the testing and comparison of numerical solutions obtained from higher-order accurate finite difference schemes for the two-dimensional Burgers' equation having moderate to severe internal gradients. The fourth-order accurate two-point compact scheme, and the fourth-order accurate Du Fort Frankel scheme are derived. The numerical stability and convergence are presented. The cases of shock waves of severe gradient are solved and checked with the fourth-order accurate Du Fort Frankel scheme solutions. The present study shows that the fourth-order two-point compact scheme is highly stable and efficient in comparison with the fourth-order accurate Du Fort Frankel scheme.     

Compact mixed methods for convection/diffusion type problems

This paper presents a class of fourth-order compact finite difference technique for solving two-dimensional convection diffusion equation. The equation is recasted as a first-order mixed system, introducing a conservation and flux equations. Since flux appears explicitly in the mixed formulation, we search a fourth-order compact approximation of the primary solution field and flux. Based on Taylor series expansion, the proposed compact mixed formulation generalizes the work of Carey and Spotz [G.F. Carey, W.F. Spotz, Higher-order compact mixed methods, Commun. Numer. Meth. Eng. 13 (1997)]. We show that their fourth-order formulation corresponds to a particular case of our presented scheme, and we extend their work to variable diffusion and convection coefficients. Some numerical experiments are performed to demonstrate the fourth-order effective convergence rate.     

COMPACT FOURTH-ORDER FINITE DIFFERENCE SCHEMES FOR HELMHOLTZ EQUATION WITH HIGH WAVE NUMBERS

In this paper, two fourth-order accurate compact difference schemes are presented for solving the Helmholtz equation in two space dimensions when the corresponding wave numbers are large. The main idea is to derive and to study a fourth-order accurate compact difference scheme whose leading truncation term, namely, the O（h^4） term, is independent of the wave number and the solution of the Helmholtz equation. The convergence property of the compact schemes are analyzed and the implementation of solving the resulting linear algebraic system based on a FFT approach is considered. Numerical results are presented, which support our theoretical predictions.     

求解对流扩散反应方程的四阶混合紧致差分方法

针对一维对流扩散反应方程,基于对流扩散方程的四阶指数型紧致差分格式,以及一阶导数的四阶Padé公式,发展了一种高效求解对流扩散反应方程的混合型四阶紧致差分格式.数值实验结果验证了格式对于边界层问题或大雷诺数或大Pelect数的大梯度问题的求解的高精度和鲁棒性的优点.     

Gaussian spectral rules for second order finite-difference schemes

Earlier the authors suggested an algorithm of grid optimization for a second order finite-difference approximation of a two-point problem. The algorithm yields exponential superconvergence of the Neumann-to-Dirichlet map (or the boundary impedance). Here we extend that approach to PDEs with piecewise-constant coefficients and rectangular homogeneous subdomains. Examples of the numerical solution of the 2-dimensional oscillatory Helmholtz equation exhibit exponential convergence at prescribed points, where the cost per grid node is close to that of the standard five-point finite-difference scheme. Our scheme demonstrates high accuracy with slightly more than two grid points per wavelength and reduces the grid size by more than three orders as compared with the standard scheme.     

Accelerated multigrid high accuracy solution of the convection-diffusion equation with high Reynolds number

A fourth-order compact finite difference scheme is employed with the multigrid algorithm to obtain highly accurate numerical solution of the convection-diffusion equation with very high Reynolds number and variable coefficients. The multigrid solution process is accelerated by a minimal residual smoothing (MRS) technique. Numerical experiments are employed to show that the proposed multigrid solver is stable and yields accurate solution for high Reynolds number problems. We also show that the MRS acceleration procedure is efficient and the acceleration cost is negligible. © 1997 John Wiley & Sons, Inc.     

A high-order exponential scheme for solving 1D unsteady convection-diffusion equations

In this paper, a high-order exponential (HOE) scheme is developed for the solution of the unsteady one-dimensional convection-diffusion equation. The present scheme uses the fourth-order compact exponential difference formula for the spatial discretization and the (2,2) Padé approximation for the temporal discretization. The proposed scheme achieves fourth-order accuracy in temporal and spatial variables and is unconditionally stable. Numerical experiments are carried out to demonstrate its accuracy and to compare it with analytic solutions and numerical results established by other methods in the literature. The results show that the present scheme gives highly accurate solutions for all test examples and can get excellent solutions for convection dominated problems.     

Numerical pricing of options using high-order compact finite difference schemes

We consider high-order compact (HOC) schemes for quasilinear parabolic partial differential equations to discretise the Black–Scholes PDE for the numerical pricing of European and American options. We show that for the heat equation with smooth initial conditions, the HOC schemes attain clear fourth-order convergence but fail if non-smooth payoff conditions are used. To restore the fourth-order convergence, we use a grid stretching that concentrates grid nodes at the strike price for European options. For an American option, an efficient procedure is also described to compute the option price, Greeks and the optimal exercise curve. Comparisons with a fourth-order non-compact scheme are also done. However, fourth-order convergence is not experienced with this strategy. To improve the convergence rate for American options, we discuss the use of a front-fixing transformation with the HOC scheme. We also show that the HOC scheme with grid stretching along the asset price dimension gives accurate numerical solutions for European options under stochastic volatility.     

Estimation of 1-dimensional nonlinear stochastic differential equations based on higher-order partial differential equation numerical scheme and its application

A method based on higher-order partial differential equation (PDE) numerical scheme are proposed to obtain the transition cumulative distribution function (CDF) of the diffusion process (numerical differentiation of the transition CDF follows the transition probability density function (PDF)), where a transformation is applied to the Kolmogorov PDEs first, then a new type of PDEs with step function initial conditions and 0, 1 boundary conditions can be obtained. The new PDEs are solved by a fourth-order compact difference scheme and a compact difference scheme with extrapolation algorithm. After extrapolation, the compact difference scheme is extended to a scheme with sixth-order accuracy in space, where the convergence is proved. The results of the numerical tests show that the CDF approach based on the compact difference scheme to be more accurate than the other estimation methods considered; however, the CDF approach is not time-consuming. Moreover, the CDF approach is used to fit monthly data of the Federal funds rate between 1983 and 2000 by CKLS model.     

Iterative methods and high-order difference schemes for 2D elliptic problems with mixed derivative

We derive a fourth-order compact finite difference scheme for a two-dimensional elliptic problem with a mixed derivative and constant coefficients. We conduct experimental study on numerical solution of the problem discretized by the present compact scheme and the traditional second-order central difference scheme. We study the computed accuracy achieved by each scheme and the performance of the Gauss-Seidel iterative method, the preconditioned GMRES iterative method, and the multigrid method, for solving linear systems arising from the difference schemes.     

A fourth-order compact ADI method for solving two-dimensional unsteady convection–diffusion problems

In this article, an exponential high-order compact (EHOC) alternating direction implicit (ADI) method, in which the Crank–Nicolson scheme is used for the time discretization and an exponential fourth-order compact difference formula for the steady-state 1D convection–diffusion problem is used for the spatial discretization, is presented for the solution of the unsteady 2D convection–diffusion problems. The method is temporally second-order accurate and spatially fourth order accurate, which requires only a regular five-point 2D stencil similar to that in the standard second-order methods. The resulting EHOC ADI scheme in each ADI solution step corresponds to a strictly diagonally dominant tridiagonal matrix equation which can be inverted by simple tridiagonal Gaussian decomposition and may also be solved by application of the one-dimensional tridiagonal Thomas algorithm with a considerable saving in computing time. The unconditionally stable character of the method was verified by means of the discrete Fourier (or von Neumann) analysis. Numerical examples are given to demonstrate the performance of the method proposed and to compare mostly it with the high order ADI method of Karaa and Zhang and the spatial third-order compact scheme of Note and Tan.     

A compact finite difference scheme for the fourth-order time-fractional integro-differential equation with a weakly singular kernel

In this paper, a compact finite difference scheme is constructed and investigated for the fourth-order time-fractional integro-differential equation with a weakly singular kernel. In the temporal direction, the Caputo derivative term is treated by means of L₁ discrete formula and the Riemann–Liouville fractional integral term is discretized by the second-order convolution quadrature rule. A fully discrete compact difference scheme is constructed with the space discretization by the fourth-order compact approximation. The stability and convergence are obtained by the discrete energy method, the Cholesky decomposition and the reduced-order method. Numerical experiments are presented to verify the theoretical analysis.     

Optimal monotonization of a high-order accurate bicompact scheme for the nonstationary multidimensional transport equation

A hybrid scheme is proposed for solving the nonstationary inhomogeneous transport equation. The hybridization procedure is based on two baseline schemes: (1) a bicompact one that is fourth-order accurate in all space variables and third-order accurate in time and (2) a monotone first-order accurate scheme from the family of short characteristic methods with interpolation over illuminated faces. It is shown that the first-order accurate scheme has minimal dissipation, so it is called optimal. The solution of the hybrid scheme depends locally on the solutions of the baseline schemes at each node of the space-time grid. A monotonization procedure is constructed continuously and uniformly in all mesh cells so as to keep fourth-order accuracy in space and third-order accuracy in time in domains where the solution is smooth, while maintaining a high level of accuracy in domains of discontinuous solution. Due to its logical simplicity and uniformity, the algorithm is well suited for supercomputer simulation.     

Fourth-order compact finite difference method for fourth-order nonlinear elliptic boundary value problems

A compact finite difference method with non-isotropic mesh is proposed for a two-dimensional fourth-order nonlinear elliptic boundary value problem. The existence and uniqueness of its solutions are investigated by the method of upper and lower solutions, without any requirement of the monotonicity of the nonlinear term. Three monotone and convergent iterations are provided for resolving the resulting discrete systems efficiently. The convergence and the fourth-order accuracy of the proposed method are proved. Numerical results demonstrate the high efficiency and advantages of this new approach.     

A high‐order finite difference discretization strategy based on extrapolation for convection diffusion equations

We propose a new high‐order finite difference discretization strategy, which is based on the Richardson extrapolation technique and an operator interpolation scheme, to solve convection diffusion equations. For a particular implementation, we solve a fine grid equation and a coarse grid equation by using a fourth‐order compact difference scheme. Then we combine the two approximate solutions and use the Richardson extrapolation to compute a sixth‐order accuracy coarse grid solution. A sixth‐order accuracy fine grid solution is obtained by interpolating the sixth‐order coarse grid solution using an operator interpolation scheme. Numerical results are presented to demonstrate the accuracy and efficacy of the proposed finite difference discretization strategy, compared to the sixth‐order combined compact difference (CCD) scheme, and the standard fourth‐order compact difference (FOC) scheme. © 2003 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 20: 18–32, 2004.     

New Sixth-Order Compact Schemes for Poisson/Helmholtz Equations

Some new sixth-order compact finite difference schemes for Poisson/Helmholtz equations on rectangular domains in both two- and three-dimensions are developed and analyzed. Different from a few sixth-order compact finite difference schemes in the literature, the finite difference and weight coefficients of the new methods have analytic simple expressions. One of the new ideas is to use a weighted combination of the source term at staggered grid points which is important for grid points near the boundary and avoids partial derivatives of the source term. Furthermore, the new compact schemes are exact for 2D and 3D Poisson equations if the solution is a polynomial less than or equal to 6. The coefficient matrices of the new schemes are $M$-matrices for Helmholtz equations with wave number $K≤0,$ which guarantee the discrete maximum principle and lead to the convergence of the new sixth-order compact schemes. Numerical examples in both 2D and 3D are presented to verify the effectiveness of the proposed schemes.