BDDC preconditioning for high-order Galerkin Least-Squares methods using inexact solvers

A high-order Galerkin Least-Squares (GLS) finite element discretization is combined with a Balancing Domain Decomposition by Constraints (BDDC) preconditioner and inexact local solvers to provide an efficient solution technique for large-scale, convection-dominated problems. The algorithm is applied to the linear system arising from the discretization of the two-dimensional advection–diffusion equation and Euler equations for compressible, inviscid flow. A Robin–Robin interface condition is extended to the Euler equations using entropy-symmetrized variables. The BDDC method maintains scalability for the high-order discretization of the diffusion-dominated flows, and achieves low iteration count in the advection-dominated regime. The BDDC method based on inexact local solvers with incomplete factorization and p = 1 coarse correction maintains the performance of the exact counterpart for the wide range of the Peclet numbers considered while at significantly reduced memory and computational costs.     

Examination of characteristics method with cubic interpolation for advection–diffusion equation

In this study, the use of the characteristics method integrated with the Hermite cubic interpolation or the cubic-spline interpolation on the space line or the time line, i.e., the HCSL scheme, the CSSL scheme, the HCTL scheme, and the CSTL scheme, respectively, for solving the advection–diffusion equation is examined. The advection and diffusion of a Gaussian concentration distribution in a uniform flow with constant diffusion coefficient is used to conduct this investigation. The effects of parameters, such as Peclet number, Courant number, and the reachback number, on these four schemes used herein for solving the advection–diffusion equation are investigated. The simulated results show that the CSSL scheme is comparable to the HCSL scheme, and the two schemes seem insensitive to Courant number as compared with the HCTL scheme and the CSTL scheme. With large Peclet number, for small Courant number the HCTL scheme is more accurate than the HCSL scheme and the CSSL scheme. However, for large Courant number the HCTL scheme has worse computed results in comparison with the HCSL scheme and the CSSL scheme. With small Peclet number, the HCTL scheme, the HCSL scheme, and the CSSL scheme have close simulated results. Despite Peclet number, for small Courant number the CSTL scheme is comparable to the HCTL scheme, but for large Courant number the former scheme provides unacceptable simulated results in which very large numerical diffusion is induced due to the effect of the natural endpoint constraint. For large Peclet number the HCSL scheme and the CSSL scheme integrated with the reachback technique can improve simulated results, but for small Peclet number the HCSL scheme and the CSSL scheme seem not to be influenced by increasing the reachback number.     

Domain decomposition algorithm based on the group explicit formula for the heat equation

A finite difference domain decomposition algorithm (DDA) for solving the heat equation in parallel is presented. In this procedure, interface values between subdomains are calculated by the group explicit formula, whereas interior values of subdomains are determined by the classical implicit scheme. The stability and convergence for this DDA are proved. The stability bound of the procedure is derived to be eight times that of the classical explicit scheme. Though the truncation error at the interface is O(τ?+?h), L ²-error is proved to be O(τ?+?h ²). Numerical examples confirm the second-order convergence and indicate that the stability condition is sharp. A comparison of the numerical errors of this procedure with other known methods is also included.     

Implementation of convolutional perfectly matched layer for three‐dimensional hybrid implicit‐explicit finite‐difference time‐domain method

The hybrid implicit‐explicit (HIE) finite‐difference time‐domain (FDTD) method with the convolutional perfectly matched layer (CPML) is extended to a full three‐dimensional scheme in this article. To demonstrate the application of the CPML better, the entire derivation process is presented, in which the fine scale structure is changed from y‐direction to z‐direction of the propagation innovatively. The numerical examples are adopted to verify the efficiency and accuracy of the proposed method. Numerical results show that the HIE‐FDTD with CPML truncation has the similar relative reflection error with the FDTD with CPML method, but it is much better than the methods with Mur absorbing boundary. Although Courant‐Friedrich‐Levy number climbs to 8, the maximum relative error of the proposed HIE‐CPML remains more below than ?71 dB, and CPU time is nearly 72.1% less than the FDTD‐CPML. As an example, a low‐pass filter is simulated by using the FDTD‐CPML and HIE‐CPML methods. The curves obtained are highly fitted between two methods; the maximum errors are lower than ?79 dB. Furthermore, the CPU time saved much more, accounting for only 26.8% of the FDTD‐CPML method while the same example simulated.     

Numerical problems in the advection of pollutants

Prediction of pollutant transport involves solution of the advection equation numerically. Truncation errors arising from integrating the advection equation using finite difference schemes are discussed. Numerical errors manifest themselves in artificial dissipation and dispersion of pollutants. Criteria for measuring the dissipation and dispersion are presented, and minimization of those errors is discussed. An alternative procedure by integration in the wave-number space is examined. Examples illustrating quantitative discrepancy in actual forecasting are also shown.     

Simulation of Two-Dimensional Transport Processes Using Nonlinear Monotone Second-Order Schemes

The Cauchy problem for a two-dimensional transport equation is considered. Two-layer certainly monotonous explicit second-order scheme, steady at large values of the difference Courant number, and an implicit two-layered certainly monotonous second-order scheme are developed based on the maximum principle for multilayered nonlinear difference schemes.     

A numerical study of the convergence properties of ENO schemes

We report numerical results obtained with finite difference ENO schemes for the model problem of the linear convection equation with periodic boundary conditions. For the test function sin(x), the spatial and temporal errors decrease at the rate expected from the order of local truncation errors as the discretization is refined. If we take sin⁴(x) as our test function, however, we find that the numerical solution does not converge uniformly and that an improved discretization can result in larger errors. This difficulty is traced back to the linear stability characteristics of the individual stencils employed by the ENO algorithm. If we modify the algorithm to prevent the use of linearly unstable stencils, the proper rate of convergence is reestablished. The way toward recovering the correct order of accuracy of ENO schemes appears to involve a combination of fixed stencils in smooth regions and ENO stencils in regions of strong gradients —a concept that is developed in detail in a companion paper by Shu (this issue, 1990).     

A modified boundary integral evolution formulation for the wave equation

We apply a modified boundary integral formulation otherwise known as the Green element method (GEM) to the solution of the two-dimensional scalar wave equation.GEM essentially combines three techniques namely: (a) finite difference approximation of the time term (b) finite element discretization of the problem domain and (c) boundary integral replication of the governing equation. These unique and advantageous characteristics of GEM facilitates a direct numerical approximation of the governing equation and obviate the need for converting the governing partial differential equation to a Helmholtz-type Laplace operator equation for an easier boundary element manipulation. C₁ continuity of the computed solutions is established by using Overhauser elements. Numerical tests show a reasonably close agreement with analytical results. Though in the case of the Overhauser GEM solutions, the level of accuracy obtained does not in all cases justify the extra numerical rigor.     

Finite central difference/finite element approximations for parabolic integro-differential equations

We study the numerical solution of an initial-boundary value problem for parabolic integro-differential equation with a weakly singular kernel. The main purpose of this paper is to construct and analyze stable and high order scheme to efficiently solve the integro-differential equation. The equation is discretized in time by the finite central difference and in space by the finite element method. We prove that the full discretization is unconditionally stable and the numerical solution converges to the exact one with order O(Δt ² + h ^l ). A numerical example demonstrates the theoretical results.     

A posteriori error estimates for a mixed-FEM formulation of a non-linear elliptic problem

We consider the numerical solution, via the mixed finite element method, of a non-linear elliptic partial differential equation in divergence form with Dirichlet boundary conditions. Besides the temperature u and the flux $\text{σ}$, we introduce ∇u as a further unknown, which yields a variational formulation with a twofold saddle point structure. We derive a reliable a posteriori error estimate that depends on the solution of a local linear boundary value problem, which does not need any equilibrium property for its solvability. In addition, for specific finite element subspaces of Raviart–Thomas type we are able to provide a fully explicit a posteriori error estimate that does not require the solution of the local problems. Our approach does not need the exact finite element solution, but any reasonable approximation of it, such as, for instance, the one obtained with a fully discrete Galerkin scheme. In particular, we suggest a scheme that uses quadrature formulas to evaluate all the linear and semi-linear forms involved. Finally, several numerical results illustrate the suitability of the explicit error estimator for the adaptive computation of the corresponding discrete solutions.     

A finite difference non-matching domain decomposition algorithm for the parabolic equation

A finite difference domain decomposition algorithm on a non-overlapping non-matching grid for the parabolic equation is discussed. The basic procedure is to define the explicit scheme at the interface points with a larger mesh spacing H, then the implicit schemes with different mesh spacings are applied on the non-matching subdomains, respectively. The stability bound is released both for the one-dimensional and two-dimensional parabolic problem. Finally, numerical experiments are also presented.     

Convergence of Summation-by-Parts Finite Difference Methods for the Wave Equation

When using a finite difference method to solve a time dependent partial differential equation, the truncation error is often larger at a few grid points near a boundary or grid interface than in the interior. In computations, the observed convergence rate is often higher than the order of the large truncation error. In this paper, we develop techniques for analyzing this phenomenon, and particularly consider the second order wave equation. The equation is discretized by a finite difference operator satisfying a summation by parts property, and the boundary and grid interface conditions are imposed weakly by the simultaneous approximation term method. It is well-known that if the semi-discretized wave equation satisfies the determinant condition, that is the boundary system in Laplace space is nonsingular for all Re \((s)\ge 0\), two orders are gained from the large truncation error localized at a few grid points. By performing a normal mode analysis, we show that many common discretizations do not satisfy the determinant condition at \(s=0\). We then carefully analyze the error equation to determine the gain in the convergence rate. The result shows that stability does not automatically imply a gain of two orders in the convergence rate. The precise gain can be lower than, equal to or higher than two orders, depending on the boundary condition and numerical boundary treatment. The accuracy analysis is verified by numerical experiments, and very good agreement is obtained.     

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.     

Finite difference representations of vorticity transport

Explicit finite difference representations of the steady two-dimensional laminar vorticity transport equation of fluid dynamics are summarized and discussed. The approximations known as ‘upwind differencing’, ‘locally exact’ after Alien and Southwell [1], Briggs [4] or Dennis and Hudson [12] are all shown to be the central difference approximation with the addition of numerical diffusion of the order of the error term in cell Reynolds number, R_c, which makes the associated matrix diagonally dominant. The local truncation error of this type of approximation can be minimized thus: (i) for ¦$\text{R}{}_{\mathrm{c}}\text{¦? 2}$, the central difference approximation, (ii) for ¦$\text{R}{}_{\mathrm{c}}\text{¦ > 2}$, upwind differencing applied to the inviscid equations, and therefore can be considered as a boundary layer approximation. This is the scheme introduced by Spalding [35]; successfully tested by Runchal [33].The local truncation error of the boundary condition, after Woods [39] for the vorticity is minimized in such a way that the formula is third-order accurate in grid size, in rectangular Cartesian coordinates.     

The generalized finite element method for Helmholtz equation. Part II: Effect of choice of handbook functions, error due to absorbing boundary conditions and its assessment

In Part I [T. Strouboulis, I. Babuška, R. Hidajat, The generalized finite element method for Helmholtz equation: theory, computation, and open problems, Comput. Methods Appl. Mech. Engrg. 195 (2006) 4711-4731] we introduced the q-version of the generalized finite element method (GFEM) for the Helmholtz equation and we addressed its: (a) pollution error due to the wave number; (b) exponential q-convergence; (c) robustness to perturbations of the mesh, the roundoff and numerical quadrature errors; and (d) a-posteriori error estimation. Here we continue the development of the GFEM for Helmholtz and we address the effects of: (a) alternative handbook functions and mesh types; (b) the error due to the artificial truncation boundary conditions and its assessment. The conclusions are: (1) the employment of plane-wave, wave-band, and Vekua handbook functions lead to equivalent results; and (2) for high q, the most significant component of error may be the one due to the artificial truncation boundary conditions. A rather straightforward approach for assessing this error is proposed.     

Space–time adaptive finite difference method for European multi-asset options

The multi-dimensional Black–Scholes equation is solved numerically for a European call basket option using a priori–a posteriori error estimates. The equation is discretized by a finite difference method on a Cartesian grid. The grid is adjusted dynamically in space and time to satisfy a bound on the global error. The discretization errors in each time step are estimated and weighted by the solution of the adjoint problem. Bounds on the local errors and the adjoint solution are obtained by the maximum principle for parabolic equations. Comparisons are made with Monte Carlo and quasi-Monte Carlo methods in one dimension, and the performance of the method is illustrated by examples in one, two, and three dimensions.     

Stability of the totally implicit finite difference scheme for the one-dimensional diffusion equation with a moving boundary

We analyze the totally implicitO(h ² k) finite difference method applied to a linear unidimensional diffusion equation with a boundary moving with constant velocity. The related physical problem is the solidification of a finite column filled with a binary mixture, in the quasiequilibrium regime. By advancing the boundary along the pathh/k=velocity of the interface, a simple algorithm is obtained which is shown to be consistent and unconditionally stable for any value of the interfacial segregation factor and of the Peclet number.     

An analysis of the time integration algorithms for the finite element solutions of incompressible Navier–Stokes equations based on a stabilised formulation

This work is concerned with the analysis of time integration procedures for the stabilised finite element formulation of unsteady incompressible fluid flows governed by the Navier–Stokes equations. The stabilisation technique is combined with several different implicit time integration procedures including both finite difference and finite element schemes. Particular attention is given to the generalised-α method and the linear discontinuous in time finite element scheme. The time integration schemes are first applied to two model problems, represented by a first order differential equation in time and the one dimensional advection–diffusion equation, and subjected to a detailed mathematical analysis based on the Fourier series expansion. In order to establish the accuracy and efficiency of the time integration schemes for the Navier–Stokes equations, a detailed computational study is performed of two standard numerical examples: unsteady flow around a cylinder and flow across a backward facing step. It is concluded that the semi-discrete generalised-α method provides a viable alternative to the more sophisticated and expensive space–time methods for simulations of unsteady flows of incompressible fluids governed by the Navier–Stokes equations.