Generalized convolution quadrature for non smooth sectorial problems

Given a function f, we consider the approximation of linear Volterra convolutions in the abstract formwhere the convolution kernel k is allowed to be vector-valued, on an arbitrary time meshWe also consider the resolution of convolution equations like (1), where the data is c and the goal is to approximate f. The efficient discretization of (1) and, more generally, equations involving memory terms like (1), has been an active field of research for decades due to the many applications involved. Indeed the kernel can be scalar valued, such as \(k(t)=t^{\gamma }\) with \(\gamma >-1\), as it is the case for the fractional integral [6, 16], transparent boundary conditions [1, 27], impedance boundary conditions [13], etc., can be a matrix or even an operator, such as \(k(t)=\textrm{e}^{At}\), meaning the semigroup generated by the operator A, as it appears in the variation of constants formula for abstract initial value problems [17], see also [9] for other operator-valued kernels, or can even be a distribution, like the Dirac delta, in the boundary integral formulation of wave problems [8, Chapter 2].

Lubich’s convolution quadrature (CQ) [23] is nowadays a very well established family of numerical methods for the approximation of these problems, but its construction and analysis is strongly limited to uniform time meshes, where \(t_n=nh\), with \(h=\frac{T}{N}\) fixed. CQ schemes never require the evaluation of the convolution kernel k, which, as mentioned above, is allowed to be weakly singular at the origin, be defined in a distributional sense [24] or even not known analytically. Instead, the Laplace transform K of k is used, the so called transfer operator, namelyfor a certain abscissa \(\sigma \in {\mathbb {R}}\). The application of the CQ requires a bound of the formfor some \(M>0\) and \(\mu \in {\mathbb {R}}\), with \(\mu >0\) typically holding in applications to hyperbolic time-domain integral equations [24]. In this rather general setting, the generalization of Lubich’s CQ to variable steps has been developed in [19‐21], presenting the so-called generalized convolution quadrature (gCQ), with a special focus on the resolution of hyperbolic time-domain integral equations. The available stability and convergence analysis of the gCQ requires, in general, strong regularity hypotheses on the data. In particular, for \(\mu = -\alpha \), with \(\alpha \in (0,1)\), convergence of the first order can be proven on a general mesh only if the data f is of class \(C^3([0,T],B)\) and satisfies \(f(0)=f'(0)=0\), [21, Theorem 16]. Notice that the result in [21] improves the first one proven in [19], where an a priori regularization step is required for problems satisfying Assumption 1, and the data is required to satisfy \(f\in C^4([0,T],B)\) with \(f^{(\ell )}(0)=0\), with \(0\le \ell \le 3\), see also [8, Theorem 2.32].

There are however important applications, such as the time integration of parabolic problems [26], the approximation of fractional integrals and derivatives [25] and the resolution of fractional diffusion problems [9], where K can be holomorphically extended to the complement of an acute sector around the negative real axis, and it satisfies a bound of the typefor some \(\varphi \in (0,\frac{\pi }{2})\), \(M = M(\varphi )>0\), and \(\alpha >0\). If K satisfies (5), then it is said to be a sectorial Laplace transform and we also say that k is a sectorial kernel. The current theory for the generalization of the CQ to variable steps is suboptimal for these problems, where the extra regularity of the kernel should allow to relax the smoothness requirements on the data f (or c, if we are solving the convolution equation). In the present paper we address the a priori analysis of the gCQ for this important class of problems. More precisely, as a first step in the development of this theory, we consider following class of convolution operators.

In what follows, we will omit subindexes in the norms when they are clear from the context. Important examples of kernels satisfying Assumption 1 appear often in the literature, such as: Under Assumption 1, the convolution kernel k can be expressed as the inverse Laplace transform of K by means of a real integral representation, see for instance [11, Theorem 10.7d], more precisely we can writewith G given byand bounded byFor the regularity of the data f, we assume thatNotice that g continuous in [0, T] is enough for (1) to be well defined under the assumptions on k. In this situation, the original CQ methods are well known to suffer an order reduction. Typically a CQ formula of maximal order p is able to achieve that order in the \(L^{\infty }\) norm only if the zero-extension of the data f to \(t<0\) is smooth enough, depending on \(\alpha \) and p. This question has been thoroughly analyzed in the literature, starting from the introduction of the CQ itself in [23]. More precisely, we follow the operational notation introduced by Lubich and set We consider the particular case \(f(t)=t^{\beta }{{\textbf{v}}}\), with a t-independent \({{\textbf{v}}}\in B\), cf. [9]. Then, for \(p=1\), the following error estimates follow from [23, Theorem 5.2, Corollary 3.2]The above estimates imply that the order of convergence close to the origin is actually \(\alpha +\beta \), and that the maximal order of convergence (which is one) is only achievable pointwise at times away from the origin and for \(\beta \ge 0\). Similar error estimates in time hold for the application of the CQ to linear subdiffusion equations [14], whose solutions are known to satisfy (9), see [9, Section 8]. For approximations of order higher than one, correction terms are needed in order to achieve the full maximal order at a given time point away from zero but, in any case, the convergence rate still deteriorates close to the singularity [9, 15].

The real integral representation in (7) of the convolution kernel is much simpler to deal with than the usual contour integral representation along a Hankel contour in the complex plane, which is used in the analysis of more general sectorial problems [26]. This allows us to derive rather clean error estimates for the gCQ method and still brings quite a lot of insight for the analysis of more general sectorial problems and also of higher order gCQ schemes, which we do not address in the present paper. On the other hand, the definition of the gCQ based on (7) is equivalent to the original one in [19] and thus all the important properties proven in [19] still hold, such as the preservation of the composition rule, see Remark 3. Being able to use (7) also brings important advantages from the implementation point of view. In particular, we refer to the fast and oblivious CQ algorithm for the fractional integral and associated fractional differential equations developed in [5]. In this paper, we generalize the algorithm in [5] to the gCQ method, and show how both the computational complexity and the memory can be drastically reduced even for variable step approximations of the convolution problems under study.

The real integral representation of the kernel \(t^{\alpha -1}/\Gamma (\alpha )\) has been recently used in [7] to derive a posteriori error formulas for both the L1 scheme and the gCQ of the first order. For the popular L1 method the maximal order of convergence is known to be \(2-\alpha \), higher than for the gCQ of the first order. In [7], the maximal order \(2-\alpha \) is shown to be achievable in the \(L^2\) norm by using appropriate graded meshes. A posteriori error formulas are also derived for the gCQ method of the first order, but their asymptotic analysis is not developed. The authors point indeed to the complicated a priori error analysis which is required for this. In this paper we address precisely this a priori error analysis and derive error bounds in the \(L^{\infty }\) norm for the gCQ method of the first order. We obtain optimal error estimates of the maximal order for general meshes and, as a particular case, for appropriate graded meshes. By doing this, we fill an important gap in the theory in [21], for an important family of applications.

As we have already mentioned earlier, our analysis is conducted on an arbitrary time grid, but we consider in detail the particular choice of graded meshes, defined byFor (14) we derive the optimal value of the grading parameter \(\gamma \) as a function of \(\alpha \) and \(\beta \) in order to achieve full order of convergence.

The paper is organized as follows. In Sect. 2 we recall the definition of the generalized convolution quadrature method. In Sect. 3 we analyze this method for f satisfying (9) and for sectorial kernels satisfying (7)–(8). In Sect. 4 we address the application to linear subdiffusion equations. Sections 5 and 6 are devoted to implementation issues and numerical results are shown in Sect. 7.

We present the gCQ method for (1) under the assumptions (7)–(8) in a different way from the derivation in [19] and [21], which takes into account the specific properties of the convolution kernels under study. Indeed (7) allows to writewith y(x, t) the solution to the scalar ODE problemWith this representation of the convolution kernel, the gCQ approximation of (1) is defined below.

In applications it will be convenient to use the operational notation (23), which is defined bywith \(f_j=f(t_j)\), if f is a function. We will use the same notation for f being a vector, and in this case, \(f_j\) denotes its j-th component. The gCQ weights are given byNotice that \(r(x)=R(-x)\), with \(R(z)=\frac{1}{1-z}\) the stability function of the implicit Euler method.

We recall here the best convergence result available so far for the gCQ based on the implicit Euler method, which is a particular case of the class of Runge–Kutta based gCQ studied in [21].

In the next section we show how the regularity requirements for f can be significantly relaxed under assumptions (7)–(8). Furthermore, we will also be able to remove the exponentially growing term \(\textrm{e}^{{\tilde{c}}\sigma T}\) in the error estimate.

From (15) and (18) we can write the error at time \(t_n\) bywithAs it is usually done to analyze the error for ODE solvers, we notice that y(x, t) solves the recurrencewith \(d_n\) Euler’s remainder, this is,ThenFor the special case of \(f(t)= t^{\beta }{{\textbf{v}}}\), with \(\beta >-1\), and t-independent \( {{\textbf{v}}}\in B\), we can obtain explicit representations of (30). For this, we recall the definition of the Mittag–Leffler function, see for instance [10].

We also recall the definition of the Riemann–Liouville fractional derivative of order \(\mu >0\), which is given bywith \(\mu >0\), \(\rho -1\le \mu <\rho \), \(\rho \in {\mathbb {N}}\), and \({\mathcal {I}}^{\rho -\mu }\) the fractional integral of order \(\rho -\mu \), withif \(\nu >0\). For \(\mu < 0\) we take \(f^{(\mu )}={\mathcal {I}}^{-\mu }\). Notice thatwith the operational notation (23).

In the next result we collect a few identities and properties that will be needed in the proof of Theorem 14.

The main result is given below.

We will need the following generalization of the previous result to deal with remainder terms in power series expansions of the right hand side.

According to the definition of the fractional integral, Lemma 11 gives the fractional Taylor expansion of f(t) at \(t=0\) with remainder in integral form, cf. [22, (3.20)].

We state now the main result of the paper for f satisfying (9), generalizing the results in [22] to variable steps.

Notice that the above result improves significantly the regularity requirements of the result in [21]. Notice also that for a graded mesh (14), Proposition 8 shows how to choose the grading parameter \(\gamma \) in order to achieve convergence of order one, according to the regularity and the number of vanishing fractional moments at 0 of f. Detailed interpretations are presented in Corollary 15 and Corollary 16 below.

We consider the application of the gCQ method to fractional diffusion equations of the formwhere A is a symmetric, positive definite, elliptic operator, \(0<\alpha <1\), and \(D_t^\alpha \) denotes the Caputo fractional derivative of order \(\alpha \)Problem (49) is considered as an abstract initial value problem on a Banach space B, for instance \(B=L^p(\Omega )\), with \(\Omega \subset {\mathbb {R}}^d\) a domain, together with Dirichlet or Neumann boundary conditions. This is the analytical framework in [9] and corresponds to take \(D=B\) in Assumption 1. We notice that in [9] an expansion in fractional powers of the solution u is derived, of the same type as the one we consider in (47) for the data f, under suitable space-regularity conditions on \(u_0\) and f. The ambient space B can also be a finite dimensional vector space if the method of lines is a applied to (49) and a Galerkin method is used for the spatial discretization. In this case the resolvent estimates below follow in essentially the same way due to [3], with several applications so far in the literature, such as [28].

Notice that when \(u(0)=0\), the Caputo fractional derivative \(D_t^\alpha u(t)\), with \(0<\alpha <1\), is equivalent to Lubich’s operational notation \(\partial _t^\alpha u(t)\), andThe Laplace transform of the solution to (49) is given bywith F(z) the Laplace transform of the source f(t). By using the operational notation for convolutions in [23], see Remark 3, we can write the solution aswithandWe denote furtherwhich satisfies \((k*f)(t)=(K(\partial _t)f)(t)\).

Let us assume first that \(u_0\in D(A)\). Then, we can use the identityto writeCombining (50) with (54) yieldswhich is the solution ofWe use now the notationfor the gCQ discretization of \(H(\partial _t)f\), with H the Laplace transform of a convolution kernel h, on an arbitrary time grid \(\Delta := 0< t_1< \dots < t_N=T\). Then we apply the gCQ to discretize the fractional derivative, which corresponds to \(H(z) = z^{\alpha }\). Notice that this approximation is defined in [19], where more general convolutions are considered, not only those satisfying (7)–(8). In this way, we obtain for the smooth case \(u_0 \in D(A)\), the schemewith \(v_n\) denoting the approximation to \(v(t_n)\).

Since the gCQ preserves the composition rule of the continuous convolution, the approximations \(v_n \) defined in (57) are the same as the ones obtained from applying the gCQ in (55), this is, it holdsIt then follows that the approximation properties of the time discretization in (57) depend on the behavior of K(z) and the regularity of \(f-Au_0\). In the next Theorem we show that if \(-A\) is a sectorial operator and the sectorial angle \(\delta \) can be taken arbitrarily close to zero, then k in (53) satisfies (7)–(8). This is for instance the case if \(-A=\Delta \) is the Laplacian operator with Dirichlet or Neumann boundary conditions, with \(-A\) acting on a domain \(\Omega \subset {\mathbb {R}}^d\), and in the \(L^p(\Omega )\rightarrow L^p(\Omega )\) norm, for any \(1\le p \le \infty \), see for instance [12, 29]. This property is often preserved by standard spatial discretizations, such as finite differences [2] or the finite element method [3].

In this way, the results in Sect. 3 can be applied in order to choose an optimally graded time mesh for the approximation of v, depending on the regularity of the source term f.

In the non smooth case \(u_0 \notin D(A)\), we can approximate the solution (50) to (49) by applying the numerical inversion of sectorial Laplace transforms to approximate the term \(E(t)u_0\) and the gCQ method to deal with the convolution \(K(\partial _t) f\), for which Theorem 17 remains useful.

We follow the approach in [5] and start by addressing the implementation of the gCQ for the fractional integral \(\partial _t^{-\alpha }\). Notice that the associated convolution kernel in this case iswhich satisfies assumptions (7)–(8) withThis property of \(\partial _t^{-\alpha }\) has been used in [5] in order to develop a special quadrature for the original CQ weights, those corresponding to an approximation with uniform steps. We generalize here the ideas in [5] in order to obtain a fast and oblivious gCQ algorithm for the fractional integral.

First of all we split the gCQ approximation into a local and a history term likefor a fixed moderate value of \(n_0\), which can be also equal to 1, in principle. We now apply different methods to compute \(I_n^{his}\) and \( I_n^{loc}\).

For the local term \(I_n^{loc}\) we use the original derivation of the gCQ method in [19], and the expression (22) for the gCQ weights. This leads to the following complex-contour integral representationwhere \({\mathcal {C}}\) is a clockwise oriented, closed contour contained in , which encloses all poles of the integrand, namely \(\tau ^{-1}_j\), with \(j=1+(n-n_0)_+,\dots ,n\). We denotewhich satisfies the recursionand writeFor the approximation of (67) we set m the minimum pole of \(u^{loc}_{n}(z)\), M the maximum one, andThen we choose \({\mathcal {C}}\) as the circle \({\mathcal {C}}_M\) of radius M centered at \(M+m/10\). The parametrization of \({\mathcal {C}}_M\) and the quadrature nodes and weights for approximating (67) are obtained in the following way: In any case, we approximateFor the history term we use the real integral representationwith r(x) defined in (21) and \(y_n\) defined in (19). To approximate the integral, we generalize the quadrature method from [5] to accommodate variable time grids, yielding corresponding nodes \(x_l\) and weights \(\varpi _l\). We denote the error tolerance of this new quadrature as \(\textrm{tol}\) and denote \(N^{his}_Q\) the total number of quadrature nodes, which depends on both the time grid and \(\textrm{tol}\). Then (72) is approximated bywith each \(y_{n-n_0}(x_l)\) satisfying the recursionIn this way the evaluation of \(I_n^{his}\) for \(1\le n\le N\) requires a number of operations proportional to N and storage proportional to \(N_Q^{his}\). We finally approximateIn our numerical experiments, we setfor the evaluation of \({\widetilde{I}}_n^{loc}\). In this way the total complexity of this algorithm is \(O(n_0N_Q^{loc}+\left( N-n_0\right) N_Q^{his})\), while the memory requirements grow like \(O(N_Q^{loc}+N_Q^{his})\). For the uniform step approximation of (31), this is, the original CQ, it is proven in [5] that \( N_Q^{his} =O(\log (N))\). The results reported in Tables 1, 2, 3 and 4 for the generalization of this algorithm to variable steps, indicate that also on graded meshes like (14) it is \(N_Q^{his} = O(\log N)\), which certainly is an very important feature of this method. A rigorous theoretical analysis of the required complexity and memory requirements of the generalized fast and oblivious algorithm is beyond the scope of the present paper.

Here we show how to adapt the algorithm described in the previous section to the efficient computation of \(v_n\) in (57). In order to apply the fast gCQ algorithm for the fractional derivative we observe that, by definition,Then, by the discrete composition rule, it also holdswhere \(\partial ^{\Delta }_{t}\) denotes the approximation of the first order derivative provided by the gCQ method, this is,Thus, we can write (57) likewith \( \omega _{n,j} \) the gCQ weights (21) for the fractional integral \( \partial _t^{\alpha -1}\), this is withSubsequently, we haveNoticing that from (22) we have \(\omega _{n,n} = K[\tau _n^{-1}] = \tau _n^{-\alpha +1}\), the scheme readsThe summation in the right hand side can be efficiently evaluated by applying a variation of the algorithm in Sect. 5. As then, we separate this term into a local and a history term, byAfter applying the corresponding quadratures, as described in Sect. 5, we now approximate the history term bywith the values of \(f_j\) in (74) replaced by \( \left[ \partial ^{\Delta }_{t} v \right] _{j}\). The approximation of the local term now reads, after quadrature,with \(u_{n-1}^{loc}\) as in (66), with \(f_{n-1}\) replaced by \( \left[ \partial ^{\Delta }_{t} v \right] _{n-1}\). The complexity and memory requirements are as explained in Sect. 5.

We test in this section the convergence results proven in Proposition 8 and Sect. 4, by applying the gCQ method to different examples. Since the main goal of this paper is to derive accurate error estimates for the gCQ, we set a rather high tolerance requirement for the quadratures described in the previous section. More precisely, we set \(\textrm{tol}=10^{-8}\) for the evaluation of \({\widetilde{I}}_n^{his}\), for all \(1\le n\le N\) and all values of N.