Multirate Timestepping Methods for Hyperbolic Conservation Laws

This paper constructs multirate time discretizations for hyperbolic conservation laws that allow different timesteps to be used in different parts of the spatial domain. The proposed family of discretizations is second order accurate in time and has conservation and linear and nonlinear stability properties under local CFL conditions. Multirate timestepping avoids the necessity to take small global timesteps (restricted by the largest value of the Courant number on the grid) and therefore results in more efficient algorithms. Numerical results obtained for the advection and Burgers’ equations confirm the theoretical findings. This work was supported by the National Science Foundation through award NSF CCF-0515170.     

On High Order Strong Stability Preserving Runge–Kutta and Multi Step Time Discretizations

Strong stability preserving (SSP) high order time discretizations were developed for solution of semi-discrete method of lines approximations of hyperbolic partial differential equations. These high order time discretization methods preserve the strong stability properties–in any norm or seminorm—of the spatial discretization coupled with first order Euler time stepping. This paper describes the development of SSP methods and the recently developed theory which connects the timestep restriction on SSP methods with the theory of monotonicity and contractivity. Optimal explicit SSP Runge–Kutta methods for nonlinear problems and for linear problems as well as implicit Runge–Kutta methods and multi step methods will be collected     

High Order Strong Stability Preserving Time Discretizations

Strong stability preserving (SSP) high order time discretizations were developed to ensure nonlinear stability properties necessary in the numerical solution of hyperbolic partial differential equations with discontinuous solutions. SSP methods preserve the strong stability properties—in any norm, seminorm or convex functional—of the spatial discretization coupled with first order Euler time stepping. This paper describes the development of SSP methods and the connections between the timestep restrictions for strong stability preservation and contractivity. Numerical examples demonstrate that common linearly stable but not strong stability preserving time discretizations may lead to violation of important boundedness properties, whereas SSP methods guarantee the desired properties provided only that these properties are satisfied with forward Euler timestepping. We review optimal explicit and implicit SSP Runge–Kutta and multistep methods, for linear and nonlinear problems. We also discuss the SSP properties of spectral deferred correction methods. The work of S. Gottlieb was supported by AFOSR grant number FA9550-06-1-0255. The work of D.I. Ketcheson was supported by a US Dept. of Energy Computational Science Graduate Fellowship under grant DE-FG02-97ER25308. The research of C.-W. Shu is supported in part by NSF grants DMS-0510345 and DMS-0809086.     

On high order strong stability preserving runge-kutta and multi step time discretizations

Strong stability preserving (SSP) high order time discretizations were developed for solution of semi-discrete method of lines approximations of hyperbolic partial differential equations. These high order time discretization methods preserve the strong stability properties-in any norm or seminorm—of the spatial discretization coupled with first order Euler time stepping. This paper describes the development of SSP methods and the recently developed theory which connects the timestep restriction on SSP methods with the theory of monotonicity and contractivity. Optimal explicit SSP Runge-Kutta methods for nonlinear problems and for linear problems as well as implicit Runge-Kutta methods and multi step methods will be collected.     

On unconditional conservation of kinetic energy by finite-difference discretizations of the linear and non-linear convection equation

In the past the development of kinetic energy conserving finite-difference methods mostly focused on second-order accurate central methods defined on uniform grids. Nowadays the need for high-order accurate discretizations, to perform for instance accurate numerical simulations of turbulent flow, calls for the development of novel kinetic energy conserving discretization schemes. Instead of choosing a fixed basis discretization up front, in this paper a different, more general, approach is applied. For a Cartesian mesh, sets of conditions are presented such that all discretizations of the linear or non-linear convection equation which obey these conditions, unconditionally conserve kinetic energy.For the linear convection equation it is shown that on a uniform grid it is necessary and sufficient for a discretization to be central in order to be fully conservative, that is: such discretizations not only unconditionally conserve kinetic energy but also unconditionally conserve momentum. On non-uniform grids an algorithm is introduced that can be used to generate fully conservative discretizations that are at least first-order accurate.The derivation of the discretization conditions for the non-linear convection equation is performed in the two-dimensional (2D) linear case. Some examples on uniform grids and on non-uniform grids are presented. It is shown that on uniform grids no upper limit exists with respect to the accuracy of the kinetic energy conserving method. For the higher-dimensional linear and non-linear convection equation the same set of conditions, which ensure the unconditional conservation of kinetic energy, are found as in the 2D linear case. Other results too are found to be straightforward generalizations of the corresponding 2D linear results.It is shown that the fourth-order unconditionally kinetic energy conserving discretization on a staggered mesh introduced in this paper is well suited to simulate the initial development of an inviscid shear layer instability in a divergence-free flow.     

Extrapolated Multirate Methods for Differential Equations with Multiple Time Scales

In this paper we construct extrapolated multirate discretization methods that allows one to efficiently solve problems that have components with different dynamics. This approach is suited for the time integration of multiscale ordinary and partial differential equations and provides highly accurate discretizations. We analyze the linear stability properties of the multirate explicit and linearly implicit extrapolated methods. Numerical results with multiscale ODEs illustrate the theoretical findings.     

High Accuracy Schemes for DNS and Acoustics

High-accuracy schemes have been proposed here to solve computational acoustics and DNS problems. This is made possible for spatial discretization by optimizing explicit and compact differencing procedures that minimize numerical error in the spectral plane. While zero-diffusion nine point explicit scheme has been proposed for the interior, additional high accuracy one-sided stencils have also been developed for ghost cells near the boundary. A new compact scheme has also been proposed for non-periodic problems—obtained by using multivariate optimization technique. Unlike DNS, the magnitude of acoustic solutions are similar to numerical noise and that rules out dissipation that is otherwise introduced via spatial and temporal discretizations. Acoustics problems are wave propagation problems and hence require Dispersion Relation Preservation (DRP) schemes that simultaneously meet high accuracy requirements and keeping numerical and physical dispersion relation identical. Emphasis is on high accuracy than high order for both DNS and acoustics. While higher order implies higher accuracy for spatial discretization, it is shown here not to be the same for time discretization. Specifically it is shown that the 2nd order accurate Adams-Bashforth (AB)—scheme produces unphysical results compared to first order accurate Euler scheme. This occurs, as the AB-scheme introduces a spurious computational mode in addition to the physical mode that apportions to itself a significant part of the initial condition that is subsequently heavily damped. Additionally, AB-scheme has poor DRP property making it a poor method for DNS and acoustics. These issues are highlighted here with the help of a solution for (a) Navier–Stokes equation for the temporal instability problem of flow past a rotating cylinder and (b) the inviscid response of a fluid dynamical system excited by simultaneous application of acoustic, vortical and entropic pulses in an uniform flow. The last problem admits analytic solution for small amplitude pulses and can be used to calibrate different methods for the treatment of non-reflecting boundary conditions as well.     

Concepts and Application of Time-Limiters to High Resolution Schemes

A new class of implicit high-order non-oscillatory time integration schemes is introduced in a method-of-lines framework. These schemes can be used in conjunction with an appropriate spatial discretization scheme for the numerical solution of time dependent conservation equations. The main concept behind these schemes is that the order of accuracy in time is dropped locally in regions where the time evolution of the solution is not smooth. By doing this, an attempt is made at locally satisfying monotonicity conditions, while maintaining a high order of accuracy in most of the solution domain. When a linear high order time integration scheme is used along with a high order spatial discretization, enforcement of monotonicity imposes severe time-step restrictions. We propose to apply limiters to these time-integration schemes, thus making them non-linear. When these new schemes are used with high order spatial discretizations, solutions remain non-oscillatory for much larger time-steps as compared to linear time integration schemes. Numerical results obtained on scalar conservation equations and systems of conservation equations are highly promising.     

On the Linear Stability of the Fifth-Order WENO Discretization

We study the linear stability of the fifth-order Weighted Essentially Non-Oscillatory spatial discretization (WENO5) combined with explicit time stepping applied to the one-dimensional advection equation. We show that it is not necessary for the stability domain of the time integrator to include a part of the imaginary axis. In particular, we show that the combination of WENO5 with either the forward Euler method or a two-stage, second-order Runge–Kutta method is linearly stable provided very small time step-sizes are taken. We also consider fifth-order multistep time discretizations whose stability domains do not include the imaginary axis. These are found to be linearly stable with moderate time steps when combined with WENO5. In particular, the fifth-order extrapolated BDF scheme gave superior results in practice to high-order Runge–Kutta methods whose stability domain includes the imaginary axis. Numerical tests are presented which confirm the analysis.     

Flank wear detection of cutting tool inserts in turning operation: application of nonlinear time series analysis

It has been established that turning process on a lathe exhibits low dimensional chaos. This study reports the results of nonlinear time series analysis applied to sensor signals captured real time. The purpose of this chaos analysis is to differentiate three levels of flank wears on cutting tool inserts—fresh, partially worn and fully worn—utilizing the single value index extracted from the reconstructed chaotic attractor; the correlation dimension. The analysis reveals distinguishable dynamics of cutting characterized by different values for the dimension of the attractor when different quality tool inserts are used. This dependence can be effectively utilized as one of the indicators in tool condition monitoring in a lathe. This paper presents the experimental results and shows that tool vibration signals can transmit tool wear conditions reliably.     

Important aspects of geometric numerical integration

At the example of Hamiltonian differential equations, geometric properties of the flow are discussed that are only preserved by special numerical integrators (such as symplectic and/or symmetric methods). In the ‘non-stiff’ situation the long-time behaviour of these methods is well-understood and can be explained with the help of a backward error analysis. In the highly oscillatory (‘stiff’) case this theory breaks down. Using a modulated Fourier expansion, much insight can be gained for methods applied to problems where the high oscillations stem from a linear part of the vector field and where only one (or a few) high frequencies are present. This paper terminates with numerical experiments at space discretizations of the sine-Gordon equation, where a whole spectrum of frequencies is present.     

Adaptive Multiresolution Methods for the Simulation of Waves in Excitable Media

We present fully adaptive multiresolution methods for a class of spatially two-dimensional reaction-diffusion systems which describe excitable media and often give rise to the formation of spiral waves. A novel model ingredient is a strongly degenerate diffusion term that controls the degree of spatial coherence and serves as a mechanism for obtaining sharper wave fronts. The multiresolution method is formulated on the basis of two alternative reference schemes, namely a classical finite volume method, and Barkley’s approach (Barkley in Phys. D 49:61–70, 1991), which consists in separating the computation of the nonlinear reaction terms from that of the piecewise linear diffusion. The proposed methods are enhanced with local time stepping to attain local adaptivity both in space and time. The computational efficiency and the numerical precision of our methods are assessed. Results illustrate that the fully adaptive methods provide stable approximations and substantial savings in memory storage and CPU time while preserving the accuracy of the discretizations on the corresponding finest uniform grid.     

Important Aspects of Geometric Numerical Integration

At the example of Hamiltonian differential equations, geometric properties of the flow are discussed that are only preserved by special numerical integrators (such as symplectic and/or symmetric methods). In the ‘non-stiff’ situation the long-time behaviour of these methods is well-understood and can be explained with the help of a backward error analysis. In the highly oscillatory (‘stiff’) case this theory breaks down. Using a modulated Fourier expansion, much insight can be gained for methods applied to problems where the high oscillations stem from a linear part of the vector field and where only one (or a few) high frequencies are present. This paper terminates with numerical experiments at space discretizations of the sine-Gordon equation, where a whole spectrum of frequencies is present     

Positivity for Convective Semi-discretizations

We propose a technique for investigating stability properties like positivity and forward invariance of an interval for method-of-lines discretizations, and apply the technique to study positivity preservation for a class of TVD semi-discretizations of 1D scalar hyperbolic conservation laws. This technique is a generalization of the approach suggested in Khalsaraei (J Comput Appl Math 235(1): 137–143, 2010). We give more relaxed conditions on the time-step for positivity preservation for slope-limited semi-discretizations integrated in time with explicit Runge–Kutta methods. We show that the step-size restrictions derived are sharp in a certain sense, and that many higher-order explicit Runge–Kutta methods, including the classical 4th-order method and all non-confluent methods with a negative Butcher coefficient, cannot generally maintain positivity for these semi-discretizations under any positive step size. We also apply the proposed technique to centered finite difference discretizations of scalar hyperbolic and parabolic problems.     

Flux-based method of characteristics for contaminant transport in flowing groundwater

A numerical method for treating advection-dominated contaminant transport in flowing groundwater is described. This method combines advantages of numerical discretizations by finite volume methods (like local mass conservation and the positivity of solutions) and by methods of characteristics (like larger time steps and reduced artificial numerical dispersion). For one-dimensional problems the method can produce equivalent algebraic systems as the finite volume Eulerian-Lagrangian localized adjoint method [13] and the flux-based modified method of characteristics [23] (and some other methods). An extension of the "flux-based methods of characteristics" for complex transport problems on multidimensional unstructured computational grids is the main contribution of this paper. Numerical results are included for a well established test example using a flux-based method of characteristics with aligned finite volumes.     

Dispersion,group velocity,and multisymplectic discretizations

This paper examines the dispersive properties of multisymplectic discretizations of linear and nonlinear PDEs. We focus on a leapfrog in space and time scheme and the Preissman box scheme. We find that the numerical dispersion relations are monotonic and determine the relationship between the group velocities of the different numerical schemes. The group velocity dispersion is used to explain the qualitative differences in the numerical solutions obtained with the different schemes. Furthermore, the numerical dispersion relation is found to be relevant when determining the ability of the discretizations to resolve nonlinear dynamics.     

Upwind methods for hyperbolic conservation laws with source terms

This paper deals with the extension of some upwind schemes to hyperbolic systems of conservation laws with source term. More precisely we give methods to get natural upwind discretizations of the source term when the flux is approximated by using flux-difference or flux-splitting techniques. In particular, the Q-schemes of Roe and van Leer and the flux-splitting techniques of Steger-Warming and Vijayasundaram are considered. Numerical results for a scalar advection equation with nonlinear source and for the one-dimensional shallow water equations are presented. In the last case we compare the different schemes proposed in terms of a conservation property. When this property does not hold, spurious numerical waves can appear which is the case for the centred discretization of the source term.     

Explicit approximate inverse preconditioning techniques

Summary  The numerical treatment and the production of related software for solving large sparse linear systems of algebraic equations, derived mainly from the discretization of partial differential equation, by preconditioning techniques has attracted the attention of many researchers. In this paper we give an overview of explicit approximate inverse matrix techniques for computing explicitly various families of approximate inverses based on Choleski and LU—type approximate factorization procedures for solving sparse linear systems, which are derived from the finite difference, finite element and the domain decomposition discretization of elliptic and parabolic partial differential equations. Composite iterative schemes, using inner-outer schemes in conjunction with Picard and Newton method, based on approximate inverse matrix techniques for solving non-linear boundary value problems, are presented. Additionally, isomorphic iterative methods are introduced for the efficient solution of non-linear systems. Explicit preconditioned conjugate gradient—type schemes in conjunction with approximate inverse matrix techniques are presented for the efficient solution of linear and non-linear system of algebraic equations. Theoretical estimates on the rate of convergence and computational complexity of the explicit preconditioned conjugate gradient method are also presented. Applications of the proposed methods on characteristic linear and non-linear problems are discussed and numerical results are given.