Fourth-Order Splitting Methods for Time-Dependant Differential Equations

This study was suggested by previous work on the simulation of evolution equations with scale-dependent processes,e.g.,wave-propagation or heat-transfer,that are modeled by wave equations or heat equations.Here,we study both parabolic and hyperbolic equations.We focus on ADI (alternating direction implicit) methods and LOD (locally one-dimensional) methods,which are standard splitting methods of lower order,e.g.second-order.Our aim is to develop higher-order ADI methods,which are performed by Richardson extrapolation,Crank-Nicolson methods and higher-order LOD methods,based on locally higher-order methods.We discuss the new theoretical results of the stability and consistency of the ADI methods.The main idea is to apply a higher- order time discretization and combine it with the ADI methods.We also discuss the dis- cretization and splitting methods for first-order and second-order evolution equations. The stability analysis is given for the ADI method for first-order time derivatives and for the LOD (locally one-dimensional) methods for second-order time derivatives.The higher-order methods are unconditionally stable.Some numerical experiments verify our results.     

Implicit numerical method for computing three-dimensional rarefied gas flows on unstructured meshes

The method based on the numerical solution of a model kinetic equation is proposed for analyzing three-dimensional rarefied gas flows. The basic idea behind the method is the use of a second-order accurate TVD scheme on hybrid unstructured meshes in physical space and a fast implicit time discretization method without iterations at the upper level. The performance of the method is illustrated by computing test examples of three-dimensional rarefied gas flows in variously shaped channels in a wide range of Knudsen numbers.     

Solitary waves of the EW and RLW equations

Eight finite difference methods are employed to study the solitary waves of the equal-width (EW) and regularized long–wave (RLW) equations. The methods include second-order accurate (in space) implicit and linearly implicit techniques, a three-point, fourth-order accurate, compact operator algorithm, an exponential method based on the local integration of linear, second-order ordinary differential equations, and first- and second-order accurate temporal discretizations. It is shown that the compact operator method with a Crank–Nicolson discretization is more accurate than the other seven techniques as assessed for the three invariants of the EW and RLW equations and the L₂-norm errors when the exact solution is available. It is also shown that the use of Gaussian initial conditions may result in the formation of either positive or negative secondary solitary waves for the EW equation and the formation of positive solitary waves with or without oscillating tails for the RLW equation depending on the amplitude and width of the Gaussian initial conditions. In either case, it is shown that the creation of the secondary wave may be preceded by a steepening and an narrowing of the initial condition. The creation of a secondary wave is reported to also occur in the dissipative RLW equation, whereas the effects of dissipation in the EW equation are characterized by a decrease in amplitude, an increase of the width and a curving of the trajectory of the solitary wave. The collision and divergence of solitary waves of the EW and RLW equations are also considered in terms of the wave amplitude and the invariants of these equations.     

A numerical model for the trans-membrane voltage of vesicles

The Immersed Interface Method is employed to solve the time-varying electric field equations around a three-dimensional vesicle. To achieve second-order accuracy the implicit jump conditions for the electric potential, up to the second normal derivative, are derived. The trans-membrane potential is determined implicitly as part of the algorithm. The method is compared to an analytic solution based on spherical harmonics and verifies the second-order accuracy of the underlying discretization even in the presence of solution discontinuities. A sample result for an elliptic interface is also presented.     

Convergence and stability of finite element nonlinear Galerkin method for the Navier-Stokes equations

In this article, we present a new fully discrete finite element nonlinear Galerkin method, which are well suited to the long time integration of the Navier-Stokes equations. Spatial discretization is based on two-grid finite element technique; time discretization is based on Euler explicit scheme with variable time step size. Moreover, we analyse the boundedness, convergence and stability condition of the finite element nonlinear Galerkin method. Our discussion shows that the time step constraints of the method depend only on the coarse grid parameter and the time step constraints of the finite element Galerkin method depend on the fine grid parameter under the same convergence accuracy. Received February 2, 1994 / Revised version received December 6, 1996     

On parallel algorithms for semidiscretized parabolic partial differential equations based on subdiagonal Padé approximations

It is well known that methods for solving semidiscretized parabolic partial differential equations based on the second-order diagonal [1/1] Padé approximation (the Crank–Nicolson or trapezoidal method) can produce poor numerical results when a time discretization is imposed with steps that are “too large” relative to the spatial discretization. A monotonicity property is established for all diagonal Padé approximants from which it is shown that corresponding higher-order methods suffer a similar time step restriction as the [1/1] Padé. Next, various high-order methods based on subdiagonal Padé approximations are presented which, through a partial fraction expansion, are no more complicated to implement than the first-order implicit Euler method based on the [0/1] Padé approximation; moreover, the resulting algorithms are free of a time step restriction intrinsic to those based on diagonal Padé approximations. Numerical results confirm this when various test problems from the literature are implemented on a Multiple Instruction Multiple Data (MIMD) machine such as an Alliant FX/8. © 1993 John Wiley & Sons, Inc.     

Fully Discrete Error Estimation by the Method of Lines for a Nonlinear Parabolic Problem

A posteriori error estimates for a nonlinear parabolic problem are introduced. A fully discrete scheme is studied. The space discretization is based on a concept of hierarchical finite element basis functions. The time discretization is done using singly implicit Runge-Kutta method (SIRK). The convergence of the effectivity index is proven.     

An Extrapolated Second Order Backward Difference Time-Stepping Scheme for the Magnetohydrodynamics System

In this article, we introduce a fully implicit, linearly extrapolated second-order backward difference time-stepping scheme for solving a time dependent non-homogeneous magnetohydrodynamic system for electrically conducting fluids. The extrapolated time-stepping scheme is used for time discretization and the mixed finite element method is used for spatial discretization. We first prove unconditional energetic stability without introducing an undesirable exponential Gronwall constant. Complete error analysis is provided without assuming any stability condition or restrictions on the time-step size. Numerical experiments are presented to confirm the theoretical convergence results and efficiency of the scheme.     

A framework for polynomial preconditioners based on fast transforms II: PDE applications

The solution of systems of equations arising from systems of time-dependent partial differential equations (PDEs) is considered. Primarily, first-order PDEs are studied, but second-order derivatives are also accounted for. The discretization is performed using a general finite difference stencil in space and an implicit method in time. The systems of equations are solved by a preconditioned Krylov subspace method. The preconditioners exploit optimal and superoptimal approximations by low-degree polynomials in a normal basis matrix, associated with a fast trigonometric transform. Numerical experiments for high-order accurate discretizations are presented. The results show that preconditioners based on fast transforms yield efficient solution algorithms, even for large quotients between the time and space steps. Utilizing a spatial grid ratio less than one, the arithmetic work per grid point is bounded by a constant as the number of grid points increases. This research was supported by the Swedish National Board for Industrial and Technical Development (NUTEK) and by the U.S. National Science Foundation under grant ASC-8958544.     

Résolution d'EDP par un schéma en temps «pararéel »

The purpose of this Note is to propose a time discretization of a partial differential evolution equation that allows for parallel implementations. The method, based on an Euler scheme, combines coarse resolutions and independent fine resolutions in time in the same spirit as standard spacial approximations. The resulting parallel implementation is done in the non standard time direction. Its main goal concerns real time problems, hence the proposed terminology of “parareal” algorithm.     

Two-time level ADI finite volume method for a class of second-order hyperbolic problems

In this paper, we develop a two-time level alternating direction implicit (ADI) method for a class of second-order hyperbolic problems on a rectangular domain. The method builds on the finite volume method with biquadratic basis functions for the discretization in space, and a Crank-Nicolson approach for the time stepping. We obtain a second-order error estimation in the H¹ norm. Numerical experiments are performed to demonstrate the theoretical findings.     

A reduced FE formulation based on POD method for hyperbolic equations

A proper orthogonal decomposition (POD) method was successfully used in the reduced-order modeling of complex systems. In this paper, we extend the applications of POD method, namely, apply POD method to a classical finite element (FE) formulation for second-order hyperbolic equations with real practical applied background, establish a reduced FE formulation with lower dimensions and high enough accuracy, and provide the error estimates between the reduced FE solutions and the classical FE solutions and the implementation of algorithm for solving reduced FE formulation so as to provide scientific theoretic basis for service applications. Some numerical examples illustrate the fact that the results of numerical computation are consistent with theoretical conclusions. Moreover, it is shown that the reduced FE formulation based on POD method is feasible and efficient for solving FE formulation for second-order hyperbolic equations.     

A higher order uniformly convergent method for singularly perturbed parabolic turning point problems

In this article, we study numerical approximation for a class of singularly perturbed parabolic (SPP) convection-diffusion turning point problems. The considered SPP problem exhibits a parabolic boundary layer in the neighborhood of one of the sides of the domain. Some a priori bounds are given on the exact solution and its derivatives, which are necessary for the error analysis. A numerical scheme comprising of implicit finite difference method for time discretization on a uniform mesh and a hybrid scheme for spatial discretization on a generalized Shishkin mesh is proposed. Then Richardson extrapolation method is applied to increase the order of convergence in time direction. The resulting scheme has second-order convergence up to a logarithmic factor in space and second-order convergence in time. Numerical experiments are conducted to demonstrate the theoretical results and the comparative study is done with the existing schemes in literature to show better accuracy of the proposed 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 robust and accurate finite difference method for a generalized Black-Scholes equation

In this paper we present a numerical method for a generalized Black-Scholes equation, which is used for option pricing. The method is based on a central difference spatial discretization on a piecewise uniform mesh and an implicit time stepping technique. Our scheme is stable for arbitrary volatility and arbitrary interest rate, and is second-order convergent with respect to the spatial variable. Furthermore, the present paper efficiently treats the singularities of the non-smooth payoff function. Numerical results support the theoretical results.     

Nonlinear Galerkin methods and mixed finite elements: two-grid algorithms for the Navier-Stokes equations

Summary. A nonlinear Galerkin method using mixed finite elements is presented for the two-dimensional incompressible Navier-Stokes equations. The scheme is based on two finite element spaces and for the approximation of the velocity, defined respectively on one coarse grid with grid size and one fine grid with grid size and one finite element space for the approximation of the pressure. Nonlinearity and time dependence are both treated on the coarse space. We prove that the difference between the new nonlinear Galerkin method and the standard Galerkin solution is of the order of $H^2$, both in velocity ( and pressure norm). We also discuss a penalized version of our algorithm which enjoys similar properties. Received October 5, 1993 / Revised version received November 29, 1993     

A Two-Grid Finite Element Approximation for Nonlinear Time Fractional Two-Term Mixed Sub-Diffusion and Diffusion Wave Equations

In this paper, we develop a two-grid method (TGM) based on the FEM for 2D nonlinear time fractional two-term mixed sub-diffusion and diffusion wave equations. A two-grid algorithm is proposed for solving the nonlinear system, which consists of two steps: a nonlinear FE system is solved on a coarse grid, then the linearized FE system is solved on the fine grid by Newton iteration based on the coarse solution. The fully discrete numerical approximation is analyzed, where the Galerkin finite element method for the space derivatives and the finite difference scheme for the time Caputo derivative with order $\alpha\in(1,2)$ and $\alpha_{1}\in(0,1)$. Numerical stability and optimal error estimate $O(h^{r+1}+H^{2r+2}+\tau^{\min\{3-\alpha,2-\alpha_{1}\}})$ in $L^{2}$-norm are presented for two-grid scheme, where $t,$ $H$ and $h$ are the time step size, coarse grid mesh size and fine grid mesh size, respectively. Finally, numerical experiments are provided to confirm our theoretical results and effectiveness of the proposed algorithm.     

A spectral element method using the modal basis and its application in solving second‐order nonlinear partial differential equations

We present a high‐order spectral element method (SEM) using modal (or hierarchical) basis for modeling of some nonlinear second‐order partial differential equations in two‐dimensional spatial space. The discretization is based on the conforming spectral element technique in space and the semi‐implicit or the explicit finite difference formula in time. Unlike the nodal SEM, which is based on the Lagrange polynomials associated with the Gauss–Lobatto–Legendre or Chebyshev quadrature nodes, the Lobatto polynomials are used in this paper as modal basis. Using modal bases due to their orthogonal properties enables us to exactly obtain the elemental matrices provided that the element‐wise mapping has the constant Jacobian. The difficulty of implementation of modal approximations for nonlinear problems is treated in this paper by expanding the nonlinear terms in the weak form of differential equations in terms of the Lobatto polynomials on each element using the fast Fourier transform (FFT). Utilization of the Fourier interpolation on equidistant points in the FFT algorithm and the enough polynomial order of approximation of the nonlinear terms can lead to minimize the aliasing error. Also, this approach leads to finding numerical solution of a nonlinear differential equation through solving a system of linear algebraic equations. Numerical results for some famous nonlinear equations illustrate efficiency, stability and convergence properties of the approximation scheme, which is exponential in space and up to third‐order in time. Copyright © 2014 John Wiley & Sons, Ltd.     

Runge-Kutta methods without order reduction for linear initial boundary value problems

Summary. It is well-known the loss of accuracy when a Runge–Kutta method is used together with the method of lines for the full discretization of an initial boundary value problem. We show that this phenomenon, called order reduction, is caused by wrong boundary values in intermediate stages. With a right choice, the order reduction can be avoided and the optimal order of convergence in time is achieved. We prove this fact for time discretizations of abstract initial boundary value problems based on implicit Runge–Kutta methods. Moreover, we apply these results to the full discretization of parabolic problems by means of Galerkin finite element techniques. We present some numerical examples in order to confirm that the optimal order is actually achieved. Received July 10, 2000 / Revised version received March 13, 2001 / Published online October 17, 2001     

Multigrid Methods with Newton-Gauss-Seidel Smoothing and Constraint Preserving Interpolation for Obstacle Problems

In this paper, we propose a multigrid algorithm based on the full approximate scheme for solving the membrane constrained obstacle problems and the minimal surface obstacle problems in the formulations of HJB equations. A Newton-Gauss-Seidel (NGS) method is used as smoother. A Galerkin coarse grid operator is proposed for the membrane constrained obstacle problem. Comparing with standard FAS with the direct discretization coarse grid operator, the FAS with the proposed operator converges faster. A special prolongation operator is used to interpolate functions accurately from the coarse grid to the fine grid at the boundary between the active and inactive sets. We will demonstrate the fast convergence of the proposed multigrid method for solving two model obstacle problems and compare the results with other multigrid methods.