Parallel S.O.R. iterative methods

New explicit group S.O.R. methods suitable for use on an asynchronous MIMD computer are presented for the numerical solution of the sparse linear systems derived from the discretization of two-dimensional, second-order, elliptic boundary value problems. A comparison with existing implicit line S.O.R. schemes for the Dirichlet model problem shows the new schemes to be superior (Barlow and Evans, 1982).     

Method of Lines Transpose: An Efficient Unconditionally Stable Solver for Wave Propagation

Building upon recent results obtained in Causley and Christlieb (SIAM J Numer Anal 52(1):220–235, 2014), Causley et al. (Math Comput 83(290):2763–2786, 2014, Method of lines transpose: high order L-stable O(N) schemes for parabolic equations using successive convolution, 2015), we describe an efficient second-order, unconditionally stable scheme for solving the wave equation, based on the method of lines transpose (MOL\(^T\)), and the resulting semi-discrete (i.e. continuous in space) boundary value problem. In Causley and Christlieb (SIAM J Numer Anal 52(1):220–235, 2014), unconditionally stable schemes of high order were derived, and in Causley et al. (Method of lines transpose: high order L-stable O(N) schemes for parabolic equations using successive convolution, 2015) a high order, fast \(\mathcal {O}(N)\) spatial solver was derived, which is matrix-free and is based on dimensional-splitting. In this work, are interested in building a wave solver, and our main concern is the development of boundary conditions. We demonstrate all desired boundary conditions for a wave solver, including outflow boundary conditions, in 1D and 2D. The scheme works in a logically Cartesian fashion, and the boundary points are embedded into the regular mesh, without incurring stability restrictions, so that boundary conditions are imposed without any reduction in the order of accuracy. We demonstrate how the embedded boundary approach works in the cases of Dirichlet and Neumann boundary conditions. Further, we develop outflow and periodic boundary conditions for the MOL\(^T\) formulation. Our solver is designed to couple with particle codes, and so special attention is also paid to the implementation of point sources, and soft sources which can be used to launch waves into waveguides.     

Accurate Implicit–Explicit General Linear Methods with Inherent Runge–Kutta Stability

We investigate implicit–explicit (IMEX) general linear methods (GLMs) with inherent Runge–Kutta stability (IRKS) for differential systems with non-stiff and stiff processes. The construction of such formulas starts with implicit GLMs with IRKS which are A- and L-stable, and then we ‘remove’ implicitness in non-stiff terms by extrapolating unknown stage derivatives by stage derivatives which are already computed by the method. Then we search for IMEX schemes with large regions of absolute stability of the ‘explicit part’ of the method assuming that the ‘implicit part’ of the scheme is \(A(\alpha )\)-stable for some \(\alpha \in (0,\pi /2]\). Examples of highly stable IMEX GLMs are provided of order \(1\le p\le 4\). Numerical examples are also given which illustrate good performance of these schemes.     

Efficient removal of boundary-divergence errors in time-splitting methods

A normal mode analysis is presented and numerical tests are performed to assess the effectiveness of a new time-splitting algorithm proposed recently in Karniadakiset al. (1990) for solving the incompressible Navier-Stokes equations. This new algorithm employs high-order explicit pressure boundary conditions and mixed explicit/implicit stiffly stable time-integration schemes, which can lead to arbitrarily high-order accuracy in time. In the current article we investigate both the time accuracy of the new scheme as well as the corresponding reduction in boundary-divergence errors for two model flow problems involving solid boundaries. The main finding is that time discretization errors, induced by the nondivergent splitting mode, scale with the order of the accuracy of the integration rule employed if a proper rotational form of the pressure boundary condition is used; otherwise a first-order accuracy in time similar to the classical splitting methods is achieved. In the former case the corresponding errors in divergence can be completely eliminated, while in the latter case they scale asO(vt)_1/2.     

A Supra-Convergent Finite Difference Scheme for the Poisson and Heat Equations on Irregular Domains and Non-Graded Adaptive Cartesian Grids

We present finite difference schemes for solving the variable coefficient Poisson and heat equations on irregular domains with Dirichlet boundary conditions. The computational domain is discretized with non-graded Cartesian grids, i.e., grids for which the difference in size between two adjacent cells is not constrained. Refinement criteria is based on proximity to the irregular interface such that cells with the finest resolution is placed on the interface. We sample the solution at the cell vertices (nodes) and use quadtree (in 2D) or octree (in 3D) data structures as efficient means to represent the grids. The boundary of the irregular domain is represented by the zero level set of a signed distance function. For cells cut by the interface, the location of the intersection point is found by a quadratic fitting of the signed distance function, and the Dirichlet boundary value is obtained by quadratic interpolation. Instead of using ghost nodes outside the interface, we use directly this intersection point in the discretization of the variable coefficient Laplacian. These methods can be applied in a dimension-by-dimension fashion, producing schemes that are straightforward to implement. Our method combines the ability of adaptivity on quadtrees/octrees with a quadratic treatment of the Dirichlet boundary condition on the interface. Numerical results in two and three spatial dimensions demonstrate second-order accuracy for both the solution and its gradients in the L ¹ and L ^∞ norms.     

A strictly conservative Cartesian cut-cell method for compressible viscous flows on adaptive grids

A Cartesian cut-cell method which allows the solution of two- and three-dimensional viscous, compressible flow problems on arbitrarily refined graded meshes is presented. The finite-volume method uses cut cells at the boundaries rendering the method strictly conservative in terms of mass, momentum, and energy. For three-dimensional compressible flows, such a method has not been presented in the literature, yet. Since ghost cells can be arbitrarily positioned in space the proposed method is flexible in terms of shape and size of embedded boundaries. A key issue for Cartesian grid methods is the discretization at mesh interfaces and boundaries and the specification of boundary conditions. A linear least-squares method is used to reconstruct the cell center gradients in irregular regions of the mesh, which are used to formulate the surface flux. Expressions to impose boundary conditions and to compute the viscous terms on the boundary are derived. The overall discretization is shown to be second-order accurate in L¹. The accuracy of the method and the quality of the solutions are demonstrated in several two- and three-dimensional test cases of steady and unsteady flows.     

Finite difference schemes for two-dimensional parabolic inverse problem with temperature overspecification

Two different explicit finite difference schemes for solving the two-dimensional parabolic inverse problem with temperature overspecification are considered. These schemes are developed for indentifying the control parameter which produces, at any given time, a desired temperature distribution at a given point in the spatial domain. The numerical methods discussed, are based on the second-order, 5-point Forward Time Centred Space (FTCS) explicit formula, and the (1,9) FTCS explicit scheme which is generally second-order, but is fourth order when the diffusion number takes the value s = (1/6). These schemes are economical to use, are second-order and have bounded range of stability. The range of stability for the 5-point formula is less restrictive than the (1,9) FTCS explicit scheme. The results of numerical experiments are presented, and accuracy and Central Processor (CPU) times needed for each of the methods are discussed. These schemes use less central processor times than the second-order fully implicit method for two-dimensional diffusion with temperature overspecification. We also give error estimates in the maximum norm for each of these methods.     

Long time stability and convergence rate of MacCormack rapid solver method for nonstationary Stokes–Darcy problem

We propose and study a combination of two second-order implicit–explicit (IMEX) methods for the coupled Stokes–Darcy system that governs flows in karst aquifers. The first is a second-order explicit two-step MacCormack scheme and the second is a second-order implicit Crank–Nicolson method. Both algorithms only require the solution of two decoupled problems at each time step, one Stokes and the other Darcy. This combination so called the MacCormack rapid solver method is very efficient (faster, at least of second order accuracy in time and space) and can be easily implemented using legacy codes. Under time step limitation of the form $\Delta t\le Ch$ (where $h,$$\Delta t$ are mesh size and time step, respectively, and $C$ is a physical parameter) we prove both long time stability and the rate of convergence of the method. Some numerical experiments are presented and discussed.     

H2-stability of the first order Galerkin method for the Boussinesq equations with smooth and non-smooth initial data

In this paper, the $H^2$-stability of the first order fully discrete Galerkin finite element methods for the Boussinesq equations with smooth and non-smooth initial data is presented. The finite element spatial discretization for the Boussinesq equations is based on the mixed finite element method, and the temporal treatments of the spatial discrete Boussinesq equations include the implicit scheme, the semi-implicit scheme, the implicit/explicit scheme and the explicit scheme. The $H^2$-stability results of the above numerical schemes are established. Firstly, we prove that the implicit and semi-implicit schemes are the $H^2$-unconditional stable. Then we show that the implicit/explicit scheme is $H^2$-almost unconditional stable with the initial data that belong to $H^1$ and $H^2$, and the similar results are obtained for the semi-implicit/explicit scheme in the case of the initial data that belong to $L^2$. Furthermore, we show that the explicit scheme is the $H^2$-conditional stable. Finally, some numerical examples are provided to verify the established theoretical findings and confirm the corresponding $H^2$ stability analysis of the different numerical schemes.     

Optimal Spectral Schemes Based on Generalized Prolate Spheroidal Wave Functions of Order $$$$

We introduce a family of generalized prolate spheroidal wave functions (PSWFs) of order \(-1,\) and develop new spectral schemes for second-order boundary value problems. Our technique differs from the differentiation approach based on PSWFs of order zero in Kong and Rokhlin (Appl Comput Harmon Anal 33(2):226–260, 2012); in particular, our orthogonal basis can naturally include homogeneous boundary conditions without the re-orthogonalization of Kong and Rokhlin (2012). More notably, it leads to diagonal systems or direct “explicit” solutions to 1D Helmholtz problems in various situations. Using a rule optimally pairing the bandwidth parameter and the number of basis functions as in Kong and Rokhlin (2012), we demonstrate that the new method significantly outperforms the Legendre spectral method in approximating highly oscillatory solutions. We also conduct a rigorous error analysis of this new scheme. The idea and analysis can be extended to generalized PSWFs of negative integer order for higher-order boundary value and eigenvalue problems.     

An implicit,conservative, zonal-boundary scheme for Euler equation calculations

A “zonal”, or “patched-grid”, approach is one in which the flow region of interest is divided into subregions which are then discretized independently, using existing grid generators. The equations of motion are integrated in each subregion in conjunction with zonal-boundary schemes which allow proper information transfer across interfaces that separate subregions. The zonal approach greatly simplifies the treatment of complex geometries and also the addition of grid points to selected regions of the flow. In this study a conservative, zonal-boundary condition that could be used with explicit schemes has been extended so that it can be used with existing second-order accurate implicit integration schemes such as the Beam-Warming and Osher schemes. In the test case considered, the implicit schemes increased the rate of convergence considerably (by a factor of about 30 over that of the explicit scheme). Results demonstratiting the time-accuracy of the zonal scheme and the feasibility of performing calculations on zones that move relative to each other are also presented.     

A Mixed Discontinuous Galerkin Method Without Interior Penalty for Time-Dependent Fourth Order Problems

A novel discontinuous Galerkin (DG) method is developed to solve time-dependent bi-harmonic type equations involving fourth derivatives in one and multiple space dimensions. We present the spatial DG discretization based on a mixed formulation and central interface numerical fluxes so that the resulting semi-discrete schemes are \(L^2\) stable even without interior penalty. For time discretization, we use Crank–Nicolson so that the resulting scheme is unconditionally stable and second order in time. We present the optimal \(L^2\) error estimate of \(O(h^{k+1})\) for polynomials of degree k for semi-discrete DG schemes, and the \(L^2\) error of \(O(h^{k+1} +(\Delta t)^2)\) for fully discrete DG schemes. Extensions to more general fourth order partial differential equations and cases with non-homogeneous boundary conditions are provided. Numerical results are presented to verify the stability and accuracy of the schemes. Finally, an application to the one-dimensional Swift–Hohenberg equation endowed with a decay free energy is presented.     

An Implicit Eulerian–Lagrangian WENO3 Scheme for Nonlinear Conservation Laws

We present a new, formally third order, implicit Weighted Essentially Non-Oscillatory (iWENO3) finite volume scheme for solving systems of nonlinear conservation laws. We then generalize it to define an implicit Eulerian–Lagrangian WENO (iEL-WENO) scheme. Implicitness comes from the use of an implicit Runge–Kutta (RK) time integrator. A specially chosen two-stage RK method allows us to drastically simplify the computation of the intermediate RK fluxes, leading to a computationally tractable scheme. The iEL-WENO3 scheme has two main steps. The first accounts for particles being transported within a grid element in a Lagrangian sense along the particle paths. Since this particle velocity is unknown (in a nonlinear problem), a fixed trace velocity v is used. The second step of the scheme accounts for the inaccuracy of the trace velocity v by computing the flux of particles crossing the incorrect tracelines. The CFL condition is relaxed when v is chosen to approximate the characteristic velocity. A new Roe solver for the Euler system is developed to account for the Lagrangian tracings, which could be useful even for explicit EL-WENO schemes. Numerical results show that iEL-WENO3 is both less numerically diffusive and can take on the order of about 2–3 times longer time steps than standard WENO3 for challenging nonlinear problems. An extension is made to the advection–diffusion equation. When advection dominates, the scheme retains its third order accuracy.     

A new unconditionally stable explicit scheme for the convection–diffusion equation with Robin boundary conditions

An alternating direction explicit (ADE) scheme to solve the unsteady convection–diffusion equation with Robin boundary conditions is presented and discussed in this paper. It was derived based on the local series expansion method and proved unconditionally stable by von Neumann stability analysis. Thereafter, the ADE scheme is compared with the conventional schemes, and a comparison between the amplification factor of all schemes and the exact one shows that the proposed scheme can simulate well both convection- and diffusion-dominated problems. Finally, the proposed method was validated by a numerical experiment which indicates that, for large cell Reynolds numbers, the proposed scheme, which has unconditional stability, is more accurate than implicit schemes and most explicit schemes. It is also shown that the proposed scheme is simple to implement, economical to use, effective for dealing with Robin boundary conditions and easy to apply to multidimensional problems.     

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.     

Cartesian cut cell approach for simulating incompressible flows with rigid bodies of arbitrary shape

In this paper, a Cartesian grid method with cut cell approach has been developed to simulate two dimensional unsteady viscous incompressible flows with rigid bodies of arbitrary shape. A collocated finite volume method with nominally second-order accurate schemes in space is used for discretization. A pressure-free projection method is used to solve the equations governing incompressible flows. For fixed-body problems, the Adams-Bashforth scheme is employed for the advection terms and the Crank-Nicholson scheme for the diffusion terms. For moving-body problems, the fully implicit scheme is employed for both terms. The present cut cell approach with cell merging process ensures global mass/momentum conservation and avoid exceptionally small size of control volume which causes impractical time step size. The cell merging process not only keeps the shape resolution as good as before merging, but also makes both the location of cut face center and the construction of interpolation stencil easy and systematic, hence enables the straightforward extension to three dimensional space in the future. Various test examples, including a moving-body problem, were computed and validated against previous simulations or experiments to prove the accuracy and effectiveness of the present method. The observed order of accuracy in the spatial discretization is superlinear.     

Euler-like discrete models of the logistic differential equation

To understand the behavior of difference schemes on nonlinear differential equations, it seems desirable to extend the standard linear stability theory into a nonlinear theory. As a step in that direction, we investigate the stability properties of Euler-related integration algorithms by checking how they preserve and violate the dynamical structure of the logistic differential equation.Among the schemes considered are two linearly implicit nonstandard schemes which are adjoint to each other. We find that these schemes are superior to explicit schemes when they are stable and the blow-up time has not passed: for these λh-values they are dynamically faithful. When these schemes ‘turn unstable’, however, they have much less desirable properties than explicit or fully implicit schemes: they become simultaneously superstable and unstable. This is explained by the fact that these schemes are not self-adjoint: the linearly implicit self-adjoint scheme is dynamically faithful in an Euler-typical range of step sizes and gives correct stability for all step sizes.     

Second-Order Accurate Computation of Curvatures in a Level Set Framework Using Novel High-Order Reinitialization Schemes

We present a high-order accurate scheme for the reinitialization equation of Sussman et al.(J. Comput. Phys. 114:146–159, [1994]) that guarantees accurate computation of the interface’s curvatures in the context of level set methods. This scheme is an extension of the work of Russo and Smereka (J. Comput. Phys. 163:51–67, [2000]). We present numerical results in two and three spatial dimensions to demonstrate fourth-order accuracy for the reinitialized level set function, third-order accuracy for the normals and second-order accuracy for the interface’s mean curvature in the L ¹- and L ^∞-norms. We also exploit the work of Min and Gibou (UCLA CAM Report (06-22), [2006]) to show second-order accurate scheme for the computation of the mean curvature on non-graded adaptive grids.     

Residual Distribution Schemes on Quadrilateral Meshes

We propose an investigation of the residual distribution schemes for the numerical approximation of two-dimensional hyperbolic systems of conservation laws on general quadrilateral meshes. In comparison to the use of triangular cells, usual basic features are recovered, an extension of the upwinding concept is given, and a Lax–Wendroff type theorem is adapted for consistency. We show how to retrieve many variants of standard first and second-order accurate schemes. They are proven to satisfy this theorem. An important part of this paper is devoted to the validation of these schemes by various numerical tests for scalar equations and the Euler equations system for compressible fluid dynamics on non Cartesian grids. In particular, second-order accuracy is reached by an adaptation of the Linearity preserving property to quadrangle meshes. We discuss several choices as well as the convergence of iterative method to steady state. We also provide examples of schemes that are not constructed from an upwinding principle     

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.