Dispersion analysis of numerical wave propagation and its computational consequences

We present in this paper a comparison of the dispersion properties for several finite-difference approximations of the acoustic wave equation. We investigate the compact and staggered schemes of fourth order accuracy in space and of second order or fourth order accuracy in time. We derive the computational cost of the simulation implied by a precision criterion on the numerical simulation (maximum allowed error in phase or group velocity). We conclude that for moderate accuracy the staggered scheme of second order in time is more efficient, whereas for very precise simulation the compact scheme of fourth order in time is a better choice. The comparison increasingly favors the lower order staggered scheme as the dimension increases. In three dimensional simulation, the cost of extremely precise simulation with any of the schemes is very large, whereas for simulation of moderate precision the staggered scheme is the least expensive.     

A Fourth Order Accurate Finite Difference Scheme for the Elastic Wave Equation in Second Order Formulation

We present a fourth order accurate finite difference method for the elastic wave equation in second order formulation, where the fourth order accuracy holds in both space and time. The key ingredient of the method is a boundary modified fourth order accurate discretization of the second derivative with variable coefficient, (??(x)u _x ) _x . This discretization satisfies a summation by parts identity that guarantees stability of the scheme. The boundary conditions are enforced through ghost points, thereby avoiding projections or penalty terms, which often are used with previous summation by parts operators. The temporal discretization is obtained by an explicit modified equation method. Numerical examples with free surface boundary conditions show that the scheme is stable for CFL-numbers up to 1.3, and demonstrate a significant improvement in efficiency over the second order accurate method. The new discretization of (??(x)u _x ) _x has general applicability, and will enable stable fourth order accurate approximations of other partial differential equations as well as the elastic wave equation.     

Finite Volume Approximation of One-Dimensional Stiff Convection-Diffusion Equations

In this work, we present a novel method to approximate stiff problems using a finite volume (FV) discretization. The stiffness is caused by the existence of a small parameter in the equation which introduces a boundary layer. The proposed semi-analytic method consists in adding in the finite volume space the boundary layer corrector which encompasses the singularities of the problem. We verify the stability and convergence of our finite volume schemes which take into account the boundary layer structures. A major feature of the proposed scheme is that it produces an efficient stable second order scheme to be compared with the usual stable upwind schemes of order one or the usual costly second order schemes demanding fine meshes.     

On the convergence of compact difference schemes

Difference schemes that are compact in space, i.e., schemes constructed on a two- or three-point stencil in each spatial direction, are more efficient and convenient for boundary condition formulation than other high-order accurate schemes. Originally, these schemes were developed primarily to obtain smooth solutions. In the last two decades, compact schemes have been actively used to compute gas dynamic flows with shock waves. However, when a numerical solution with guaranteed accuracy is desired, the actual properties of difference schemes have to be known in the calculation of solutions with discontinuities. For some widely used compact schemes, this issue has not yet been well studied. The properties of compact schemes constructed by the method of lines are examined in this paper. An initial-boundary value problem for the linear heat equation with discontinuous initial data is used as a test problem. In the method of lines, the spatial derivative in the heat equation is approximated on a two-point stencil according to a fourth-order accurate compact differentiation formula. The resulting evolution system of ordinary differential equations is solved using various implicit one-step two- and three-stage schemes of the second and third order of accuracy. The relation between the properties of the stability function of a scheme and the spatial monotonicity of the numerical solution is analyzed. In computations over long time intervals, the compact schemes are shown to be superior to traditional schemes based on the second-order accurate three-point approximation of the spatial derivative.     

An unconditional stable compact fourth-order finite difference scheme for three dimensional Allen–Cahn equation

In this paper, we present an unconditional stable linear high-order finite difference scheme for three dimensional Allen–Cahn equation. This scheme, which is based on a backward differentiation scheme combined with a fourth-order compact finite difference formula, is second order accurate in time and fourth order accurate in space. A linearly stabilized splitting scheme is used to remove the restriction of time step. We prove the unconditional stability of our proposed method in analysis. A fast and efficient linear multigrid solver is employed to solve the resulting discrete system. We perform various numerical experiments to confirm the high-order accuracy, unconditional stability and efficiency of our proposed method. In particular, we show two applications of our proposed method: triply-periodic minimal surface and volume inpainting.     

Using Distributed Computers to Deterministically Approximate Higher Dimensional Convection Diffusion Equations

A new approach to solving D> 3 spatial dimensional convection-diffusion equation on clusters of workstations is derived by exploiting the stability and scalability of the combination of a generalized D dimensional high-order compact (HOC) implicit finite difference scheme and parallelized GMRES(m). We then consider its application to multifactor Option pricing using the Black–Scholes equation and further show that an isotropic fourth order compact difference scheme is numerically stable and determine conditions under which its coefficient matrix is positive definite. The performance of GMRES(m) on distributed computers is limited by the inter-processor communication required by the matrix-vector multiplication. It is shown that the compact scheme requires approximately half the number of communications as a non-compact difference scheme of the same order of truncation error. As the dimensionality is increased, the ratio of computation that can be overlapped with communication also increases. CPU times and parallel efficiency graphs for single time step approximation of up to a 7D HOC scheme on 16 processors confirm the numerical stability constraint and demonstrate improved parallel scalability over non-compact difference schemes.     

Lod generalized trapezoidal formula schemes for parabolic differential equations in two space dimensions

We describe locally one-dimensional (LOD) time integration schemes for parabolic differential equations in two space dimensions, based on the generalized trapezoidal formulas (GTF(α)). We describe the schemes for the diffusion equation with Dirichlet and Neumann boundary conditions, for nonlinear reaction-diffusion equations, and for the convection-diffusion equation in two space dimensions. The obtained schemes are second order in time and unconditionally stable for all α ∈ [0, 1]. Numerical experiments are given to illustrate the obtained schemes and to compare their performance with the better known LOD Crank-Nicolson scheme. While the LOD Crank-Nicolson scheme can give unwanted oscillations in the computed solution, our present LOD-GTF(α) schemes provide both stable and accurate approximations for the true solution.     

Numerical analysis and physical simulations for the time fractional radial diffusion equation

We do the numerical analysis and simulations for the time fractional radial diffusion equation used to describe the anomalous subdiffusive transport processes on the symmetric diffusive field. Based on rewriting the equation in a new form, we first present two kinds of implicit finite difference schemes for numerically solving the equation. Then we strictly establish the stability and convergence results. We prove that the two schemes are both unconditionally stable and second order convergent with respect to the maximum norm. Some numerical results are presented to confirm the rates of convergence and the robustness of the numerical schemes. Finally, we do the physical simulations. Some interesting physical phenomena are revealed; we verify that the long time asymptotic survival probability ∝t^−α, but independent of the dimension, where α is the anomalous diffusion exponent.     

Numerical methods for two-dimensional parabolic inverse problem with energy overspecification

An inverse problem concerning the two-dimensional diffusion equation with source control parameter is considered. Four finite-difference schemes are presented for identifying the con- trol parameter which produces, at any given time, a desired energy distribution in a portion of the spatial domain. The fully explicit schemes developed for this purpose, are based on the (1,5) forward time centred space (FTCS) explicit formula, and the (1,9) FTCS scheme, are economical to use, are second-order and have bounded range of stability. Therange of stability for the 9-point finite difference scheme is less restrictive than the (1,5) FTCS formula. The fully implicit finite difference schemes employed, are based on the (5,1) backward time centred space (BTCS) formula, and the (5,5) Crank–Nicolson implicit scheme, which are unconditionally stable, but use more CPU times than the fully explicit techniques. The basis of analysis of the finite difference equation considered here is the modified equivalent partial differential equation approach, developed from the 1974 work of Warming and Hyeet. This allows direct and simple comparison of the errors associated with the equations as well as providing a means to develop more accurate finite difference methods. The results of numerical experiments are presented, and central processor (CPU) times needed for solving this inverse problem are reported.     

A new fourth-order difference scheme for solving an N-carrier system with Neumann boundary conditions

In this paper, a numerical method is developed to solve an N-carrier system with Neumann boundary conditions. First, we apply the compact finite difference scheme of fourth order for discretizing spatial derivatives at the interior points. Then, we develop a new combined compact finite difference scheme for the boundary, which also has fourth-order accuracy. Lastly, by using a Padé approximation method for the resulting linear system of ordinary differential equations, a new compact finite difference scheme is obtained. The present scheme has second-order accuracy in time direction and fourth-order accuracy in space direction. It is shown that the scheme is unconditionally stable. The present scheme is tested by two numerical examples, which show that the convergence rate with respect to the spatial variable from the new scheme is higher and the solution is much more accurate when compared with those obtained by using other previous methods.     

High-accuracy finite-difference methods for the valuation of options

A finite-difference scheme often employed for the valuation of options from the Black–Scholes equation is the Crank–Nicolson (CN) scheme. The CN scheme is second order in both time and asset. For a rapid valuation with a reasonable resolution of the option price curve, it requires extremely small steps in both time and asset. In this paper, we present high-accuracy finite-difference methods for the Black–Scholes equation in which we employ the fourth-order L-stable Simpson-type (LSIMP) time integration schemes developed earlier and the well-known Numerov method for discretization in the asset direction. The resulting schemes, called LSIMP–NUM, are fourth order in both time and asset. The LSIMP–NUM schemes obtained can provide a rapid, stable and accurate resolution of option prices, allowing for relatively large steps in both time and asset. We compare the computational efficiency of the LSIMP–NUM schemes with the CN and Douglas schemes by considering valuation of European options and American options via the linear complementarity approach.     

A linearly implicit conservative scheme for the fractional nonlinear Schrödinger equation with wave operator

The present work is mainly devoted to studying the fractional nonlinear Schrödinger equation with wave operator. We first derive two conserved quantities of the equation, and then develop a three-level linearly implicit difference scheme. This scheme is shown to be conserves the discrete version of conserved quantities. Using energy method, we prove that the difference scheme is unconditionally stable, and the difference solution converges to the exact one with second order accuracy in both the space and time dimensions. Numerical experiments are performed to support our theoretical analysis and demonstrate the accuracy, discrete conservation laws and effectiveness for long-time simulation.     

General finite difference approximation for the wave equation with variable coefficients using a cubic spline technique

General implicit finite difference approximations for the wave equation with variable coefficients in one and two space variables are derived by using a cubic spline function and continuous parameter approach. An optimal scheme of the family and high accuracy schemes due to McKee are obtained for special cases of the parameters. The stability of the schemes are discussed and one test example is solved to illustrate the theory.     

On Semi-implicit Splitting Schemes for the Beltrami Color Image Filtering

The Beltrami flow is an efficient nonlinear filter, that was shown to be effective for color image processing. The corresponding anisotropic diffusion operator strongly couples the spectral components. Usually, this flow is implemented by explicit schemes, that are stable only for very small time steps and therefore require many iterations. In this paper we introduce a semi-implicit Crank-Nicolson scheme based on locally one-dimensional (LOD)/additive operator splitting (AOS) for implementing the anisotropic Beltrami operator. The mixed spatial derivatives are treated explicitly, while the non-mixed derivatives are approximated in an implicit manner. In case of constant coefficients, the LOD splitting scheme is proven to be unconditionally stable. Numerical experiments indicate that the proposed scheme is also stable in more general settings. Stability, accuracy, and efficiency of the splitting schemes are tested in applications such as the Beltrami-based scale-space, Beltrami denoising and Beltrami deblurring. In order to further accelerate the convergence of the numerical scheme, the reduced rank extrapolation (RRE) vector extrapolation technique is employed.     

An Explicit Implicit Scheme for Cut Cells in Embedded Boundary Meshes

We present a new mixed explicit implicit time stepping scheme for solving the linear advection equation on a Cartesian cut cell mesh. We use a standard second-order explicit scheme on Cartesian cells away from the embedded boundary. On cut cells, we use an implicit scheme for stability. This approach overcomes the small cell problem—that standard schemes are not stable on the arbitrarily small cut cells—while keeping the cost fairly low. We examine several approaches for coupling the schemes in one dimension. For one of them, which we refer to as flux bounding, we can show a TVD result for using a first-order implicit scheme. We also describe a mixed scheme using a second-order implicit scheme and combine both mixed schemes by an FCT approach to retain monotonicity. In the second part of this paper, extensions of the second-order mixed scheme to two and three dimensions are discussed and the corresponding numerical results are presented. These indicate that this mixed scheme is second-order accurate in \(L^1\) and between first- and second-order accurate along the embedded boundary in two and three dimensions.     

A CCD-ADI method for two-dimensional linear and nonlinear hyperbolic telegraph equations with variable coefficients

In this paper, a combined compact finite difference method (CCD) together with alternating direction implicit (ADI) scheme is developed for two-dimensional linear and nonlinear hyperbolic telegraph equations with variable coefficients. The proposed CCD-ADI method is second-order accurate in time variable and sixth-order accurate in space variable. For the linear hyperbolic equation, the CCD-ADI method is shown to be unconditionally stable by using the Von Neumann stability analysis. Numerical results for both linear and nonlinear hyperbolic equations are presented to illustrate the high accuracy of the proposed method.     

Finite difference method for time-space-fractional Schrödinger equation

In this paper, an implicit finite difference scheme for the nonlinear time-space-fractional Schrödinger equation is presented. It is shown that the implicit scheme is unconditionally stable with experimental convergence order of O(τ^2?α+h²), where τ and h are time and space stepsizes, respectively, and α (0<α<1) is the fractional-order in time. In order to reduce the computational cost, the explicit–implicit scheme is proposed such that the nonlinear term is easily treated. Meanwhile, the implicit finite difference scheme for the coupled time-space-fractional Schrödinger system is also presented, which is unconditionally stable too. Numerical examples are given to support the theoretical analysis.     

High order spatial discretisations in electrochemical digital simulation. 2. Combination with the extrapolation algorithm

The application of fourth order discretisations of the second derivative of concentration with respect to distance from the electrode, in electrochemical digital simulations, is examined. In the bulk of the diffusion space, a central five-point scheme is used, and six-point asymmetric schemes are used at the edges. In this paper, the scheme is applied to the extrapolation technique, based on the backward implicit (BI) algorithm for temporal integration, which (with extrapolation) allows higher orders in time as well. The method is found to be stable, using both the von Neumann and matrix methods. Exceptional efficiency is obtained both for Cottrell and chronopotentiometry simulations, requiring as few as 3-5 steps in time, starting at the dimensionless time t = 0 to gain four-decimal accuracy at t = 1.     

High order spatial discretisations in electrochemical digital simulation. 2. Combination with the extrapolation algorithm

The application of fourth order discretisations of the second derivative of concentration with respect to distance from the electrode, in electrochemical digital simulations, is examined. In the bulk of the diffusion space, a central five-point scheme is used, and six-point asymmetric schemes are used at the edges. In this paper, the scheme is applied to the extrapolation technique, based on the backward implicit (BI) algorithm for temporal integration, which (with extrapolation) allows higher orders in time as well. The method is found to be stable, using both the von Neumann and matrix methods. Exceptional efficiency is obtained both for Cottrell and chronopotentiometry simulations, requiring as few as 3-5 steps in time, starting at the dimensionless time t = 0 to gain four-decimal accuracy at t = 1.     

Monotonic bicompact schemes for linear transport equations

The biocompact difference scheme earlier proposed by these authors for a linear transport equation, which has the fourth-order approximation in spatial coordinate on the two-point stencil and the first-order approximation in time, is monotonic. This implicit scheme is absolutely stable and can be solved by explicit formulas of a running calculation. On the basis of this scheme a monotone non-linear homogeneous difference scheme of high (third for smooth solutions) order accuracy in time is constructed. Calculations of test problems with discontinuous solutions have demonstrated that the proposed scheme has a significant advantage in accuracy over the known nonoscillatory schemes of high-order approximation.