Generalized trapezoidal formulas for parabolic equations

We investigate the application of the one-parameter family of generalized trapezoidal formulas (GTFs) introduced in Chawla et al. [2] for the time-integration of parabolic equations. The resulting GTF finite-difference schemes (GTF-FDS) are, in general, second order in both time and space and unconditionally stable. Interestingly, there exists a method of the family which is third order in time. Unlike the popular Crank -Nicolson scheme, our present GTF-FDS can cope with discontinuities in the boundary conditions and the initial conditions. We consider extensions of the GTF-FDS for equations with derivative boundary conditions and to a nonlinear problem. Numerical experiments demonstrate the superiority of the present GTF-FDS, especially for the case of problems with discontinuities in the boundary and the initial conditions.     

On the Connection Between the Correction and Weighting Functions in the Correction Procedure via Reconstruction Method

In this note, the connection between the correction and weighting functions for the correction procedure via reconstruction (CPR) method in 1D is addressed. A one-parameter family of weighting functions is constructed from the discontinuous test space. It is found that if the solution polynomials lie in the space P ^k , then the first k weighting functions can always be chosen as the basis of the polynomial space P ^k?1 and the last weighting function can be selected as a piece-wise continuous polynomial. There exists at least one set of weighting functions which can recover the energy stable flux reconstruction (ESFR) schemes. This strategy has been successfully applied to recover several known high-order discontinuous schemes, including DG, SD, SV, and Huynh??s g ₂ scheme.     

Tridiagonal solver-based L-stable one-step schemes for nonlinear parabolic equations

An attractive feature of the widely used Crank-Nicolson (C-N) scheme for parabolic equations is that it is a tridiagonal solver-based (TSB) scheme. But, in case of inconsistencies in the initial and boundary conditions or when the ratio of temporal to spatial steplengths is large, it can produce unwanted oscillations or an unacceptable solution. As alternative to C-N, Chawla et al. [2, 3] introduced L-stable generalized trapezoidal formulas (GTF(α)) which can give a more acceptable solution by a judicious choice of the parameter α; however, GTF are not TSB schemes. It is natural to ask for L-stable TSB schemes. In the present paper, we first introduce a one-parameter family of generalized midpoint formulas (GMF(α)); again GMF are not TSB schemes. We then introduce a two-parameter family through a linear combination of the GMF and the classical trapezoidal formula, and show the existence of a one-parameter subfamily of L-stable TSB schemes; these schemes are unconditionally stable. The computational performance of the obtained schemes is compared with the C-N scheme by considering a nonlinear reaction-diffusion equation.     

On the lack of convergence of unconditionally stable explicit rational runge-kutta schemes

The poor performance of the rational Runge-Kutta (RRK) schemes of Hairer [2,3] are investigated. By considering two simple model problems, it is demonstrated that this poor performance is in fact due to a lack of convergence. A conceptual model of an unconditionally stable implicit-explicit time-integration scheme is also considered. With the aid of this model, it is possible to establish necessary bounds on the extent of the explicit region for convergence. This demonstrates the limited applicability of such hybrid time-integration 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.     

Stability of a saddle node bifurcation under numerical approximations

In this paper, we show that the solution flows generated by a one-parameter family of ordinary differential equations are stable under their numerical approximations in a vicinity of a saddle node. Our result sharpens the one in [¹] and the proof is adapted from the method of Sotomayor in [^{2. and 3.}].     

Generalized Trapezoidal Formulas for the Symmetric Heat Equation in Polar Coordinates

This paper has two objectives. We first describe one-step time integration schemes for the symmetric heat equation in polar coordinates: u t = v ( u rr +( a / r ) u r ) based on the generalized trapezoidal formulas (GTF( f ) of Chawla et al. [2]. This includes the case of cylindrical symmetry for a =1 and of spherical symmetry for a =2. The obtained GTF( f ) time integration schemes are second order in time and unconditionally stable. We then introduce generalized finite Hankel transforms to obtain an analytical solution of the heat equation for all a S 1, with Dirichlet and Neumann type boundary conditions. Numerical experiments are provided to compare the accuracy and stability of the obtained GTF( f ) time integration schemes with the schemes based on the backward Euler, the classical arithmetic-mean trapezoidal formula and a third order time integration scheme.     

New Analysis of the Du Fort–Frankel Methods

In 1953 Du Fort and Frankel (Math. Tables Other Aids Comput., 7(43):135?C152, 1953) proposed to solve the heat equation u _t =u _xx using an explicit scheme, which they claim to be unconditionally stable, with a truncation error is of order of $\tau= O({{k}}^{2}+{{h}}^{2}+\frac{{{k}}^{2}}{{{h}}^{2}})$ . Therefore, it is not consistent when k=O(h). In the analysis presented below we show that the Du Fort?CFrankel schemes are not unconditionally stable. However, when properly defined, the truncation error vanishes as h,k??0.     

Alternating group explicit method with exponential-type for the diffusion–convection equation

Based on the semi-explicit asymmetric exponential schemes constructed by the author, a new alternating group explicit (AGE) method with exponential-type for the numerical solution of the convection–diffusion equation is derived in the paper. The method has the obvious property of parallelism and is unconditionally stable. The results of numerical examples are given to show the effectiveness of the present methods that are in preference to the Evans and Abdullah' method in [Evans, D.J. and Abdullah, A.R., 1985, A new explicit method for the diffusion–convection equation. Computers & Mathematics with Application, 11, 145–154].     

Le cylindre des langages linéaires

Define a cylinder to be a family of languages which is closed under inverse homomorphisms and intersection with regular sets. A number of well-known families of languages are cylinders:

—CFL, the family of context-free languages, is a principal cylinder, i.e. the smallest cylinder containing a languageL _O described in [6].

—the family of deterministic context-free languages is proved to be a nonprincipal cylinder in [7].

—the family of unambiguous context-free languages is a cylinder: to prove that it is not principal seems to be a very hard problem.

In this paper we prove that Lin, the family of linear context-free languages, is a nonprincipal cylinder. This is achieved in the standard way by exhibiting a sequence of languages S_n, n∈N, such that Lin is the union of all the principal cylinders generated by these languages and is not the union of any finite number of these cylinders. This leaves open the problem raised by Sheila Greibach of whether there exists a languageL such that every linear context-free language is the image ofL in some inverse gsm mapping.     

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.     

A(α)-stable cyclic composite multistep methods of order 5

We describe a newA(α)-stable 3-cyclic 3-step method with accuracy of orderP=5. This is in contrast to the originally developed methods [5] which have greater order of accuracy (P=6) but a small stability region. Moreover, the new method shows slightly better stability than the backward differentiation formula (BDF) [6] of the same order.     

Arbitrary high order PNPM schemes on unstructured meshes for the compressible Navier-Stokes equations

In this paper, we propose a new unified family of arbitrary high order accurate explicit one-step finite volume and discontinuous Galerkin schemes on unstructured triangular and tetrahedral meshes for the solution of the compressible Navier-Stokes equations. This new family of numerical methods has first been proposed in [16] for purely hyperbolic systems and has been called P_NP_M schemes, where N indicates the polynomial degree of the test functions and M is the degree of the polynomials used for flux and source computation. A particular feature of the general P_NP_M schemes is that they contain classical high order accurate finite volume schemes (N=0) as well as standard discontinuous Galerkin methods (M=N) just as special cases, which therefore allows for a direct efficiency comparison.In the application section of this paper we first show numerical convergence results on unstructured meshes obtained for the compressible Navier-Stokes equations with Sutherland’s viscosity law, comparing all third to sixth order accurate P_NP_M schemes with each other. In order to validate the method also in practice we show several classical steady and unsteady CFD applications, such as the laminar boundary layer flow over a flat plate at high Reynolds numbers, flow past a NACA0012 airfoil, the unsteady flows past a circular cylinder and a sphere, the unsteady flows of a compressible mixing layer in two space dimensions and finally we also show applications to supersonic flows with shock Mach numbers up to M_s=10.     

Time discretized operators. Part 2: towards the theoretical design of a new generation of a generalized family of unconditionally stable implicit and explicit representations of arbitrary order for computational dynamics

The new generation of a generalized family of time discretized operators encompassing implicit and explicit representations that are unconditionally stable and which theoretically inherit Nth-order time accurate features developed in Part 1 are restricted here in Part 2 of the exposition to second-order time accurate operators. As such, unconditionally stable implicit representations are first described followed by unconditionally stable explicit representations. The theoretical design leading to computational algorithms with excellent algorithmic attributes for applicability to practical situations are also addressed for both the implicit and explicit unconditionally stable representations of time discretized operators. Attention is first focused on linear problems and extensions to nonlinear situations are subsequently briefly addressed.     

Unconditionally stable algorithms for quasi-static elasto/visco-plastic finite element analysis

A new one-parameter family of implicit algorithms for quasi-static elasto/visco-plastic finite element analysis is proposed. For appropriate values of the parameter, the algorithms are shown to be unconditionally stable. Numerical tests in confirmation of the theory are presented.     

ADER schemes on unstructured meshes for nonconservative hyperbolic systems: Applications to geophysical flows

We develop a new family of well-balanced path-conservative quadrature-free one-step ADER finite volume and discontinuous Galerkin finite element schemes on unstructured meshes for the solution of hyperbolic partial differential equations with non-conservative products and stiff source terms. The fully discrete formulation is derived using the recently developed framework of explicit one-step P_NP_M schemes of arbitrary high order of accuracy in space and time for conservative hyperbolic systems [Dumbser M, Balsara D, Toro EF, Munz CD. A unified framework for the construction of one-step finite-volume and discontinuous Galerkin schemes. J Comput Phys 2008;227:8209–53]. The two key ingredients of our high order approach are: first, the high order accurate P_NP_M reconstruction operator on unstructured meshes, using the WENO strategy presented in [Dumbser M, Käser M, Titarev VA Toro EF. Quadrature-free non-oscillatory finite volume schemes on unstructured meshes for nonlinear hyperbolic systems. J Comput Phys 2007;226:204–43] to ensure monotonicity at discontinuities, and second, a local space–time Galerkin scheme to predict the evolution of the reconstructed polynomial data inside each element during one time step to obtain a high order accurate one-step time discretization. This approach is also able to deal with stiff source terms as shown in [Dumbser M, Enaux C, Toro EF. Finite volume schemes of very high order of accuracy for stiff hyperbolic balance laws. J Comput Phys 2008;227:3971–4001]. These two key ingredients are combined with the recently developed path-conservative methods of Parés [Parés C. Numerical methods for nonconservative hyperbolic systems: a theoretical framework. SIAM J Numer Anal 2006;44:300–21] and Castro et al. [Castro MJ, Gallardo JM, Parés C. High-order finite volume schemes based on reconstruction of states for solving hyperbolic systems with nonconservative products. Applications to shallow-water systems. Math Comput 2006;75:1103–34] to treat the non-conservative products properly. We show applications of our method to the two-layer shallow water equations as well as applications to the recently published depth-averaged two-fluid flow model of Pitman and Le [Pitman EB, Le L. A two-fluid model for avalanche and debris flows. Philos Trans Roy Soc A 2005;363:1573–601].     

On stable and explicit numerical methods for the advection–diffusion equation

In this paper two stable and explicit numerical methods to integrate the one-dimensional (1D) advection–diffusion equation are presented. These schemes are stable by design and follow the main general concept behind the semi-Lagrangian method by constructing a virtual grid where the explicit method becomes stable. It is shown that the new schemes compare well with analytic solutions and are often more accurate than implicit schemes. In particular, the diffusion-only case is explored in some detail. The error produced by the stable and explicit method is a function of the ratio between the standard deviation σ₀ of the initial Gaussian state and the characteristic virtual grid distance ΔS. Larger values of this ratio lead to very accurate results when compared to implicit methods, while lower values lead to less accuracy. It is shown that the σ₀/ΔS ratio is also significant in the advection–diffusion problem: it determines the maximum error generated by new methods, obtained with a certain combination of the advection and diffusion values. In addition, the error becomes smaller when the problem becomes more advective or more diffusive.     

Implicit space–time residual distribution method for unsteady laminar viscous flow

The class of multidimensional upwind residual distribution (RD) schemes has been developed in the past decades as an attractive alternative to the finite volume (FV) and finite element (FE) approaches. Although they have shown superior performances in the simulation of steady two-dimensional and three-dimensional inviscid and viscous flows, their extension to the simulation of unsteady flow fields is still a topic of intense research [ICCFD2, International Conference on Computational Fluid Dynamics 2, Sydney, Australia, 15–19 July 2002; M. Mezine, R. Abgrall, Upwind multidimensional residual schemes for steady and unsteady flows].Recently the space–time RD approach has been developed by several researchers [Int. J. Numer. Methods Fluids 40 (2002) 573; J. Comput. Phys. 188 (2003) 16; Á.G. Csı́k, Upwind residual distribution schemes for general hyperbolic conservation laws and application to ideal magnetohydrodynamics, PhD thesis, Katholieke Universiteit Leuven, 2002; J. Comput. Phys. 188 (2003) 16; R. Abgrall; M. Mezine, Construction of second order accurate monotone and stable residual distribution schemes for unsteady flow problems] which allows to perform second order accurate unsteady inviscid computations. In this paper we follow the work done in [Int. J. Numer. Methods Fluids 40 (2002) 573; Á.G. Csı́k, Upwind residual distribution schemes for general hyperbolic conservation laws and application to ideal magnetohydrodynamics, PhD thesis, Katholieke Universiteit Leuven, 2002]. In this approach the space–time domain is discretized and solved as a (d+1)-dimensional problem, where d is the number of space dimensions. In [Int. J. Numer. Methods Fluids 40 (2002) 573; Á.G. Csı́k, Upwind residual distribution schemes for general hyperbolic conservation laws and application to ideal magnetohydrodynamics, PhD thesis, Katholieke Universiteit Leuven, 2002] it is shown that thanks to the multidimensional upwinding of the RD method, the solution of the unsteady problem can be decoupled into sub-problems on space–time slabs composed of simplicial elements, allowing to obtain a true time marching procedure. Moreover, the method is implicit and unconditionally stable for arbitrary large time-steps if positive RD schemes are employed.We present further development of the space–time approach of [Int. J. Numer. Methods Fluids 40 (2002) 573; Á.G. Csı́k, Upwind residual distribution schemes for general hyperbolic conservation laws and application to ideal magnetohydrodynamics, PhD thesis, Katholieke Universiteit Leuven, 2002] by extending it to laminar viscous flow computations. A Petrov–Galerkin treatment of the viscous terms [Project Report 2002-06, von Karman Institute for Fluid Dynamics, Belgium, 2002; J. Dobeš, Implicit space–time method for laminar viscous flow], consistent with the space–time formulation has been investigated, implemented and tested. Second order accuracy in both space and time was observed on unstructured triangulation of the spatial domain.The solution is obtained at each time-step by solving an implicit non-linear system of equations. Here, following [Int. J. Numer. Methods Fluids 40 (2002) 573; Á.G. Csı́k, Upwind residual distribution schemes for general hyperbolic conservation laws and application to ideal magnetohydrodynamics, PhD thesis, Katholieke Universiteit Leuven, 2002], we formulate the solution of this system as a steady state problem in a pseudo-time variable. We discuss the efficiency of an explicit Euler forward pseudo-time integrator compared to the implicit Euler. When applied to viscous computation, the implicit method has shown speed-ups of more than a factor 50 in terms of computational time.     

Generalized trapezoidal formulas for the black–scholes equation of option pricing

For the celebrated Black–Scholes parabolic equation of option pricing, we present new time integration schemes based on the generalized trapezoidal formulas introduced by Chawla et al. [3]. The resulting GTF(α) schemes are unconditionally stable and second order in both space and time. Interestingly, since the Black–Scholes equation is linear, GTF (1/3) attains order three in time. The computational performance of the obtained schemes is compared with the Crank–Nicolson scheme for the case of European option valuation. Since the payoff is nondifferentiable having a “corner” on expiry at the exercise price, the classical trapezoidal formula used in the Crank–Nicolson scheme can experience oscillations at this corner. It is demonstrated that our present GTF (1/3) scheme can cope with this situation and performs consistently superior than the Crank–Nicolson scheme.     

Fourth-order runge-kutta schemes for fluid mechanics applications

Multiple high-order time-integration schemes are used to solve stiff test problems related to the Navier-Stokes (NS) equations. The primary objective is to determine whether high-order schemes can displace currently used second-order schemes on stiff NS and Reynolds averaged NS (RANS) problems, for a meaningful portion of the work-precision spectrum. Implicit-Explicit (IMEX) schemes are used on separable problems that naturally partition into stiff and nonstiff components. Non-separable problems are solved with fully implicit schemes, oftentimes the implicit portion of an IMEX scheme. The convection-diffusion-reaction (CDR) equations allow a term by term stiff/nonstiff partition that is often well suited for IMEX methods. Major variables in CDR converge at near design-order rates with all formulations, including the fourth-order IMEX additive Runge-Kutta (ARK₂) schemes that are susceptible to order reduction. The semi-implicit backward differentiation formulae and IMEX ARK₂ schemes are of comparable efficiency. Laminar and turbulent aerodynamic applications require fully implicit schemes, as they are not profitably partitioned. All schemes achieve design-order convergence rates on the laminar problem. The fourth-order explicit singly diagonally implicit Runge-Kutta (ESDIRK4) scheme is more efficient than the popular second-order backward differentiation formulae (BDF2) method. The BDF2 and fourth-order modified extended backward differentiation formulae (MEBDF4) schemes are of comparable efficiency on the turbulent problem. High precision requirements slightly favor the MEBDF4 scheme (greater than three significant digits). Significant order reduction plagues the ESDIRK4 scheme in the turbulent case. The magnitude of the order reduction varies with Reynolds number. Poor performance of the high-order methods can partially be attributed to poor solver performance. Huge time steps allowed by high-order formulations challenge the capabilities of algebraic solver technology.