Galerkin approximations with embedded boundary conditions for retarded delay differential equations

Finite-dimensional approximations are developed for retarded delay differential equations (DDEs). The DDE system is equivalently posed as an initial-boundary value problem consisting of hyperbolic partial differential equations (PDEs). By exploiting the equivalence of partial derivatives in space and time, we develop a new PDE representation for the DDEs that is devoid of boundary conditions. The resulting boundary condition-free PDEs are discretized using the Galerkin method with Legendre polynomials as the basis functions, whereupon we obtain a system of ordinary differential equations (ODEs) that is a finite-dimensional approximation of the original DDE system. We present several numerical examples comparing the solution obtained using the approximate ODEs to the direct numerical simulation of the original non-linear DDEs. Stability charts developed using our method are compared to existing results for linear DDEs. The presented results clearly demonstrate that the equivalent boundary condition-free PDE formulation accurately captures the dynamic behaviour of the original DDE system and facilitates the application of control theory developed for systems governed by ODEs.     

A friendly Fortran DDE solver

DKLAG6 is a FORTRAN 77 code widely used to solve delay differential equations (DDEs). Like all the popular Fortran DDE solvers, new users find it formidable and in many respects, it is not easy to use. We have applied our experience writing DDE solvers in Matlab and the capabilities of Fortran 90 to the development of a friendly Fortran DDE solver. How we accomplished this may be of interest to others who would like to modernize legacy code. In the course of developing a completely new user interface, we have added significantly to the capabilities of DKLAG6.     

OpenMG: A new multigrid implementation in Python

In many large‐scale computations, systems of equations arise in the form Au = b, where A is a linear operation to be performed on the unknown data u, producing the known right‐hand side, b, which represents some constraint of known or assumed behavior of the system being modeled. Because such systems can be very large, solving them directly can be too slow. In contrast, a multigrid method removes different components of the error at different resolutions using smoothers that reduce high‐frequency components of the error more readily than low. Here, we present an open‐source multigrid solver written only in Python. OpenMG is a pure Python experimentation environment for testing multigrid concepts, not a production solver. The particular restriction method implemented is for ‘standard’ multigrid. By making the code simple and modular, we make the algorithmic details clear. The resulting solver is tested on an implicit pressure reservoir simulation problem with satisfactory results.Copyright © 2013 John Wiley & Sons, Ltd.     

An efficient linear solver for the hybridized discontinuous Galerkin method

Discretizing partial differential equations by an implicit solving technique ultimately leads to a linear system of equations that has to be solved. The number of globally coupled unknowns is especially large for discontinuous Galerkin (DG) methods. It can be reduced by using hybridized discontinuous Galerkin (HDG) methods, but still efficient linear solvers are needed. It has been shown that, if hierarchical basis functions are used, a hierarchical scale separation (HSS) ansatz can be an efficient solver. In this work, we couple the HDG method with an HSS solver to solve a scalar nonlinear problem. It is validated by comparing the results with results obtained by GMRES with ILU(3) preconditioning as linear solver. (© 2016 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Approximate Factorization in Shallow Water Applications

We consider the numerical integration of problems modelling phenomena in shallow water in 3 spatial dimensions. If the governing partial differential equations for such problems are spatially discretized, then the right-hand side of the resulting system of ordinary differential equations can be split into terms f ₁, f ₂, f ₃ and f ₄, respectively representing the spatial derivative terms with respect to the x, y and z directions, and the interaction terms. It is typical for shallow water applications that the interaction term f ₄ is nonstiff and that the function f ₃ corresponding with the vertical spatial direction is much more stiff than the functions f ₁ and f ₂ corresponding with the horizontal spatial directions. The reason is that in shallow seas the gridsize in the vertical direction is several orders of magnitude smaller than in the horizontal directions. In order to solve the initial value problem (IVP) for these systems numerically, we need a stiff IVP solver, which is necessarily implicit, requiring the iterative solution of large systems of implicit relations. The aim of this paper is the design of an efficient iteration process based on approximate factorization. Stability properties of the resulting integration method are compared with those of a number of integration methods from the literature. Finally, a performance test on a shallow water transport problem is reported.     

Variable-step variable-order 3-stage Hermite-Birkhoff-Obrechkoff DDE solver of order 4 to 14

This article presents a solver for delay differential equations (DDEs) called HBO414DDE based on a hybrid variable-step variable-order 3-stage Hermite-Birkhoff-Obrechkoff ODE solver of order 4 to 14. The current version of our method solves DDEs with state dependent, non-vanishing, small, vanishing and asymptotically vanishing delays, except neutral type and initial value DDEs. Delayed values are computed using Hermite interpolation, small delays are dealt with by extrapolation, and discontinuities are located by a bisection method. HBO414DDE was tested on several problems and results were compared with those of known solvers like SYSDEL and the recent Matlab DDE solver ddesd and statistics show that it gives, most of the time, a smaller relative error than the other solvers for the same number of function evaluations.     

Discontinuous solutions of neutral delay differential equations

It is well known that the solutions of delay differential and implicit and explicit neutral delay differential equations (NDDEs) may have discontinuous derivatives, but it has not been appreciated (sufficiently) that the solutions of NDDEs—and, therefore, solutions of delay differential algebraic equations—need not be continuous. Numerical codes for solving differential equations, with or without retarded arguments, are generally based on the assumption that a solution is continuous. We illustrate and explain how the discontinuities arise, and present some methods to deal with these problems computationally. The investigation of a simple example is followed by a discussion of more general NDDEs and further mathematical detail.     

一类分数阶多项延迟微分方程的Jacobi谱配置方法

本文利用Jacobi谱配置方法数值求解了一类分数阶多项延迟微分方程,并证明了该方法是收敛的,通过若干数值算例验证了相应的理论结果,结果表明Jacobi谱配置方法求解这类方程是非常高效的,同时也为这类分数阶延迟微分方程的数值求解提供了新的选择,对分数阶泛函方程的数值方法的研究有一定的指导意义.     

Waveform relaxation methods for implicit differential equations

We apply a Runge-Kutta-based waveform relaxation method to initial-value problems for implicit differential equations. In the implementation of such methods, a sequence of nonlinear systems has to be solved iteratively in each step of the integration process. The size of these systems increases linearly with the number of stages of the underlying Runge-Kutta method, resulting in high linear algebra costs in the iterative process for high-order Runge-Kutta methods. In our earlier investigations of iterative solvers for implicit initial-value problems, we designed an iteration method in which the linear algebra costs are almost independent of the number of stages when implemented on a parallel computer system. In this paper, we use this parallel iteration process in the Runge-Kutta waveform relaxation method. In particular, we analyse the convergence of the method. The theoretical results are illustrated by a few numerical examples.     

Implicit Euler and Lie splitting discretizations of nonlinear parabolic equations with delay

A convergence analysis is presented for the implicit Euler and Lie splitting schemes when applied to nonlinear parabolic equations with delay. More precisely, we consider a vector field which is the sum of an unbounded dissipative operator and a delay term, where both point delays and distributed delays fit into the framework. Such equations are frequently encountered, e.g. in population dynamics. The main theoretical result is that both schemes converge with an order (of at least) \(q=1/2\) , without any artificial regularity assumptions. We discuss implementation details for the methods, and the convergence results are verified by numerical experiments demonstrating both the correct order, as well as the efficiency gain of Lie splitting as compared to the implicit Euler scheme.     

Nonlinear stability of discontinuous Galerkin methods for delay differential equations

The present paper is devoted to a study of nonlinear stability of discontinuous Galerkin methods for delay differential equations. Some concepts, such as global and analogously asymptotical stability are introduced. We derive that discontinuous Galerkin methods lead to global and analogously asymptotical stability for delay differential equations. And these nonlinear stability properties reveal to the reader the relation between the perturbations of the numerical solution and that of the initial value or the systems.     

Numerical Computation of Connecting Orbits in Delay Differential Equations

We discuss the numerical computation of homoclinic and heteroclinic orbits in delay differential equations. Such connecting orbits are approximated using projection boundary conditions, which involve the stable and unstable manifolds of a steady state solution. The stable manifold of a steady state solution of a delay differential equation (DDE) is infinite-dimensional, a problem which we circumvent by reformulating the end conditions using a special bilinear form. The resulting boundary value problem is solved using a collocation method. We demonstrate results, showing homoclinic orbits in a model for neural activity and travelling wave solutions to the delayed Hodgkin–Huxley equation. Our numerical tests indicate convergence behaviour that corresponds to known theoretical results for ODEs and periodic boundary value problems for DDEs.     

Parallel iteration across the steps of high-order Runge-Kutta methods for nonstiff initial value problems

For the parallel integration of nonstiff initial value problems (IVPs), three main approaches can be distinguished: approaches based on “parallelism across the problem”, on “parallelism across the method” and on “parallelism across the steps”. The first type of parallelism does not require special integration methods and can be exploited within any available IVP solver. The method-parallelism approach received much attention, particularly within the class of explicit Runge-Kutta methods originating from fixed point iteration of implicit Runge-Kutta methods of Gaussian type. The construction and implementation on a parallel machine of such methods is extremely simple. Since the computational work per processor is modest with respect to the number of data to be exchanged between the various processors, this type of parallelism is most suitable for shared memory systems. The required number of processors is roughly half the order of the generating Runge-Kutta method and the speed-up with respect to a good sequential IVP solver is about a factor 2. The third type of parallelism (step-parallelism) can be achieved in any IVP solver based on predictor-corrector iteration and requires the processors to communicate after each full iteration. If the iterations have sufficient computational volume, then the step-parallel approach may be suitable for implementation on distributed memory systems. Most step-parallel methods proposed so far employ a large number of processors, but lack the property of robustness, due to a poor convergence behaviour in the iteration process. Hence, the effective speed-up is rather poor. The dynamic step-parallel iteration process proposed in the present paper is less massively parallel, but turns out to be sufficiently robust to achieve speed-up factors up to 15.     

Continuous block implicit hybrid one-step methods for ordinary and delay differential equations

A class of high order continuous block implicit hybrid one-step methods has been proposed to solve numerically initial value problems for ordinary and delay differential equations. The convergence and Aω-stability of the continuous block implicit hybrid methods for ordinary differential equations are studied. Alternative form of continuous extension is constructed such that the block implicit hybrid one-step methods can be used to solve delay differential equations and have same convergence order as for ordinary differential equations. Some numerical experiments are conducted to illustrate the efficiency of the continuous methods.     

Dynamics of two-cell systems with discrete delays

We consider the system of delay differential equations (DDE) representing the models containing two cells with time-delayed connections. We investigate global, local stability and the bifurcations of the trivial solution under some generic conditions on the Taylor coefficients of the DDE. Regarding eigenvalues of the connection matrix as bifurcation parameters, we obtain codimension one bifurcations (including pitchfork, transcritical and Hopf bifurcation) and Takens-Bogdanov bifurcation as a codimension two bifurcation. For application purposes, this is important since one can now identify the possible asymptotic dynamics of the DDE near the bifurcation points by computing quantities which depend explicitly on the Taylor coefficients of the original DDE. Finally, we show that the analytical results agree with numerical simulations.     

Efficient numerical realization of discontinuous Galerkin methods for temporal discretization of parabolic problems

We present an efficient and easy to implement approach to solving the semidiscrete equation systems resulting from time discretization of nonlinear parabolic problems with discontinuous Galerkin methods of order $r$ . It is based on applying Newton’s method and decoupling the Newton update equation, which consists of a coupled system of $r+1$ elliptic problems. In order to avoid complex coefficients which arise inevitably in the equations obtained by a direct decoupling, we decouple not the exact Newton update equation but a suitable approximation. The resulting solution scheme is shown to possess fast linear convergence and consists of several steps with same structure as implicit Euler steps. We construct concrete realizations for order one to three and give numerical evidence that the required computing time is reduced significantly compared to assembling and solving the complete coupled system by Newton’s method.     

Numerical simulations of water–gas flow in heterogeneous porous media with discontinuous capillary pressures by the concept of global pressure

We present an approach and numerical results for a new formulation modeling immiscible compressible two-phase flow in heterogeneous porous media with discontinuous capillary pressures. The main feature of this model is the introduction of a new global pressure, and it is fully equivalent to the original equations. The resulting equations are written in a fractional flow formulation and lead to a coupled degenerate system which consists of a nonlinear parabolic (the global pressure) equation and a nonlinear diffusion–convection one (the saturation equation) with nonlinear transmission conditions at the interfaces that separate different media. The resulting system is discretized using a vertex-centred finite volume method combined with pressure and flux interface conditions for the treatment of heterogeneities. An implicit Euler approach is used for time discretization. A Godunov-type method is used to treat the convection terms, and the diffusion terms are discretized by piecewise linear conforming finite elements. We present numerical simulations for three one-dimensional benchmark tests to demonstrate the ability of the method to approximate solutions of water–gas equations efficiently and accurately in nuclear underground waste disposal situations.     

An iterative solver for the Oseen problem and numerical solution of incompressible Navier–Stokes equations

Incompressible unsteady Navier–Stokes equations in pressure–velocity variables are considered. By use of the implicit and semi‐implicit schemes presented the resulting system of linear equations can be solved by a robust and efficient iterative method. This iterative solver is constructed for the system of linearized Navier–Stokes equations. The Schur complement technique is used. We present a new approach of building a non‐symmetric preconditioner to solve a non‐symmetric problem of convection–diffusion and saddle‐point type. It is shown that handling the differential equations properly results in constructing efficient solvers for the corresponding finite linear algebra systems. The method has good performance for various ranges of viscosity and can be used both for 2D and 3D problems. The analysis of the method is still partly heuristic, however, the mathematically rigorous results are proved for certain cases. The proof is based on energy estimates and basic properties of the underlying partial differential equations. Numerical results are provided. Additionally, a multigrid method for the auxiliary convection–diffusion problem is briefly discussed. Copyright © 1999 John Wiley & Sons, Ltd.     

A Jacobi–Davidson method for two‐real‐parameter nonlinear eigenvalue problems arising from delay‐differential equations

The critical delays of a delay‐differential equation can be computed by solving a nonlinear two‐parameter eigenvalue problem. The solution of this two‐parameter problem can be translated to solving a quadratic eigenvalue problem of squared dimension. We present a structure preserving QR‐type method for solving such quadratic eigenvalue problem that only computes real‐valued critical delays; that is, complex critical delays, which have no physical meaning, are discarded. For large‐scale problems, we propose new correction equations for a Newton‐type or Jacobi–Davidson style method, which also forces real‐valued critical delays. We present three different equations: one real‐valued equation using a direct linear system solver, one complex valued equation using a direct linear system solver, and one Jacobi–Davidson style correction equation that is suitable for an iterative linear system solver. We show numerical examples for large‐scale problems arising from PDEs. Copyright © 2012 John Wiley & Sons, Ltd.     

Computing breaking points in implicit delay differential equations

Systems of implicit delay differential equations, including state-dependent problems, neutral and differential-algebraic equations, singularly perturbed problems, and small or vanishing delays are considered. The numerical integration of such problems is very sensitive to jump discontinuities in the solution or in its derivatives (so-called breaking points). In this article we discuss a new strategy – peculiar to implicit schemes – that allows codes to detect automatically and then to compute very accurately those breaking points which have to be inserted into the mesh to guarantee the required accuracy. In particular for state-dependent delays, where breaking points are not known in advance, this treatment leads to a significant improvement in accuracy. As a theoretical result we obtain a general convergence theorem which was missing in the literature (see Bellen and Zennaro, Numerical Methods for Delay Differential Equations, Oxford University Press, Oxford, 2003). Furthermore, as a useful by-product, we design strategies that are able to detect points of non-uniqueness or non-existence of the solution so that the code can terminate when such a situation occurs. A new version of the code RADAR5 together with drivers for some real-life problems is available on the homepages of the authors. Supported by the Swiss National Science Foundation, project # 200020-101647.