Numerical Analysis and Computational Solution of Integro-Differential Equations

Abstract

The aim of this paper is to describe the current state of the numerical analysis and the computational solution of non-standard integro-differential equations of Volterra and Fredholm types that arise in various applications. In order to do so, we first give a brief review of recent results concerning the numerical analysis of standard (ordinary and partial) Volterra and Fredholm integro-differential equations, with the focus being on collocation and (continuous and discontinuous) Galerkin methods. In the second part of the paper we look at the extension of these results to various classes of non-standard integro-differential equations type that arise as mathematical models in applications. We shall see that in addition to numerous open problems in the numerical analysis of such equations, many challenges in the computational solution of non-standard Volterra and Fredholm integro-differential equations are waiting to be addressed.

Dedicated to Ian Sloan, with my best wishes on your 80th birthday.

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

1 Introduction

In applications integro-differential equations (IDEs) of Volterra or Fredholm type often arise in ‘non-standard’ form. While the numerical analysis and the computational solution of standard IDEs are now well understood, this is largely not true for many of their non-standard versions. Thus, the aim of this paper is to present first a concise overview of collocation and Galerkin methods for standard Volterra and Fredholm IDEs (with the focus being on the former class of equations) and then to describe various classes of non-standard IDEs where the analysis and the implementation of those numerical schemes is rather incomplete. Owing to limitation of space we will deal with partial (e.g. parabolic) IDEs only in passing, as the spatial discretization of such IDEs leads to a (usually large) system of IDEs in time.

1.1 Standard Volterra Integro-Differential Equations

The generic (standard) forms of linear and nonlinear first-order Volterra integro-differential equations (VIDEs) are respectively given by

$$\displaystyle \begin{aligned} u'(t) = a(t)u(t) + f(t) + \int _{0}^{t} (t-s)^{\alpha -1}K(t,s)u(s)\,ds, \;\, t \in I := [0,T], \end{aligned} $$

(1)

and

$$\displaystyle \begin{aligned} u'(t) = F(t,u(t)) + \int _{0}^{t} (t-s)^{\alpha -1}k(t,s,u(s))\,ds, \;\, t \in I \;\, (0 < \alpha \leq 1), \end{aligned} $$

(2)

with 0 < α ≤ 1 and complemented by an initial condition u(0) = u₀. The kernels K = K(t, s) and k = k(t, s, u) are assumed to be continuous on their respective domains D := {(t, s) : 0 ≤ s ≤ t ≤ T} and $D \times {\mathbb {R}}\,$. If 0 < α < 1 we will refer to (1) and (2) as weakly singular VIDEs.

In applications, nonlinear VIDEs usually occur in Hammerstein form; that is, the function k(t, s, u) in (2) is

$$\displaystyle \begin{aligned} k(t,s,u) = K(t,s)G(s,u), \end{aligned} $$

(3)

where G = G(s, u) is a smooth function in s and u.

The spatial discretization (by, e.g., finite element or finite difference techniques) of parabolic partial VIDEs for u = u(t, x), for example

$$\displaystyle \begin{aligned} \frac{\partial u}{\partial t} = \mathcal{A}u + \int _{0}^{t}(t-s)^{\alpha -1} K(t,s)(\mathcal{B}u)(s,\cdot )\,ds, \;\, x \in \varOmega \subset {\mathbb{R}}^d, \; t \in I, \end{aligned} $$

(4)

where $\mathcal {A}$ denotes a linear, uniformly elliptic spatial differential operator (e.g. $\mathcal {A} = \varDelta$, the spatial Laplace operator) and $\mathcal {B}$ is a spatial differential operator of order not exceeding 2, leads to a (usually very large) system of VIDEs (1). If the partial VIDE is of hyperbolic type, e.g.

$$\displaystyle \begin{aligned} \frac{\partial ^2 u}{\partial t^2} = \mathcal{A}u + \int _{0}^{t} (t-s)^{\alpha -1} K(t,s)(\mathcal{B}u)(s,\cdot )\,ds, \end{aligned} $$

(5)

spatial discretization yields a (large) system of ordinary second-order VIDEs that is the matrix analogue of the VIDE

$$\displaystyle \begin{aligned} u^{(r)}(t) = \sum _{j=0}^{r-1} a_j(t)u^{(j)}(t) + f(t) + \int _{0}^{t} \sum _{j=0}^{r} K_j(t,s)u^{(j)}(s)\,ds, \;\, t \in I, \end{aligned} $$

(6)

with r = 2.

1.2 Non-standard Integro-Differential Equations

VIDEs arising in the mathematical modelling of physical or biological phenomena (for example, in materials with memory, in population dynamics, and in chemical reaction-diffusion processes) often occur in ‘non-standard’ form. Typical examples are

$$\displaystyle \begin{aligned} u'(t) = F(t,u(t)) + \int _{0}^{t} k(t-s)G(u(t),u(s))\,ds, \;\, u(0) = u_0; \end{aligned} $$

(7)

$$\displaystyle \begin{aligned} \varepsilon u'(t) = F(t,u(t)) + \int _{-\infty }^{t} k(t-s)G(u(t),u(s))\,ds, \;\, t> 0 \;\, (0 < \varepsilon \ll 1) \end{aligned} $$

(8)

(singularly perturbed VIDE), with u(t) = ϕ(t), (t ≤ 0); and

$$\displaystyle \begin{aligned} u'(t) = a(t)u(t) + f(t) + \int _{0}^{t}K(t,s)G(u(t-s))G(u(s))\,ds, \;\, u(0) = u_0 \end{aligned} $$

(9)

(generalized auto-convolution VIDE). A representative example corresponds to G(u) = u ^β (β > 0).

In these VIDEs the nonlinearity under the integral sign does not only depend on u(s) but also on u(t) or on u(t − s). We illustrate this, also for further reference, by means of six representative examples. They show that these equations may also depend on a (constant or variable) delay τ > 0.

Example 1 (Volterrra [95,96,97,98]; see also Brunner [17])

The system of VIDEs

$$\displaystyle \begin{aligned} \begin{array}{rcl} \frac{dN_1(t)}{dt} &\displaystyle = &\displaystyle N_1(t) \Big (\varepsilon _1 -\gamma _1N_2(t) - \int _{t-\tau }^{t}F_1(t-s)N_1(s)\,ds \Big ), {} \end{array} \end{aligned} $$

(10)

$$\displaystyle \begin{aligned} \begin{array}{rcl} \frac{dN_2(t)}{dt} &\displaystyle = &\displaystyle N_2(t) \Big (-\varepsilon _2 + \gamma _2N_1(t) - \int _{t-\tau }^{t} F_2(t-s)N_2(s)\,ds \Big ),{} \end{array} \end{aligned} $$

(11)

where the ε_i and γ_i are given positive parameters, is a mathematical model describing the size of the populations N₁(t) and N₂(t) of interacting predators and preys. The integral operators describing these VIDEs contain a constant delay τ > 0. (See also Cushing [38, Ch. 4] for related population growth models of interacting species.)

Example 2 (Markowich and Renardy [65, 66])

The non-standard VIDE

$$\displaystyle \begin{aligned} \mu u'(t) = b(t)u^{\beta }(t) + \int _{-\infty }^{t}k(t-s)\Big (\frac{u^3(t)}{u^2(s)}-u(s)\Big )\,ds,\;\, t \geq 0, \end{aligned} $$

(12)

is a mathematical model for the stretching (and recovery) of a filament or a sheet of a certain molten polymer under a prescribed force. The constant μ ≥ 0 is related to the Newtonian contribution to viscosity, and β = 2 (polymeric filament) or β = 1∕2 (polymeric sheet). For small parameters 0 < μ ≪ 1 this is a singularly perturbed VIDE. (See also Lodge et al. [58] and Jordan [48] for related mathematical models.)

Example 3 (Janno and von Wolfersdorf [47], von Wolfersdorf and Janno [99])

A particular case of the VIDE of auto-convolution type,

$$\displaystyle \begin{aligned} u'(t) = a(t)u(t) + f(t) + \int _{0}^{t}K(t,s)u(t-s)u(s)\,ds, \;\, t \geq 0, \end{aligned} $$

(13)

namely,

$$\displaystyle \begin{aligned} u'(t) + \frac{\gamma }{t}\,u(t) = a(t) \int _{0}^{t}u(t-s)u(s)\,ds, \, t > 0, \end{aligned} $$

(14)

arises in the theory of Burgers’ turbulence. Details on the physical background of the model can be found in the above papers and their references.

Example 4 (Burns et al. [32])

The mathematical modelling of the elastic motions of a 3-degree of freedom airfoil with flap in a 2-dimensional incompressible flow leads to a system of neutral Volterra functional differential equations of the form

$$\displaystyle \begin{aligned} \frac{d}{dt} \Big ( A_0u(t) - \int _{-\tau }^{0} A_1(s)u(t+s)\,ds \Big ) = B_0u(t) + B_1u(t-\tau )+ f(t),\;\, t > 0 \end{aligned} $$

(15)

(τ > 0), with A₀, A₁(⋅) and B₀, B₁ denoting square matrices in ${\mathbb {R}}^{d\times d}$ (where d = 8). The matrix A₀ is singular (det A₀ = 0 but rank A₀ ≥ 1); typically, its last row consists of zeros. Compare also Ito and Turi [46] for details and additional references.

Example 5 (Doležal [39, Ch. 5])

The related system of integro-differential algebraic equations (IDAEs)

$$\displaystyle \begin{aligned} A(t)u'(t) + B(t)u(t) = f(t) + \int _{0}^{t}(t-s)^{\alpha -1}K(t,s)u(s)\,ds, \;\, t \geq 0, \end{aligned} $$

(16)

with α = 1, arises in the theory of electrical networks. Here, A(⋅), B(⋅) and K(⋅, ⋅) are square matrices in ${\mathbb {R}}^{d\times d}\, (d \geq 2)$, with det A(t) = 0 for all t ≥ 0 and rank A(t) > 0. A similar system of IDAEs occurs in the mathematical modelling of a hydraulic circuit that feeds on a combustion process (cf. Nassirharand [78]). The paper by Bulatov et al. [31] is concerned with the theory of IDAEs (16).

Example 6

Population growth models (Cushing [38]):

$$\displaystyle \begin{aligned} u'(t) = u(t) \Big (1-\int _{-\infty }^{t} k(t-s)u(s)\,ds \Big ), \;\, t > 0. \end{aligned} $$

(17)

See also Aves et al. [4] and its references.

Example 7

Thermal behavior for a confined reactive gas (Bebernes and Kassoy [8], Bebernes and Bressan [6]):

$$\displaystyle \begin{aligned} u_t - \varDelta u = \delta \mathrm{e}^{u} +\big ( (\gamma -1)/\gamma \big )\big (1/\mathrm{vol}(\varOmega )\big ) \int _{\varOmega }u_t(\cdot , y)\,dy , \end{aligned} $$

(18)

with u(t, x) = 0 (x ∈ ∂Ω, t > 0), u(0, x) = u₀(x) (where $\varOmega \in {\mathbb {R}}^{n}$ is bounded with boundary ∂Ω), and δ > 0, γ = 1 or γ > 1. Note that this (Fredholm) integro-differential equation is implicit in u_t. The monograph by Bebernes and Eberly [7] conveys the general framework of such combustion problems.

Example 8

Local chemical reaction-diffusion processes (Chadam et al. [35], Chadam and Yin [34]): The VIDE

$$\displaystyle \begin{aligned} u_t - \varDelta u = \int _{\varOmega }H(u(\cdot ,y))\,dy, \;\, t > 0, \; x \in \varOmega \subset {\mathbb{R}}^d , \end{aligned} $$

(19)

complemented by homogeneous Dirichlet or Neumann boundary conditions on ∂Ω, represents a mathematical model of chemical reaction-diffusion processes in which, owing to the effects of a catalyst, the reaction occurs only at some local sites. A typical example corresponds to H(u) = e^u. For certain (large) initial data u(0, x) ≥ 0 the solution blows up in finite time.

Example 9

Non-local reaction-diffusion equations with finite-time blow-up (Souplet [89], Quittner and Souplet [83, Ch. V]):

$$\displaystyle \begin{aligned} u_t - \varDelta u = a \int _{0}^{t}u^p(s)\,ds - bu^q, \;\, x \in \varOmega \subset {\mathbb{R}}^d \end{aligned} $$

(20)

(a > 0, b > 0, p, q ≥ 1), with u(0, x) = u₀(x) ≥ 0 (x ∈ Ω), u(t, x) = 0 (x ∈ ∂Ω, t ≥ 0). For u₀ with u₀(x)≢0, the solution blows up in finite time T_b (i.e. ∥u(t, ⋅)∥_∞→∞ (as $t \rightarrow T_b^-$) whenever p > q. For p ≤ q the solution exists for all t > 0 but is unbounded: $\,\lim \, \sup _{t \rightarrow \infty } |u(t,\cdot )| = \infty$.

An analogous result holds for a similar partial VIDE containing integrals over both time and space,

$$\displaystyle \begin{aligned} u_t - \varDelta u = a \int _{0}^{t}\int _{\varOmega } k(s)u^p(s,y)\,dy\,ds - bu^q(t,\cdot ). \end{aligned} $$

(21)

Example 10

Dynamics of price adjustment in a single commodity market i (Bélair and Mackey [9]): If D(⋅) and S(⋅) denote, respectively, the demand and supply functions for a particular commodity, and P_D and P_S are the demand and supply prices, then a model for the relative variations in market price P = P(t) is

$$\displaystyle \begin{aligned} \frac{1}{P(t)}P'(t) = F\big (D(P_D),S(P_S)\big ), \;\, t \geq 0, \end{aligned} $$

(22)

subject to some appropriate initial condition. The function F = F(D, S) is the price range function (a simple example is F(D, S) = D − S). The demand price

$$\displaystyle \begin{aligned}P_D(t) = \int _{-\infty }^{t}K_D(t-v)P(v)\,dv \end{aligned}$$

is the weighted average of all the past prices, where K_D(t − s) is a weight attached by the consumer to a past market price P(s) (−∞≤ s ≤ t). The weighting function K_D (the demand price kernel) is assumed to be normalized so that $\,{\displaystyle \int _{0}^{\infty } K_D(s)ds = 1}$. An analogous expression exists for the supply price P_S: it is

$$\displaystyle \begin{aligned}P_S(t) = \int _{-\infty }^{t-T_{\mathrm{min}}} K_S(t-T_{\mathrm{min}}-v)P(v)\,dv, \end{aligned}$$

where T_min denotes the minimum time which must elapse before a decision to alter production is translated into an actual change of supply.

Example 11

Evolution of a spherical flame initiated by a point source energy input and subject to heat loss (Audounet et al. [3], Rouzaud [84]):

$$\displaystyle \begin{aligned} \pi ^{-1/2}\int _{0}^{t}(t-s)^{-1/2}u'(s)\,ds = u(t) \log \big (u(t)\big ) +Eq(t)-\lambda u^3(t), \end{aligned} $$

(23)

with u(0) = 0. Here, the constant E > 0 and the function q(t) ≥ 0 are given; Eq(t) is a point source energy input. It can be shown that there exists a ‘critical value’ λ = λ ^∗ for which the flame always quenches.

The monographs by Prüss [82] and by Appell et al. [2] contain, in addition to the theory of VIDEs, additional applications of (ordinary and partial) VIDEs.

We note that in many of the above examples the numerical analysis and computational treatment of the respective integro-differential equations are as yet little understood.

The paper is organized as follows. In Sect. 2 we give a concise review of results on the optimal (global and local) order of convergence of collocation and (continuous or discontinuous) Galerkin solutions for standard linear VIDEs. The extension of the convergence analysis for collocation and Galerkin-type solutions for various classes of non-standard VIDEs, including equations with delay arguments, integro-algebraic equations and fractional evolution equations, is the subject of Sect. 3. There we describe theoretical and computational issues that are waiting to be addressed. In Sect. 4 we turn our attention to Volterra and Fredholm IDEs whose solutions blow up in finite time. Owing to limitation of space we only briefly discuss partial VIDEs. However, since the first step in the discretization of such problems usually consists in the approximation (e.g. by finite difference of finite element Galerkin techniques) of the spatial derivatives of the solution, the numerical schemes described in this paper can be employed for the subsequent temporal discretization (time-stepping). The aim of the list of references is to guide the reader to papers that reflect the current ‘state of the art’ of the numerical analysis and the computational solution of VIDEs, as well as to papers on integro-differential equations not treated in the present paper.

2 Numerical Analysis of Ordinary VIDEs

In his paper [94] of 1909 (the first paper on applications of partial VIDEs) Volterra makes the following observation:

The problem of solving integro-differential equations constitutes a problem which is fundamentally different from the problems of solving differential equations and integral equations.

As we shall see in the following sections, this comment remains true for the numerical analysis and computational solution of VIDEs.

We first present a brief overview of prominent time-stepping schemes for VIDEs. They include collocation methods, continuous and discontinuous Galerkin methods, and convolution quadrature methods.

2.1 Collocation and Galerkin Spaces

Suppose we want to approximate the solution of an ordinary VIDE (1.1) (we use the notation (1.1) to refer to Eq. (1) in Sect. 1, etc.) on the time interval I := [0, T] (T < ∞), and let I_h := {t_n : 0 = t₀ < t₁ < ⋯ < t_N = T} be a (not necessarily uniform) mesh for I (i.e. an h-discretization of I), with

$$\displaystyle \begin{aligned} h_n := t_{n+1}-t_n, \quad e_n := (t_n,t_{n+1}], \quad h := \max \{h_n: \; 0 \leq n \leq N-1 \}.\end{aligned}$$

The approximating space will be either

$$\displaystyle \begin{aligned} S_m^{(0)}(I_h) := \{v \in C(I): \; v\big |{}_{e_n} \in \mathcal{P}_m \; (0 \leq n \leq N-1)\}, \end{aligned}$$

the space of globally continuous piecewise polynomials of (fixed) degree m ≥ 1 for all e_n ($\mathcal {P}_m = \mathcal {P}_m(e_n)$ denotes the set of (real-valued) polynomials on e_n of degree not exceeding m), or

$$\displaystyle \begin{aligned} S_{m}^{(-1)}(I_h) := \{v: \; v \big |{}_{e_n} \in \mathcal{P}_{m} \; (0 \leq n \leq N-1)\}, \end{aligned}$$

the space of piecewise polynomials of degree m ≥ 0 that may possess finite jump discontinuities at the interior mesh points of I_h. The dimensions of these linear spaces are given respectively by

$$\displaystyle \begin{aligned} \mathrm{dim}\, S_m^{(0)}(I_h) = Nm+1 \qquad \mbox{and} \qquad \mathrm{dim}\, S_{m}^{(-1)}(I_h) = N(m+1). \end{aligned}$$

It is often advantageous (especially when approximating non-smooth solutions of (1.1)) not to use the same polynomial degree m on each subinterval e_n. Thus, an hp-discretization of I is defined as follows: for the given mesh and given nonnegative integers m_i (i = 0, 1, …, N − 1) we consider the degree vector $\, \underline {m} := (m_0, m_1, \ldots , m_{N-1} )$, with $| \underline {m}| := \max \{m_n: \; 0 \leq n \leq N-1 \}$. For d ∈{−1, 0} the corresponding piecewise polynomial spaces are then

$$\displaystyle \begin{aligned} S_{\underline{m}}^{(d)}(I_h) := \{v \in C^d(I): \; v \big|{}_{e_n} \in \mathcal{P}_{m_n} \; (0 \leq n \leq N-1)\} .\end{aligned}$$

(If d = −1 the elements of $S_{ \underline {m}}^{(-1)}(I_h)$ are in general not continuous at the interior points of I_h.) It is easily seen that we have

$$\displaystyle \begin{aligned} \mathrm{dim}\, S_{\underline{m}}^{(0)}(I_h) = \sum _{n=0}^{N-1} m_n + 1 \qquad \mbox{and} \qquad \mathrm{dim}\,S_{\underline{m}}^{(-1)}(I_h) = \sum _{n=0}^{N-1} m_n + N . \end{aligned}$$

In order to obtain high-order collocation or Galerkin approximations to VIDEs with weakly singular kernels whose solutions typically have unbounded second derivatives at t = 0, one will choose a mesh on I = [0, T] that is locally refined near t = 0. Such meshes, denoted by I_h(r, σ), correspond to a grading parameter σ ∈ (0, 1) and r ≥ 1 levels of refinement and are defined by the mesh points

$$\displaystyle \begin{aligned} \{t_{0,0} := 0, \;\, t_{0,\mu } := \sigma ^{r-\mu }t_1 \;(1 \leq \mu \leq r),\;\, t_n \; (1 \leq n \leq N)\}. \end{aligned} $$

(24)

We associate with each subinterval e_0,μ := (t_0,μ, t_0,μ+1] (0 ≤ μ ≤ r − 1) a nonnegative integer m_0,μ; these integers define the initial degree vector $\, \underline {m}_0 := ( \, m_{0,0}, \ldots , m_{0,r-1})$. For d ∈{−1, 0} the corresponding piecewise polynomial spaces are defined by

$$\displaystyle \begin{aligned} &S_{\underline{m}}^{(d)}(I_h(r,\sigma ))\\ &\quad := \{v \in C^d(I): \; v\big |{}_{e_{0,\mu }} \in \mathcal{P}_{m_{0,\mu }} \; (0 \leq \mu \leq r-1); \; v\big |{}_{e_n} \in \mathcal{P}_{m_n} \}, \end{aligned} $$

(25)

where (m₁, …, m_N−1) is the degree vector for the intervals e₁, …, e_N−1. The dimensions of these linear spaces are

$$\displaystyle \begin{aligned} \mathrm{dim}\, S_{\underline{m}}^{(-1)}(I_h(r,\sigma )) = \sum _{k=0}^{r-1}m_{0,k} + \sum _{n=1}^{N-1}m_n + r + N-1 \end{aligned} $$

(26)

and

$$\displaystyle \begin{aligned}\mathrm{dim}\, S_{\underline{m}}^{(0)}(I_h(r,\sigma )) = \sum _{k=0}^{r-1}m_{0,k} + \sum _{n=1}^{N-1} m_n +1, \end{aligned}$$

respectively. These spaces will be used below in the formulation of the hp-versions of collocation and (continuous and discontinuous) Galerkin methods.

2.2 Collocation Time-Stepping

We first recall time-stepping schemes based on collocation in the piecewise polynomial space $S_m^{(0)}(I_h)$ for the VIDE

$$\displaystyle \begin{aligned} u'(t) = a(t)u(t) + f(t) + (\mathcal{V}_{\alpha }u)(t), \;\, t \in I := [0,T], \;\, u(0) = u_0, \end{aligned} $$

(27)

where the Volterra integral operator $\mathcal {V}_{\alpha }: \; C(I) \rightarrow C(I)$ is

$$\displaystyle \begin{aligned} (\mathcal{V}_{\alpha }u)(t) := \int _{0}^{t}(t-s)^{\alpha -1}K(t,s)u(s)\,ds \end{aligned}$$

(0 < α ≤ 1), with K ∈ C(D) (D := {(t, s) : 0 ≤ s ≤ t ≤ T}). Since $\mathrm {dim}\, S_m^{(0)}(I_h) = Nm+1$, we choose the set of collocation points

$$\displaystyle \begin{aligned} X_h := \{ t_{n,i} := t_n+c_ih_n: \; i = 1, \ldots , m \; (0 \leq n \leq N-1)\} \end{aligned} $$

(28)

of cardinality |X_h| = Nm and defined by m ≥ 1 prescribed collocation parameters {c_i : 0 < c₁ < ⋯ < c_m ≤ 1}. The collocation equation defining the collocation solution $u_h \in S_m^{(0)}(I_h)$ for (4) is then given by

$$\displaystyle \begin{aligned} u_h^{\prime}(t) = a(t)u_h(t) + f(t) + (\mathcal{V}_{\alpha }u)(t), \;\, t \in X_h, \end{aligned} $$

(29)

and complemented by the initial condition u_h(0) = u₀.

The local (time-stepping) version of (4) (for t = t_n + vh_n ∈ e_n) has the form

$$\displaystyle \begin{aligned} \begin{array}{rcl} u'(t_n+vh_n) &\displaystyle = &\displaystyle a(t_n+vh_n)u(t_n+vh_n) + f(t_n+vh_n) + H_n(t_n+vh_n) \\ &\displaystyle &\displaystyle + h_n^{\alpha }\int _{0}^{v}(v-s)^{\alpha -1}K(t_n+vh_n,t_n+sh_n)u(t_n+sh_n)\,ds{} \end{array} \end{aligned} $$

(30)

(v ∈ (0, 1]), with the history term

$$\displaystyle \begin{aligned} \begin{array}{rcl} H_n(t) &\displaystyle := &\displaystyle \int _{0}^{t_n} (t-s)^{\alpha -1}K(t,s)u(s)\,ds \\ &\displaystyle = &\displaystyle \sum _{\ell =0}^{n-1} h_{\ell }\int _{0}^{1}(t-(t_{\ell } +sh_{\ell }))^{\alpha -1}K(t,t_{\ell }+sh_{\ell }) u(t_{\ell }+sh_{\ell })\,ds{} \end{array} \end{aligned} $$

(31)

(t = t_n + vh_n ∈ e_n). Thus, the corresponding (local) collocation equation for t_n,i ∈ e_n is

$$\displaystyle \begin{aligned} \begin{array}{rcl} &\displaystyle &\displaystyle u_h^{\prime}(t_{n,i}) - a(t_{n,i})u_h(t_{n,i}) - h_n^{\alpha }\int _{0}^{c_i} (c_i-s)^{\alpha -1}K(t_{n,i},t_n+sh_n)u_h(t_n+sh_n)\,ds \\ &\displaystyle &\displaystyle \qquad = f(t_{n,i}) + \hat{H}_n(t_{n,i}){} \end{array} \end{aligned} $$

(32)

(i = 1, …, m), where the approximation $\hat {H}_n(t)$ to the history term H_n(t) in (8) is

$$\displaystyle \begin{aligned} \hat{H}_n(t) := \int _{0}^{t_n} (t-s)^{\alpha-1}K(t,s)u_h(s)\,ds \;\, (t \in e_n). \end{aligned}$$

In order to obtain the computational form of (9) we set

$$\displaystyle \begin{aligned}Y_{n,i} := u_h^{\prime}(t_{n,i}), \quad L_j(v) := \prod _{k=1,k\neq j}^{m}\frac{v-c_k}{c_j-c_k}, \quad b_j(v) := \int _{0}^v L_j(s)\,ds \;\, (v \in [0,1]). \end{aligned}$$

Since $u_h^{\prime }$ on e_n is a polynomial of degree m − 1 we may write

$$\displaystyle \begin{aligned} u_h^{\prime}(t_n+vh_n) = \sum _{j=1}^m L_j(v)Y_{n,j} \;\, (v \in (0,1]). \end{aligned}$$

This implies that on e_n the collocation approximation u_h has the local representation

$$\displaystyle \begin{aligned} u_h(t_n+vh_n) = u_n + h_n \sum _{j=1}^{m}b_j(v)Y_{n,j} \;\, (v \in [0,1]), \end{aligned} $$

(33)

where u_n := u_h(t_n). It allows us to write the local collocation Eq. (9) in the form

$$\displaystyle \begin{aligned} \begin{array}{rcl} &\displaystyle &\displaystyle Y_{n,i}-h_n a(t_{n,i})\sum _{j=1}^{m}b_{i,j}Y_{n,j}-h_n^2\sum _{j=1}^{m}\int _{0}^{c_i} (c_i-s)^{\alpha -1}K(t_{n,i},t_n+sh_n)b_j(s)ds \cdot Y_{n,j} \\ &\displaystyle &\displaystyle \;\; = f(t_{n,i})+\hat{H}(t_{n,i})+ \Big (a(t_{n,i}) + h_n\int _{0}^{c_i}(c_i-s)^{\alpha -1} K(t_{n,i},t_n+sh_n)ds \Big )u_n,{} \end{array} \end{aligned} $$

(34)

with b_i,j := b_j(c_i). This is a system of m linear algebraic equations for the vector Y_n := (Y_n,1, …, Y_n,m)^T. For a, f ∈ C(I), K ∈ C(D) and 0 < α ≤ 1, it possesses a unique solution $Y_n \in {\mathbb {R}}^m$ for 0 ≤ n ≤ N − 1 and for all meshes I_h with sufficiently small mesh diameter h > 0.

Remark 1

Since the integrals in (11) cannot, in general, be evaluated analytically a further discretization step consisting in approximating these integrals by appropriate numerical quadrature schemes, e.g. m-point interpolatory quadrature formulas with abscissas coinciding with the collocation points will be necessary (cf. Brunner [16] and Remark 2 below).

The attainable order of convergence of the collocation solution $u_h \in S_m^{(0)}(I_h)$ depends strongly on the regularity of the solution u of the VIDE (3). If α = 1, then u essentially inherits the regularity of the data: C ^m data a, f and K imply that u ∈ C ^m+1(I). For 0 < α < 1 this is no longer true: for such C ^m data we obtain in general only u ∈ C ¹(I) ∩ C ^m+1(0, T]: its second derivative behaves like u″(t) ∼ t ^α−1 as t → 0⁺. We summarize these observations in the following theorems (see for example Brunner [16, Ch. 3]).

Theorem 1

Assume that a, f ∈ C ^d(I), K ∈ C ^d(D) (d ≥ m), α = 1, and let $u_h \in S_m^{(0)}(I_h)$ be the collocation solution defined by the collocation Eq.(6), with I_h being (quasi-)uniform.

• (a) If d ≥ m and the collocation parameters {c_i} are chosen arbitrarily, there holds ∥u − u_h∥_∞≤ Ch ^m . The exponent m can in general not be replaced by m + 1.

• (b) If d ≥ m + 1 and if the collocation parameters satisfy the orthogonality condition

  $$\displaystyle \begin{aligned} \int _{0}^{1}\prod _{i=1}^{m} (s-c_i)\,ds = 0, \end{aligned} $$

  (35)

  the attainable order of convergence of u_h is given by ∥u − u_h∥_∞≤ Ch ^m+1 . This holds in particular when the c_i are the (shifted) Gauss-Legendre points (i.e. the zeros of the Legendre polynomial P_m(2s − 1)) or the (shifted) Radau II points (the zeros of P_m(2s − 1) − P_m−1(2s − 1), with c_m = 1).

For sufficiently regular solutions and very special choices of the collocation parameters {c_i} the collocation solution $u_h \in S_m^{(0)}(I_h)$ exhibits a higher order of (local) superconvergence at the mesh points I_h.

Theorem 2

Let the assumptions of Theorem 1 hold and assume that the collocation parameters are such that

$$\displaystyle \begin{aligned} \int _{0}^{1}s^{\nu }\prod _{i=1}^{m}(s-c_i)\,ds = 0 \quad \mathit{\mbox{for}} \quad \nu = 0, \ldots , \kappa -1 \;\, (\kappa \leq m). \end{aligned}$$

Then the optimal order of (local) convergence of $u_h \in S_m^{(0)}(I_h)$ at the points of I _h is

$$\displaystyle \begin{aligned} \max _{1 \leq n \leq N} |u(t_n)-u_h(t_n)| \leq C_dh^{m+\kappa }. \end{aligned}$$

Important special cases are the m Gauss-Legendre points (corresponding to κ = m) and the Radau II points (corresponding to κ = m − 1, with c_m = 1).

Remark 2

The local superconvergence results on I_h remain valid (with different, usually larger, error constants C_d) if the integrals in the collocation Eq. (11) are approximated by m-point interpolatory quadrature formulas whose abscissas are the collocation points. The resulting ‘fully discretized’ collocation equation represents an implicit m-stage Volterra-Runge-Kutta method (Brunner [16, Section 3.2.2]; see also Brunner and van der Houwen [21]).

The general theory of (explicit and implicit) Runge-Kutta is due to Lubich [60] (compare also Brunner and van der Houwen [21, Section 4.2]). Implicit Runge-Kutta time discretization (and their asymptotic stability properties) were studied by Brunner et al. [24]. See also Kauthen [49] on implicit Runge-Kutta methods for singularly perturbed VIDEs.

For VIDEs (4) with weakly singular kernels (corresponding to 0 < α < 1) the above results on the attainable order of convergence of the collocation solution $u_h \in S_m^{(0)}(I_h)$ are no longer valid, owing to the low regularity of the solution u at t = 0. The following theorem is due to Brunner [12], Tang [91] (see also Brunner et al. [25] and Brunner [16, Section 7.2]).

Theorem 3

Let the functions a, f, K in (4) be subject to the assumptions of Theorem 1 , with 0 < α < 1. Then the collocation solution $u_h \in S_m^{(0)}(I_h)$ defined by (6), (7) possesses the following convergence properties:

• (a) If the mesh I_h is (quasi-)uniform, then ∥u − u_h∥_∞≤ C_α h ^1+α for any m ≥ 2.

• (b) If I_h is a (globally) graded mesh whose points are given by t_n = (n∕N)^r T, with r ≥ (m + α)∕(1 + α), then the attainable order of convergence of u_h on I is described by

  $$\displaystyle \begin{aligned} \max _{1 \leq n \leq N} |u(t_n)-u_h(t_n)| \leq C_{\alpha }N^{-(m+\alpha )} \;\, (m \geq 2), \end{aligned}$$

  provided the collocation parameters {c_i} are such that (12) holds.

While the use of globally graded meshes restores the higher order of convergence of collocation solutions for VIDEs (1.1) with 0 < α < 1, it has the drawback that h_n, the size of the subinterval e_n becomes very large (compared to h₀) as n tends to N − 1. There are a number of approaches that avoid this problem.

• (a) Piecewise non-polynomial spline collocation: For a given (uniform) mesh I_h the piecewise polynomial space $S_m^{(0)}(I_h)$ is augmented by an appropriate number (depending on m and α) of non-polynomial basis functions that, on the initial interval e₀, reflect the singular behaviour of higher derivatives of the solution u (cf. Brunner [11]).

• (b) Hybrid collocation: This approach combines non-polynomial spline collocation near the initial point t = 0 and piecewise polynomial spline collocation on e_n with n ≥ 1. It was analyzed for weakly singular Volterra integral equations in Cao et al. [33]; it seems that for weakly singular VIDEs this has not yet been studied.

• (c) hp-collocation with local mesh refinement: As we shall see at the end of Sect. 2.3, piecewise polynomial collocation in $S_{m}^{(0)}(I_h)$ for the VIDE (4) is closely related to discretized cG and dG methods in $S_{m}^{(0)}(I_h)$ and $S_{m-1}^{(-1)}(I_h)$, respectively. Thus, the convergence analysis for the latter approximations to the solution of (4) with 0 < α ≤ 1 can be employed to derive optimal convergence results for hp-collocation methods. This analysis is currently being carried out.

2.3 Continuous and Discontinuous Galerkin Time-Stepping

Based on the variational form of the VIDE (4) the exact continuous Galerkin (cG) equation for $u_h \in S_{m}^{(0)}(I_h)$ has the form

$$\displaystyle \begin{aligned} \langle u_h^{\prime} - au_h,\phi \rangle = \langle f,\phi \rangle + \langle \mathcal{V}_{\alpha } u_h,\phi \rangle \quad \mbox{for all} \quad \phi \in S_m^{(0)}(I_h), \end{aligned} $$

(36)

where the (global) inner product of g and h is given by $\,{\displaystyle \langle g,h \rangle := \int _{I} g(s)h(s)ds}$. (We use the terminology ‘exact Galerkin equation’ to indicate that the inner products are evaluated exactly.) In analogy to the collocation Eq. (6) in $S_{m}^{(0)}(I_h)$ the cG Eq. (13) is complemented by the initial condition u_h(0) = u₀.

The (exact) discontinuous Galerkin (dG) equation in $S_{m}^{(-1)}(I_h)$ for (4) is

$$\displaystyle \begin{aligned} \langle u_h^{\prime} - au_h, \phi \rangle = \langle f,\phi \rangle + \langle \mathcal{V}_{\alpha }u_h,\phi \rangle \quad \mbox{for all} \quad \phi \in S_{m}^{(-1)}(I_h). \end{aligned} $$

(37)

The above cG and dG equations can be written in local ‘time-stepping’ form where the inner products are now taken over the subintervals e_n. We will do this first for the dG Eq. (14) where we have to take into account the jump discontinuities of the test functions $\phi \in S_m^{(-1)}(I_h)$ across the interior points of the mesh I_h. It is readily verified that on e_n the dG equation assumes the form

$$\displaystyle \begin{aligned} \begin{array}{rcl} \int _{e_n} u_h^{\prime}(t)\phi (t)\,dt - U_n^+\phi _n^+ &\displaystyle = &\displaystyle \int _{e_n}a(t)u_h(t)\phi (t)\,dt \\ &\displaystyle &\displaystyle + \int _{e_n} \Big ( \int _{t_n}^t (t-s)^{\alpha -1}K(t,s)u_h(s)ds \Big )\phi (t)\,dt \\{} &\displaystyle &\displaystyle + \; U_n^-\phi _n^+ + \int _{e_n}f(t)\phi (t)dt + \int _{e_n} \hat{H}_n(t)\phi (t)\,dt \end{array} \end{aligned} $$

(38)

for all $\phi \in \mathcal {P}_m(e_n)$ and 0 ≤ n ≤ N − 1 (see also Brunner and Schötzau [20]). Here, we have set

$$\displaystyle \begin{aligned} U_n^+ := u_h(t_n^+), \;\; U_n^- := u_h(t_n^-), \;\; \phi_n^+ := \phi (t_n^+), \end{aligned}$$

and $\hat {H}_n(t)$ is as in (9).

An equation analogous to (15) holds for the cG Eq. (13), except that now there are no jump discontinuity terms (since u_h ∈ C(I)):

$$\displaystyle \begin{aligned} \begin{array}{rcl} \int _{e_n} u_h^{\prime}(t)\phi (t)\,dt &\displaystyle = &\displaystyle \int _{e_n}a(t)u_h(t)\phi (t)\,dt \\ &\displaystyle &\displaystyle \quad +\int _{e_n} \Big (\int _{t_n}^t (t-s)^{\alpha -1}K(t,s) u(s)ds \Big )\phi (t)\,dt \\{} &\displaystyle &\displaystyle \quad + \int _{e_n}f(t)\phi (t)\,ds + \int _{e_n} \hat{H}_n(t)\phi (t)\,dt \end{array} \end{aligned} $$

(39)

for all $\phi \in \mathcal {P}_m(e_{n}) \; (0 \leq n \leq N-1)$.

We cite two representative results on the attainable order of convergence of hp-dG approximations $u_h \in S_{ \underline {m}}^{(-1)}(I_h)$ and $u_h \in S_{ \underline {m}}^{(-1)}(I_h(r,\sigma ))$. The underlying VIDE (1.1) is assumed to be parabolic (that is, a ∈ C(I) satisfies $\underline {a} \leq -a(t) \leq \bar {a} \; (t \in I)$ for some constants $\underline {a} \leq \bar {a} < \infty$), as well as subject to some additional technical assumptions (see Brunner and Schötzau [20] and Mustapha et al. [76] for details).

• (1) In the (atypical) case where the solution u of the VIDE (1.1) with 0 < α < 1 is analytic on I there holds

  $$\displaystyle \begin{aligned} \|u-u_h\|{}_{\infty } \leq C\mathrm{e}^{-b|\underline{m}|}, \end{aligned}$$

  where the constants C and b are independent of the degree vector $\underline {m}$.

• (2) If the data a f, and K are analytic on I and D, respectively, (implying that u is not analytic on I) then there exist degree vectors $\underline {m}_0$ (on e₀) and $\underline {m}$ (on [t₁, T]) so that for the locally geometrically refined mesh I_h(r, σ) the dG solution $u_h \in S_{ \underline {m}}^{(-1)}(I_h(r,\sigma ))$ satisfies

  $$\displaystyle \begin{aligned} \|u-u_h\|{}_{\infty } \leq C \mathrm{e}^{-bM_m^{-1/2}}, \end{aligned}$$

  where

  $$\displaystyle \begin{aligned} M_m := \mathrm{dim}\, S_{\underline{m}}^{(-1)}(I_h(r,\sigma )) = \sum _{k=0}^{r-1}m_{0,k} + \sum _{n=1}^{N-1}m_n + r + N -1, \end{aligned}$$

  (cf. (3)), with constants C and b not depending on the degree vectors.

Remark 3

• (i) While ‘good’ values of the grading parameter σ ∈ (0, 1) can be determined numerically (see Brunner and Schötzau [20, pp. 242–243] for a discussion), the analysis of how to select an optimal grading parameter σ remains to be carried out.

• (ii) Superconvergence results for dG solutions (h-version) for weakly singular VIDEs (1.1) can be found in Mustapha [72]. Analogous results for cG solutions do not seem to have been derived yet.

• (iii) An interesting alternative to hp-dG methods for VIDEs with weakly singular kernels are hp-Petrov-Galerkin methods: here, the approximate solution is sought in the space $S_{m}^{(0)}(I_h)$ while the test space is a space of discontinuous piecewise polynomials. This extension of the hp-dG methods analyzed in [20] can be found in Yi and Guo [100], together with results on the attainable order of convergence of such Petrov-Galerkin solutions.

Since the (local) integrals (inner products) in the Galerkin equations (15) and (16) can in general not be found analytically, they need to be approximated by appropriate quadrature schemes in order to obtain the computational form of these equations. For the dG Eq. (15) the obvious choice are m-point interpolatory (product) quadrature formulas with abscissas 0 ≤ d₀ < d₁ < ⋯ < d_m ≤ 1. For the approximation of the first integral on the right-hand side of (15) this results in

$$\displaystyle \begin{aligned} \begin{array}{rcl} \int _{e_n} a(t)u_h(t)\phi (t)\,dt &\displaystyle = &\displaystyle h_n \int _{0}^{1} a(t_n+vh_n)u_h(t_n+vh_n)\phi (t_n+vh_n)\,dv \\ &\displaystyle \approx &\displaystyle h_n \sum _{j=0}^{m} w_j a(t_n+d_jh_n)u_h(t_n+d_jh_n)\phi (t_n+d_jh_n). \end{array} \end{aligned} $$

The resulting discretized dG equation is related to (but, owing to the finite jump terms, not identical with) the collocation Eq. (9) for $u_h \in S_{m+1}^{(0)}(I_h)$ with the {d_i} as collocation parameters. (This is an extension of Lasaint and Raviart [51] where this relationship was explored for ODEs; see also [20].) On the other hand, the discretized cG Eq. (16) coincides with the collocation Eq. (9) if m-point interpolatory quadrature with abscissas d_i = c_i is used.

Remark 4

• (i) For long-time integration and very large values of N the re-evaluation of the history terms (i.e. the integrals over [0, t_n]) in (15) and (16) for each new interval e_n will become very expensive. In such situations the use of ‘sparse quadrature’ may reduce the computational effort; see for example Sloan and Thomeé [88] or Adolfssson et al. [1].

• (ii) For certain partial VIDEs with convolution kernels, for example

  $$\displaystyle \begin{aligned} \frac{\partial u}{\partial t} + \int _{0}^{t} (t-s)^{\alpha -1}\mathcal{A}u(s)\,ds = f(t), \;\, t \in I,\;\, u(0) = u_0 \end{aligned} $$

  (40)

  where 0 < α < 1 and $\mathcal {A}$ is an elliptic (spatial) differential operator, convolution quadrature based on Laplace transform techniques leads to efficient time-stepping schemes (see for example McLean and Thomée [71], Schädle et al. [85], López-Fernández et al. [59], Mustapha and McLean [73], as well as Cuesta et al. [37] for more general versions of (17) and the use of modified convolution quadrature techniques for time-stepping). A particular example (Fujita [40]) is the VIDE

  $$\displaystyle \begin{aligned} u_t = f + \int _{0}^{t}k(t-s)\varDelta u(s,\cdot )\,ds\;: \end{aligned}$$

  it ‘interpolates’ between heat equation (corresponding to k(t − s) = δ(t − s)) and the wave equation (k(t − s) ≡ 1).

2.4 Collocation and Galerkin Methods for FIDEs

A comprehensive analysis of piecewise polynomial collocation solutions for boundary-value problems for nonlinear Fredholm integro-differential equations

$$\displaystyle \begin{aligned} u^{(r)}(t) &= F\big (t,u(t), \ldots , u^{(r-1)}(t)\big )\\ &\quad + \int _{a}^{b} k\big (t,s,u(s), \ldots , u^{(r)}(s)\big )ds, \;\, t \in [a,b], \end{aligned} $$

(41)

with r ≥ 1, is due to Hangelbroek et al. [45]. In particular, they derived optimal local superconvergence results at the mesh points I_h. Similar local superconvergence results hold for initial-value problems for analogous rth-order VIDEs (cf. Brunner [13]). A boundary-value problem for the nonlinear second-order nonlinear FIDE

$$\displaystyle \begin{aligned} u''(t) + \int _{0}^{1}k(t-s)u^4(s)\,ds = f(t), \;\, t \in [0,1], \end{aligned}$$

arises when studying a coupled system of integro-differential-algebraic equations that models exothermic catalytic combustion in a cylinder. Its numerical treatment by orthogonal collocation methods and the derivation of optimal convergence results are discussed in Ganesh and Spence [42]. An alternative numerical scheme, namely a Petrov-Galerkin method, is analyzed in Ganesh and Sloan [41].

An analysis of projection methods, and in particular of cG methods, for FIDEs (18) can be found in Volk [92, 93]. The second paper also contains superconvergence results for cG solutions.

Parts, Pedas and Tamme [79] and Pedas and Tamme [80] established a comprehensive theory on the regularity of solutions of linear, weakly singular FIDEs

$$\displaystyle \begin{aligned} u'(t) = a(t)u(t) + f(t) + \int _{0}^{T}K(t,s)u(s)\,ds, \;\, t \in [0,T], \end{aligned}$$

where K(t, s) contains weak algebraic or logarithmic singularities, or is bounded but has unbounded derivatives. This is complemented by an equally comprehensive analysis of the order of optimal convergence of piecewise polynomial collocation solutions (see also [81]).

Large systems of FIDEs with dense matrices are encountered in the spatial discretization of linear parabolic FIDEs $u_t + \mathcal {A}u = 0$ where $\mathcal {A}$ is the sum of a second-order elliptic (spatial) differential operator and a linear Fredholm integral operator over some bounded domain $\varOmega \subset {\mathbb {R}}^d$. Such FIDEs arise in the mathematical modelling of stochastic processes in financial mathematics (e.g. in option pricing). Matache et al. [67] proposed a numerical scheme, based on wavelet discretization in space and dG time discretization, in which the (large) dense matrix is replaced by using wavelet compression techniques. The complexity of such schemes is analyzed in Matache et al. [68].

3 Numerical Analysis of Non-standard VIDEs

3.1 Auto-Convolution VIDEs

It was shown in Brunner [14] that for the non-standard VIDE

$$\displaystyle \begin{aligned} u'(t) = a(t)u(t) + f(t) + \int _{0}^{t}K(t,s)G(u(t),u(s))\,ds, \;\, t \in I, \end{aligned} $$

(42)

the optimal orders of (global and local) convergence of collocation solutions $u_h \in S_{m}^{(0)}(I_h)$ described in Theorems 1 and 2 remain valid (see also Brunner et al. [26] for a study of similar time-stepping for analogous partial VIDEs). The proof of these results proceeds along the lines of the one for standard nonlinear VIDEs (cf. Brunner [16]). Discontinuous Galerkin methods for (1) were analyzed in Ma and Brunner [62]; the paper includes the derivation of a posteriori error bounds for the piecewise polynomial spaces $S_{m-1}^{(-1)}(I_h)$ with m = 1 and m = 2.

Consider now the (generalized) auto-convolution VIDE

$$\displaystyle \begin{aligned} u'(t) = a(t)u(t)+f(t) + \int _{0}^{t}K_{\alpha }(t,s)G(u(t-s))G(u(s))\,ds, \;\, t \in I, \end{aligned} $$

(43)

with a ∈ C(I), f ∈ C(I) and K_α(t, s) := (t − s)^α−1 K(t, s) (0 < α ≤ 1, K ∈ C(D)). If G(u) = u the analysis of its solvability differs significantly from one for the non-standard VIDE (1). It follows by a fixed-point argument similar to the one used in Zhang et al. [102] for auto-convolution VIEs that there exists a (small) δ₀ > 0 (depending on $\bar {a} := \|a\|{ }_{\infty }, \, \bar {f} := \|\,f\|{ }_{\infty }$ and $\bar {K} := \|K\|{ }_{\infty }$) so that (1) possesses a unique (local) solution w₀ ∈ C ¹[0, δ₀]. For t ∈ [δ₀, 2δ₀] we may write (1) in the form

$$\displaystyle \begin{aligned} \begin{array}{rcl} u'(t) &\displaystyle = &\displaystyle a(t)u(t)+f(t)+\int _{0}^{\delta _0}K_{\alpha }(t,s)u(t-s)u(s)ds + \int _{\delta _0}^{t}K_{\alpha }(t,s)u(t-s)u(s)ds \\ &\displaystyle = &\displaystyle a(t)u(t)+f(t) + \int _{t-\delta _0}^{\delta _0} K_{\alpha }(t,s)w_0(t-s)w_0(s)\,ds \\ &\displaystyle &\displaystyle \quad + \int _{\delta _0}^{t}\big (K_{\alpha }(t,t-s)+K_{\alpha }(t,s)\big )u(t-s)u(s)\,ds.{} \end{array} \end{aligned} $$

(44)

We see that in (3), t − s ∈ [0, δ₀]. Since u(t − s) = w₀(t − s) is known, (3) is linear in u. This process can be continued to the entire (bounded) interval [δ₀, T] because there exists an integer $\bar {N}$ so that T ∈ [(M − 1)δ₀, Mδ₀].

The above observation implies that the results on the attainable orders of superconvergence of Theorems 1 and 2 are also valid for the auto-convolution VIDE (2) with G(u) = u. (A different, though rather sketchy, convergence analysis for implicit, collocation-based Runge-Kutta methods for (2) with α = 1 and G(u) = u was given in Yuan and Tang [101].)

For more general (nonlinear) functions G in (2), for example G(u) = u ^β with β > 1, the analysis of the optimal order of (global or local) superconvergence of collocation solutions $u_h \in S_m^{(0)}(I_h)$ remains open.

3.2 VIDEs with Delay Arguments

The generic form of a linear Volterra functional integro-differential equation (VFIDE) with (real-valued) delay function θ is

$$\displaystyle \begin{aligned} u'(t) = a(t)u(t) + b(t)u(\theta (t)) + \int _{\theta (t)}^{t}(t-s)^{\alpha -1}K(t,s)u(s)\,ds, \;\, t \in I = [0,T], \end{aligned} $$

(45)

where 0 < α ≤ 1, and θ(t) := t − τ(t) is either a vanishing delay (τ(0) = 0, 0 < θ(t) < t if t > 0) or a non-vanishing delay (τ(t) ≥ τ₀ > 0, t ∈ I). Regularity results for the solutions of weakly singular VFIDES (4) with non-vanishing delays can be found in Brunner and Ma [19]. For (4) with α = 1, optimal (super-)convergence results analogous to the ones in Theorems 1 and 2 were established in Brunner [15]. Shakourifar and Enright [86] studied continuous implicit Runge-Kutta methods for such VFIDEs; an alternative to collocation, using (explicit) continuous Volterra-Runge-Kutta methods together with C ¹ Hermite interpolants at non-mesh points is described in Shakourifar and Enright [87] (compare also [86]). These methods are then used to solve Volterra’s predator-prey system (1.10), (1.11). A very general theoretical framework for the analysis of Runge-Kutta methods for Volterra functional differential equations is due to Lin [52] and Li and Li [53].

If a VFIDE is of the form

$$\displaystyle \begin{aligned} \begin{array}{rcl} u'(t) &\displaystyle = &\displaystyle a(t)u(t)+b(t)u(\theta (t))+ c(t)u'(\theta (t)) \\ &\displaystyle &\displaystyle \quad + \int _{\theta (t)}^{t}(t-s)^{\alpha -1} \big ( K(t,s)u(s) + K_1(t,s)u'(s) \big )ds,{} \end{array} \end{aligned} $$

(46)

it is said to be of neutral type; it may be viewed as the nonlocal analogue of a neutral delay differential equation. The terminology ‘neutral’ VIDE or VFIDE is also used for equations like

$$\displaystyle \begin{aligned} \frac{d}{dt} \Big (u(t)-\int _{\theta (t)}^{t} (t-s)^{\alpha -1}K(t,s)u(s)ds \Big ) = a(t)u(t) + f(t), \;\, t \in I, \end{aligned} $$

(47)

with, respectively, θ(t) ≡ 0 and θ(t) = t − τ(t). We have encountered a closely related system of such neutral VFIDEs in Example 4. That system of VFIDEs is also closely related to a system of integral-algebraic equations (cf. following section). The numerical analysis and computational solution of VFIDEs (6) was studied by, e.g., Brunner and Vermiglio [22] (θ(t) ≡ 0 and α = 1) and, for 0 < α < 1), by Ito and Turi [46] (using a semigroup framework) and by Brunner [18]. (The latter two papers also contain numerous additional references.)

3.3 Volterra Integro-Differential-Algebraic Equations

The system

$$\displaystyle \begin{aligned} A(t)u'(t) + B(t)u(t) = f(t) + (\mathcal{V}_{\alpha }u)(t), \;\, t \in I = [0,T], \end{aligned} $$

(48)

with

$$\displaystyle \begin{aligned} (\mathcal{V}_{\alpha }u)(t) := \int _{0}^{t}(t-s)^{\alpha -1}K(t,s)u(s)\,ds \;\, (0 < \alpha \leq 1), \end{aligned}$$

and $A(\cdot ),\,B(\cdot ),\,K(\cdot ,\cdot ) \in {\mathbb {R}}^{d\times d} \; (d \geq 2)$ and 0 < α ≤ 1, is called a system of Volterra integro-differential-algebraic equations (IDAEs). It may be viewed as a nonlocal extension of the system of differential-algebraic equations (DAEs)

$$\displaystyle \begin{aligned} A(t)u'(t) + B(t)u(t) = f(t), \;\, t \in I. \end{aligned} $$

(49)

The numerical analysis of systems of DAEs is now well understood (see for example Lamour et al. [50] and its references), and this is to a somewhat lesser extent also true for systems of integral-algebraic equations (IAEs) (that is, (7) with A(t) ≡ 0; cf. Liang and Brunner [54, 55]). The extension of the optimal convergence results for collocation methods from IAEs (which used an adaptation of the projection techniques of [50]) to systems of IDAEs is currently being studied by Liang and Brunner [56]. Owing to the non-local character of IAEs and IDAEs, the analysis becomes much more complex than the one for DAEs because it not only requires an appropriate understanding of the (tractability) index of the IDAE system but has also to take into account the degree of ill-posedness of the inherent system of first-kind Volterra integral equations. However, the analysis of collocation methods for IAEs and IDAEs with weakly singular kernels remains open.

3.4 Time-Fractional Evolution Equations

An equation of the form

$$\displaystyle \begin{aligned} \big ({}^CD_t^{\alpha }u \big )(t) = a(t)u(t) + f(t), \;\, t \in I, \end{aligned} $$

(50)

is a basic example of a (time-)fractional VIDE. For 0 < α < 1,

$$\displaystyle \begin{aligned} \big ({}^CD_t^{\alpha }u \big )(t) := \frac{1}{\varGamma (1-\alpha )}\int _{0}^{t}\frac{(t-s)^{1-\alpha -1}}{ \varGamma (1-\alpha )}\frac{du(s)}{ds}\,ds \end{aligned}$$

is the Caputo fractional derivative of order α of u(t). It is related to the Riemann-Liouville fractional derivative,

$$\displaystyle \begin{aligned} \big ({}^{RL}D_t^{\alpha }u \big )(t) := \frac{1}{\varGamma (1-\alpha )}\frac{d}{dt} \int _{0}^{t}(t-s)^{-\alpha }u(s)\,ds, \end{aligned}$$

via

$$\displaystyle \begin{aligned} \big ({}^{RL}D_t^{\alpha }u \big )(t) = \frac{t^{-\alpha }}{\varGamma (1-\alpha )}u(0) + \big ({}^CD_t^{\alpha }u \big )(t). \end{aligned}$$

Using the inverse (fractional time-integration) operator corresponding to $^CD_t^{\alpha }$ the fractional VIDE (9) can be written as an equivalent first-order VIDE or a VIE with weakly singular kernel (see for example Ma and Huang [63] where this is used as the basis for a numerical scheme). Although the numerical treatment of time-fractional VIDEs (and more general time-fraction evolution equations) has by now become a substantial ‘industry’, many issues are still waiting to be addressed. These include a detailed (analytical and numerical) comparison of computational schemes for fractional diffusion equations based on either the Caputo or the Riemann-Liouville fractional derivative (and the relationship between the respective schemes), as well as a thorough analysis of the merits of solving (9) directly, rather than its corresponding VIDE or VIE version.

Owing to limitation of space, and the sheer mass of recent papers on fractional diffusion equations, we will have to restrict this section to pointing the reader to a selection recent contributions relevant to the topics treated in the present paper. The 2010 monograph by Mainardi [64] contains, in addition to an introduction to fractional calculus, numerous applications of fractional diffusion-wave equations. The regularity of solutions to fractional diffusion is analyzed in McLean [69] (see also Clément and Londen [36] and its references). Various aspects (including a maximum principle) of discretizing such problems are treated in Mustapha and McLean [73], Brunner et al. [27], Mustapha and McLean [74], Ling and Yamamoto [57], Mustapha and Schötzau [75], Mustapha et al. [77], McLean and Mustapha [70], and Brunner et al. [28, 29]. Most of these papers contain extensive references.

4 Computational Challenges and Open Problems

4.1 Semilinear VIDEs with Blow-Up Solutions

For certain functions a, f, smooth or weakly singular kernels k, and (smooth) G the solution of the semilinear VIDE

$$\displaystyle \begin{aligned} u'(t) = a(t)u(t) + f(t) + \int _{0}^{t}k(t-s)G(u(s))\,ds, \;\, t \geq 0 \end{aligned} $$

(51)

(with a(t) ≤ 0) may blow up in finite time. For VIDEs (1) whose solution behaves monotonically the blow-up analysis of nonlinear VIEs developed in Brunner and Yang [23] can be used to derive necessary and sufficient conditions for finite-time blow-up. (Sufficient conditions for very special case of (1) were derived in Ma [61].) However, the blow-up theory for general VIDEs (1) whose solutions do (typically) not exhibit a monotone behavior remains to be established.

The finite-time blow-up of solutions of semilinear parabolic VIDEs

$$\displaystyle \begin{aligned} u_t - \varDelta u = f + \int _{0}^{t}k(t-s)G(u(s,\cdot ))\,ds, \;\, x \in \varOmega \subset {\mathbb{R}}^d, \; t \geq 0, \end{aligned} $$

(52)

with typical nonlinearities G(u) = (u + λ)^p (p > 1, λ > 0) or G(u) = e^βu (β > 0 was studied by Bellout [10] (see also Souplet [90]), under the assumption that Ω is bounded and has a smooth boundary ∂Ω. Blow-up results for different classes of semilinear parabolic VIDEs, including VIDEs of the form

$$\displaystyle \begin{aligned} u_t - \varDelta u = \mu \int _{0}^{t}u^p(s,\cdot )\,ds - au^q \;\, (p,\,q \geq 1), \end{aligned} $$

(53)

where μ is Hölder continuous, with μ ≥ 0 (μ≢0), and a > 0, and analogous partial VIDEs of Fredholm type, can be found in Souplet [89] and in Chapter V of Quittner and Souplet [83]. The blow-up of solutions for IDEs whose right-hand sides contain the composition of temporal and spatial integrals are also studied. The analysis is again based on the assumption that the spatial domain Ω possesses a smooth boundary. It appears that the blow-up theory for (2) and (3) with d = 2 and rectangular Ω remains to be established (in contrast to semilinear parabolic PDEs; cf. Bandle and Brunner [5] and its references).

The computational solution of parabolic VIDEs (2) on unbounded spatial domains Ω was studied in, e.g., Han et al. [44] and Brunner et al. [30] (see also for additional references). It is based on the choice of an appropriate bounded computational domain $\bar {\varOmega }$ and the construction of corresponding artificial boundary conditions for $\bar {\varOmega }$. (Compare also the monograph by Han and Wu [43] on the underlying theory of artificial boundary conditions for various classes of PDEs.)

On the other hand, the numerical analysis of parabolic VIDEs with finite-time blow-up, in particular the derivation of a posteriori error bounds for the numerical blow-up time, remains open.

4.2 Semilinear FIDEs with Blow-Up Solutions

As we have seen in Sect. 1.2, semilinear Fredholm integro-differential equations with nonlocal reaction term,

$$\displaystyle \begin{aligned} u_t - \varDelta u = f + \int _{\varOmega } H(u(\cdot ,y))\,dy, \;\, t > 0, \; x \in \varOmega \in {\mathbb{R}}^d, \end{aligned} $$

(54)

where Ω is bounded with smooth boundary, occur in chemical reaction-diffusion processes. It was shown in Chadam et al. [35] and Chadam and Yin [34] that for typical nonlinearities like H(u) = e^u the solution of (4) may blow up in finite time. While the theory of such FIDEs is well understood, this is not true of the numerical analysis and the efficient computational solution of these problems. The key difference between the spatial semidiscretization of the parabolic VIDE (2) and the parabolic FIDE (4) is that the approximation of the spatial integral in (4) leads to a large, dense system of semilinear FIDEs. It would be of interest to see if a discretization scheme similar to the one described at the end of Section 2.4 [67] can be used in the efficient computational solution of (4).