Symmetric linear multistep methods

Some important early contributions of Germund Dahlquist are reviewed and their impact to recent developments in the numerical solution of ordinary differential equations is shown. This work is an elaboration of a talk presented in the Dahlquist session at the SciCADE05 conference in Nagoya. In memory of Germund Dahlquist (1925–2005).AMS subject classification (2000) 65L06, 65P10     

Generating numerical algorithms using a computer algebra system

An useful application of computer algebra systems is the generation of algorithms for numerical computations. We have shown in Gander and Gruntz (SIAM Rev., 1999) how computer algebra can be used in teaching to derive numerical methods. In this paper we extend this work, using essentially the capability of computer algebra system to construct and manipulate the interpolating polynomial and to compute a series expansion of a function. We will automatically generate formulas for integration and differentiation with error terms and also generate multistep methods for integrating differential equations. In memory of Germund Dahlquist (1925–2005).AMS subject classification (2000) 65D25, 65D30, 65D32, 65L06     

Dahlquist’s classical papers on stability theory

This text, which is based on the author’s talk in honour of G. Dahlquist at the SciCade05 meeting in Nagoya, describes the two classical papers from 1956 and 1963 of Dahlquist and their enormous impact on the research of decades to come; it also allows the author to present a personal testimony of his never ending admiration for the scientific and personal qualities of this great man.In memory of Germund Dahlquist (1925–2005).AMS subject classification (2000) 65F05, 65F07     

An iterative Lavrentiev regularization method

This paper presents an iterative method for the computation of approximate solutions of large linear discrete ill-posed problems by Lavrentiev regularization. The method exploits the connection between Lanczos tridiagonalization and Gauss quadrature to determine inexpensively computable lower and upper bounds for certain functionals. This approach to bound functionals was first described in a paper by Dahlquist, Eisenstat, and Golub. A suitable value of the regularization parameter is determined by a modification of the discrepancy principle. In memory of Germund Dahlquist (1925–2005).AMS subject classification (2000) 65R30, 65R32, 65F10     

Adaptive partitioning techniques for ordinary differential equations

Many stiff systems of ordinary differential equations (ODEs) modeling practical problems can be partitioned into loosely coupled subsystems. In this paper the objective of the partitioning is to permit the numerical integration of one time step to be performed as the solution of a sequence of small subproblems. This reduces the computational complexity compared to solving one large system and permits efficient parallel execution under appropriate conditions. The subsystems are integrated using methods based on low order backward differentiation formulas.This paper presents an adaptive partitioning algorithm based on a classical graph algorithm and techniques for the efficient evaluation of the error introduced by the partitioning.The power of the adaptive partitioning algorithm is demonstrated by a real world example, a variable step-size integration algorithm which solves a system of ODEs originating from chemical reaction kinetics. The computational savings are substantial. In memory of Germund Dahlquist (1925–2005).AMS subject classification (2000) 65L06, 65Y05     

Towards explicit methods for differential algebraic equations

Explicit methods have previously been proposed for parabolic PDEs and for stiff ODEs with widely separated time constants. We discuss ways in which Differential Algebraic Equations (DAEs) might be regularized so that they can be efficiently integrated by explicit methods. The effectiveness of this approach is illustrated for some simple index three problems. In memory of Germund Dahlquist (1925–2005).AMS subject classification (2000) 65-L80, 34-04     

The logarithmic norm. History and modern theory

In his 1958 thesis Stability and Error Bounds, Germund Dahlquist introduced the logarithmic norm in order to derive error bounds in initial value problems, using differential inequalities that distinguished between forward and reverse time integration. Originally defined for matrices, the logarithmic norm can be extended to bounded linear operators, but the extensions to nonlinear maps and unbounded operators have required a functional analytic redefinition of the concept.This compact survey is intended as an elementary, but broad and largely self-contained, introduction to the versatile and powerful modern theory. Its wealth of applications range from the stability theory of IVPs and BVPs, to the solvability of algebraic, nonlinear, operator, and functional equations. In memory of Germund Dahlquist (1925–2005).AMS subject classification (2000) 65L05     

Reducibility and contractivity of Runge–Kutta methods revisited

The exact relation between a Cooper-like reducibility concept and the reducibilities introduced by Hundsdorfer, Spijker and by Dahlquist and Jeltsch is given. A shifted Runge–Kutta scheme and a transplanted differential equation is introduced in such a fashion that the input/output relation remains unchanged under these transformations. This gives a technique to prove stability and contractivity results. This is demonstrated on the example of contractivity disks. AMS subject classification (2000) 65L07     

A Class of Explicit Exponential General Linear Methods

In this paper, we consider a class of explicit exponential integrators that includes as special cases the explicit exponential Runge–Kutta and exponential Adams–Bashforth methods. The additional freedom in the choice of the numerical schemes allows, in an easy manner, the construction of methods of arbitrarily high order with good stability properties. We provide a convergence analysis for abstract evolution equations in Banach spaces including semilinear parabolic initial-boundary value problems and spatial discretizations thereof. From this analysis, we deduce order conditions which in turn form the basis for the construction of new schemes. Our convergence results are illustrated by numerical examples. AMS subject classification (2000) 65L05, 65L06, 65M12, 65J10     

One-leg variable-coefficient formulas for ordinary differential equations and local–global step size control

In this paper we discuss a class of numerical algorithms termed one-leg methods. This concept was introduced by Dahlquist in 1975 with the purpose of studying nonlinear stability properties of multistep methods for ordinary differential equations. Later, it was found out that these methods are themselves suitable for numerical integration because of good stability. Here, we investigate one-leg formulas on nonuniform grids. We prove that there exist zero-stable one-leg variable-coefficient methods at least up to order 11 and give examples of two-step methods of orders 2 and 3. In this paper we also develop local and global error estimation techniques for one-leg methods and implement them with the local–global step size selection suggested by Kulikov and Shindin in 1999. The goal of this error control is to obtain automatically numerical solutions for any reasonable accuracy set by the user. We show that the error control is more complicated in one-leg methods, especially when applied to stiff problems. Thus, we adapt our local–global step size selection strategy to one-leg methods.     

On the computation of highly oscillatory multivariate integrals with stationary points

We consider two types of highly oscillatory bivariate integrals with a nondegenerate stationary point. In each case we produce an asymptotic expansion and two kinds of quadrature algorithms: an asymptotic method and a Filon-type method. Our results emphasize the crucial role played by the behaviour at the stationary point and by the geometry of the boundary of the underlying domain. In memory of Germund Dahlquist (1925–2005). AMS subject classification (2000) Primary 65D32     

Numerical method for coupling the macro and meso scales in stochastic chemical kinetics

A numerical method is developed for simulation of stochastic chemical reactions. The system is modeled by the Fokker–Planck equation for the probability density of the molecular state. The dimension of the domain of the equation is reduced by assuming that most of the molecular species have a normal distribution with a small variance. The numerical approximation preserves properties of the analytical solution such as non-negativity and constant total probability. The method is applied to a nine dimensional problem modelling an oscillating molecular clock. The oscillations stop at a fixed point with a macroscopic model but they continue with our two dimensional, mixed macroscopic and mesoscopic model. Dedicated to the memory of Germund Dahlquist (1925–2005). AMS subject classification (2000)  65M20, 65M60     

Asymptotic Mean-Square Stability of Two-Step Methods for Stochastic Ordinary Differential Equations

We deal with linear multi-step methods for SDEs and study when the numerical approximation shares asymptotic properties in the mean-square sense of the exact solution. As in deterministic numerical analysis we use a linear time-invariant test equation and perform a linear stability analysis. Standard approaches used either to analyse deterministic multi-step methods or stochastic one-step methods do not carry over to stochastic multi-step schemes. In order to obtain sufficient conditions for asymptotic mean-square stability of stochastic linear two-step-Maruyama methods we construct and apply Lyapunov-type functionals. In particular we study the asymptotic mean-square stability of stochastic counterparts of two-step Adams–Bashforth- and Adams–Moulton-methods, the Milne–Simpson method and the BDF method. AMS subject classification (2000) 60H35, 65C30, 65L06, 65L20     

Nonnormality and stochastic differential equations

A highly nonnormal Jacobian may give rise to large transients. This behaviour has been shown to have implications for (a) the relevance of linearising a nonlinear system and (b) the timestep restrictions required to keep a numerical method stable. Here, we show that nonnormality also manifests itself for stochastic differential equations. We give an example of a family of systems that is stable without noise, but can be made exponentially unstable in mean-square by a noise perturbation that shrinks to zero as the nonnormality increases. We then show via finite-time convergence theory that an Euler approximation shares the same property, giving a discrete analogue of the result. In memory of Germund Dahlquist (1925–2005).AMS subject classification (2000) 65C30, 34F05     

A minimum residual algorithm for solving linear systems

A minimum residual algorithm for solving a large linear system (I+S)x=b, with b∈ℂ ⁿ and S∈ℂ ^n×n being readily invertible, is proposed. For this purpose Krylov subspaces are generated by applying S and S ^-1 cyclically. The iteration can be executed with every linear system once the coefficient matrix has been split into the sum of two readily invertible matrices. In case S is a translation and a rotation of a Hermitian matrix, a five term recurrence is devised. In memory of Germund Dahlquist (1925–2005).AMS subject classification (2000) 65F10     

Some observations on local least squares

In previous work we introduced a construction to produce biorthogonal multiresolutions from given subdivisions. The approach involved estimating the solution to a least squares problem by means of a number of smaller least squares approximations on local portions of the data. In this work we use a result by Dahlquist, et al. on the method of averages to make observational comparisons between this local least squares estimation and full least squares approximation. We have explored examples in two problem domains: data reduction and data approximation. We observe that, particularly for design matrices with a repetitive pattern of column entries, the least squares solution is often well estimated by local least squares, that the estimation rapidly improves with the size of the local least squares problems, and that the quality of the estimate is largely independent of the size of the full problem. In memory of Germund Dahlquist (1925–2005).AMS subject classification (2000) 93E24     

First- and second-order methods for semidefinite programming

 In this paper, we survey the most recent methods that have been developed for the solution of semidefinite programs. We first concentrate on the methods that have been primarily motivated by the interior point (IP) algorithms for linear programming, putting special emphasis in the class of primal-dual path-following algorithms. We also survey methods that have been developed for solving large-scale SDP problems. These include first-order nonlinear programming (NLP) methods and more specialized path-following IP methods which use the (preconditioned) conjugate gradient or residual scheme to compute the Newton direction and the notion of matrix completion to exploit data sparsity. Received: December 16, 2002 / Accepted: May 5, 2003 Published online: May 28, 2003 Key words. semidefinite programming – interior-point methods – polynomial complexity – path-following methods – primal-dual methods – nonlinear programming – Newton method – first-order methods – bundle method – matrix completion The author's research presented in this survey article has been supported in part by NSF through grants INT-9600343, INT-9910084, CCR-9700448, CCR-9902010, CCR-0203113 and ONR through grants N00014-93-1-0234, N00014-94-1-0340 and N00014-03-1-0401. Mathematics Subject Classification (2000): 65K05, 90C06, 90C22, 90C25, 90C30, 90C51     

Second order Runge–Kutta methods for Stratonovich stochastic differential equations

The weak approximation of the solution of a system of Stratonovich stochastic differential equations with a m–dimensional Wiener process is studied. Therefore, a new class of stochastic Runge–Kutta methods is introduced. As the main novelty, the number of stages does not depend on the dimension m of the driving Wiener process which reduces the computational effort significantly. The colored rooted tree analysis due to the author is applied to determine order conditions for the new stochastic Runge–Kutta methods assuring convergence with order two in the weak sense. Further, some coefficients for second order stochastic Runge–Kutta schemes are calculated explicitly. AMS subject classification (2000)  65C30, 65L06, 60H35, 60H10     

Local error estimation for multistep collocation methods

Multistep collocation methods for initial value problems in ordinary differential equations are known to be a subclass of multistep Runge-Kutta methods and a generalisation of the well-known class of one-step collocation methods as well as of the one-leg methods of Dahlquist. In this paper we derive an error estimation method of embedded type for multistep collocation methods based on perturbed multistep collocation methods. This parallels and generalizes the results for one-step collocation methods by Nørsett and Wanner. Simple numerical experiments show that this error estimator agrees well with a theoretical error estimate which is a generalisation of an error estimate first derived by Dahlquist for one-leg methods.     

Linearly implicit methods for nonlinear evolution equations

Summary.  We construct and analyze combinations of rational implicit and explicit multistep methods for nonlinear evolution equations and extend thus recent results concerning the discretization of nonlinear parabolic equations. The resulting schemes are linearly implicit and include as particular cases implicit–explicit multistep schemes as well as the combination of implicit Runge–Kutta schemes and extrapolation. We establish optimal order error estimates. The abstract results are applied to a third–order evolution equation arising in the modelling of flow in a fluidized bed. We discretize this equation in space by a Petrov–Galerkin method. The resulting fully discrete schemes require solving some linear systems to advance in time with coefficient matrices the same for all time levels. Received October 22, 2001 / Revised version received April 22, 2002 / Published online December 13, 2002 Mathematics Subject Classification (1991): Primary 65M60, 65M12; Secondary 65L06 Correspondence to: G. Akrivis