Springer Nature is making SARS-CoV-2 and COVID-19 research free. View research | View latest news | Sign up for updates

Multigrid Methods for Time-Fractional Evolution Equations: A Numerical Study

  • 609 Accesses


In this work, we develop an efficient iterative scheme for a class of nonlocal evolution models involving a Caputo fractional derivative of order \(\alpha (0,1)\) in time. The fully discrete scheme is obtained using the standard Galerkin method with conforming piecewise linear finite elements in space and corrected high-order BDF convolution quadrature in time. At each time step, instead of solving the linear algebraic system exactly, we employ a multigrid iteration with a Gauss–Seidel smoother to approximate the solution efficiently. Illustrative numerical results for nonsmooth problem data are presented to demonstrate the approach.


This work is concerned with efficient iterative solvers for subdiffusion. Let \(\Omega \subset {\mathbb {R}}^d\) (\(d=1,2,3\)) be a convex polyhedral domain with a boundary \(\partial \Omega \). The subdiffusion model for the function u(t) reads:

$$\begin{aligned} \left\{ \begin{array}{ll} {\partial _t^\alpha }u(t) + A u(t) = f(t), &{} \forall \, 0<t\le T,\\ u(0) =v &{} {\text {in}} \ \Omega , \end{array}\right. \end{aligned}$$

where \(T>0\) is the final time, \(f:(0,T)\rightarrow L^2(\Omega )\) is the source term, and \(v\in L^2(\Omega )\) is the initial data. The operator A denotes a general second-order elliptic operator of the form \(Au =-\nabla \cdot (a\nabla u)\), where the diffusion coefficient a is possibly also time dependent, with a zero Dirichlet boundary condition. The notation \({\partial _t^\alpha }u\), \(\alpha \in (0,1)\), denotes the Caputo fractional derivative in time of order \(\alpha \), and it is defined by [15]

$$\begin{aligned} {\partial _t^\alpha }u (t) = \frac{1}{\Gamma (1-\alpha )}\int _0^t(t-s)^{-\alpha }u'(s)\ \mathrm{d}s. \end{aligned}$$

The model (1) arises naturally in a number of important practical applications involving subdiffusion processes, in which the mean squares displacement grows only sublinear with the time. The list of successful applications includes the thermal diffusion in fractal domains, the electron transport in copier, the protein dynamics in membranes and the solute transport in column experiments, to name just a few. Due to its extraordinary modeling capability, a large number of numerical methods have been developed for (1). Existing time stepping schemes roughly can be divided into two groups: (i) the piecewise polynomial approximation, e.g., the L1 scheme [17, 22, 23] and L1–2 scheme [20], and (ii) the convolution quadrature [18], e.g., the backward Euler [9], and high-order backward differentiation formulas (BDFs) [11]. There also have been substantial progresses in their theoretical analysis, including nonsmooth problem data. We refer interested readers to the recent survey [10] for a concise overview on numerical methods for the model (1).

However, all existing error analyses have assumed that at each time step, the linear system is solved exactly. For large-scale problems, the exact linear solver can be very expensive, and efficient iterative solvers, e.g., the preconditioned conjugate gradient method [21], multigrid methods [7] and domain decomposition methods [25], represent interesting alternatives. Thus, it is very natural to explore the potential of iterative solvers for the model (1).

For standard parabolic problems, the idea of combining iterative solvers with time-stepping schemes has been long been explored [1, 2, 4, 5, 24], commonly known as the incomplete iterative scheme. It was first proposed and explored for smooth solutions in [2, 4]. Bramble et al. [1] proposed an incomplete iterative solver for a fully discrete scheme based on the standard Galerkin approximation in space and linear multistep backward difference in time, and derived various error estimates for the homogeneous problem with nonsmooth problem data. Due to the nonlocality of the model (1) and limited smoothing properties of the solution operators, the analysis techniques in these works do not apply to (1). In a recent piece of work [14], the authors presented a thorough analysis of an incomplete iterative scheme for the backward Euler convolution quadrature for nonsmooth solutions and presented very encouraging numerical results for nonsmooth problem data. However, the potential of the idea for high-order time stepping schemes and their analysis remains to be investigated.

The goal of this work is to present an experimental study on incomplete iteration for several time stepping schemes based on the high-order BDF convolution quadrature, with proper initial correction at the first few steps, as developed in [11]. Our extensive numerical experiments indicate that the iterative scheme can maintain the overall high accuracy while greatly reduce the computational expense for both smooth and nonsmooth problem data, so long as the number of iterations at each time level is chosen properly. Specifically, for smooth solutions, a fixed number of multigrid iterations at all time levels suffices the desired accuracy, whereas for nonsmooth solutions, a larger number of iterations are needed at initial steps, due to the common weakly singular initial layers for the solutions to the model (1) with nonsmooth problem data. This observation is analogous to the standard parabolic case [1] and backward Euler convolution quadrature for the model (1) [14]. Iterative solvers have been employed in a number of numerical studies of the subdiffusion model (1) and found some empirical success (see, e.g., [6, 16] for multigrid methods). However, the error analysis of such iterative schemes is still largely missing, and the numerical experiments focused mostly on smooth solutions, which, however, hold only under restrictive conditions on the problem data [10]. Thus, this work complements existing studies.

The rest of the paper is organized as follows. In Sect. 2, we describe the fully discrete scheme and the iterative scheme and give an error analysis for smooth solutions. Extensive numerical experiments are presented in Sect. 3 to illustrate the performance of the scheme for both smooth and nonsmooth solutions, including the time-dependent diffusion coefficient.

The Iterative Scheme

Fully Discrete Scheme

First, we describe a fully discrete scheme for problem (1) based on the Galerkin FEM. Let \({\mathcal {T}}_h\) be a shape regular quasi-uniform triangulation of the domain \(\Omega \) into d-simplexes, denoted by T, with a mesh size h. Then, over the triangulation \({\mathcal {T}}_h\), we define a continuous piecewise linear finite element space \(X_h\) by

$$\begin{aligned} X_h= \left\{ v_h\in H_0^1(\Omega ):\ v_h|_T \text{ is } \text{ a } \text{ linear } \text{ function},\ \forall \, T \in {\mathcal {T}}_h\right\} . \end{aligned}$$

We define the \(L^2(\Omega )\) projection \(P_h:L^2(\Omega )\rightarrow X_h\) and Ritz projection \(R_h:H_0^1(\Omega )\rightarrow X_h\) by

$$\begin{aligned} (P_h \varphi ,\chi )= & {} (\varphi ,\chi ) , \quad \forall \, \chi \in X_h,\\ (a\nabla R_h\varphi ,\nabla \chi )= & {} (a\nabla \varphi ,\nabla \chi ), \quad \forall \, \chi \in X_h, \end{aligned}$$

respectively, where \((\cdot ,\cdot )\) denotes the \(L^2(\Omega )\) inner product.

Then, the semidiscrete Galerkin FEM for problem (1) reads: find \(u_h(t)\in X_h\) such that

$$\begin{aligned} ({\partial _t^\alpha }u_h,\chi ) + (\nabla u_h,\nabla \chi ) = (f,\chi ),\quad \forall \, \chi \in X_h,\quad t>0 \end{aligned}$$

with \(u_h(0)=v_h\in X_h\). Upon introducing the negative discrete Laplacian \(A_h:X_h\rightarrow X_h\), defined by \((A_h\varphi _h,\chi )=(a\nabla \varphi _h,\nabla \chi )\), for all \(\varphi _h, \chi \in X_h,\) we rewrite (2) as

$$\begin{aligned} {\partial _t^\alpha }u_h(t)+A_h u_h(t) = f_h(t) , \quad \forall \, t>0 \end{aligned}$$

with \(u_h(0)=v_h\in X_h\) and \(f_h(t)=P_hf(t)\). The following identity holds [24, (1.34), p. 11]:

$$\begin{aligned} A_hR_h = P_h A. \end{aligned}$$

Next, we partition the time interval [0, T] uniformly, with grid points \(t_n=n\tau \), \(n=0,\cdots ,N\), and the time step size \(\tau =T/N\). Recall the Riemann–Liouville fractional derivative \(^{\text{R}}\partial _t^\alpha \varphi (t)=\frac{\mathrm{d}}{\mathrm{d}t}\frac{1}{\Gamma (1-\alpha )}\int _0^t(t-s)^{-\alpha }\varphi (s)\mathrm{d} s\). The convolution quadrature generated by the backward differentiation formula of order k (BDFk), \(k=1,\cdots ,6\) [9] for approximating the Riemann–Liouville derivative \(^{\text{R}}\partial _t^\alpha \varphi (t_n)\) is given by (with \(\varphi ^j=\varphi (t_j)\))

$$\begin{aligned} {\bar{\partial }}_\tau ^\alpha \varphi ^n = \tau ^{-\alpha } \sum _{j=0}^nb_j^{(\alpha )}\varphi ^{n-j} \quad {\text {with}} \ \delta (\xi )^\alpha =\sum _{j=0}^\infty b_j^{(\alpha )}\xi ^j, \end{aligned}$$

where \(\delta (\xi )\) is the characteristic polynomial of the method. BDFk has been extensively used due to their good accuracy and easy implementation. The corresponding characteristic polynomial \(\delta (\xi )\) is given by

$$\begin{aligned} \delta (\xi ) = \sum _{j=1}^k \frac{1}{j}(1-\xi )^j. \end{aligned}$$

For \(\alpha =1\), BDFk is known to be \(A(\vartheta _k)\)-stable with angle \(\vartheta _k= 90^\circ \), \(90^\circ \), \(86.03^\circ \), \(73.35^\circ \), \(51.84^\circ \), \(17.84^\circ \) for \(k = 1,2,3,4,5,6\), respectively [8, pp. 251].

Since \(\partial _t^\alpha \varphi = {^{\text{R}}{\partial _t^\alpha }}(\varphi (t)-\varphi (0))\) [15, p. 91], the fully discrete scheme for problem (1) reads: given \(U_h^0=v_h\in X_h\), find \(U_h^n\in X_h\) such that

$$\begin{aligned} {\bar{\partial }}_\tau ^\alpha (U_h^n-U_h^0)+A_hU_h^n=f_h^n,\quad n=1,2,\cdots ,N \end{aligned}$$

with \(f_h^n=P_hf(t_n)\). However, a straightforward implementation can lead only to \(O(\tau )\) convergence in general, unless restrictive compatibility conditions on the problem data are fulfilled. To recover the desired high-order convergence, a number of techniques have been proposed. In this work, we focus on the initial correction. The idea of the initial correction was first proposed in [19] and then extended in [3, 9, 11, 26, 27]. The following scheme was developed in [11]:

$$\begin{aligned} \left\{ \begin{array}{l} {\bar{\partial }}_\tau ^\alpha (U_h^n-U_h^0) +A_h U_h^n = a_n^{(k)} (-A_h v+f_h^0)+f_h^n+ \sum \limits _{\ell =1}^{k-2} b_{\ell ,n}^{(k)}\tau ^{\ell } \partial _t^{(\ell )}f_h^0, \\ \quad 1\le n\le k-1,\\ {\bar{\partial }}_\tau ^\alpha (U_h^n-U_h^0) + A_h U_h^n = f_h^n , k\le n\le N, \end{array}\right. \end{aligned}$$

where the coefficients \(a_n^{(k)}\) and \(b_{\ell ,n}^{(k)}\) are given in Table 1. When compared with the vanilla CQ scheme (5), the additional terms at the first \(k-1\) steps are constructed so as to improve the overall accuracy of the scheme to \(O(\tau ^k)\) (at any fixed \(t_n>0\)) for an initial data \(v\in D(A)=H_0^1(\Omega )\cap H^2(\Omega )\), the domain of the operator A, and a possibly incompatible right-hand side f [11]. The only difference between the corrected scheme (6) and the standard scheme (5) lies in the correction terms at the starting \(k-1\) steps for BDFk. Hence, the scheme (6) is easy to implement. The scheme (6) satisfies the following error estimates ([11, Theorem 2.4] and [10, Theorem 3.1]).

Theorem 2.1

Let\(f\in C^{k-1}([0,T];L^2(\Omega ))\)and\(\int _0^t(t-s)^{\alpha -1}\Vert \partial _s^{(k)}f(s)\Vert _{L^2(\Omega )}\mathrm{d}s<\infty \). Then, for the solution\(U_h^n\)to (6), the following error estimates hold for any\(t_n>0\)and\(0<h<1\).

  1. (i)

    If\( A v\in L^2(\Omega )\), then by choosing\(U_h^0 = R_h v\), there holds

    $$\begin{aligned} \Vert U_h-u(t_n)\Vert _{L^2(\Omega )}\le \,& {} c\tau ^k \bigg (t_n^{ \alpha -k } \Vert f(0)-A v\Vert _{L^2(\Omega )} + \sum _{\ell =1}^{k-1} t_n^{ \alpha +\ell -k } \Vert \partial _t^{(\ell )}f(0)\Vert _{L^2(\Omega )}\\&+\int _0^{t_n}(t_n-s)^{\alpha -1}\Vert \partial _s^{(k)}f(s)\Vert _{L^2(\Omega )}\mathrm{d}s\bigg )\\&+ c h^2 \left (\Vert A v \Vert _{L^2(\Omega )} + |\log h|^2 \Vert f \Vert _{L^\infty (0,T;L^2(\Omega ))}\right ), \end{aligned}$$
  2. (ii)

    If\(v\in L^2(\Omega )\), then by choosing\(U_h^0 = P_h v\), there holds

    $$\begin{aligned} \Vert U_h-u(t_n)\Vert _{L^2(\Omega )}&\le c\tau ^k \bigg ( t_n^{-k} \Vert v\Vert _{L^2(\Omega )} + \sum _{\ell =0}^{k-1} t_n^{ \alpha +\ell -k } \Vert \partial _t^{(\ell )}f(0)\Vert _{L^2(\Omega )} \\&\quad +\int _0^{t_n}(t_n-s)^{\alpha -1}\Vert \partial _s^{(k)}f(s)\Vert _{L^2(\Omega )}\mathrm{d}s\bigg )\\&\quad + c h^2 |\log h| \left (t_n^{-\alpha }\Vert v \Vert _{L^2(\Omega )} + |\log h| \Vert f \Vert _{L^\infty (0,T;L^2(\Omega ))}\right ). \end{aligned}$$
Table 1 The coefficients \(a_j^{(k)}\) and \(b_{\ell ,j}^{(k)}\) [11, Tables 1 and 2]

Iterative Scheme

At each time level of the scheme (6), it requires solving a linear system exactly in order for the error estimates in Theorem 2.1 to hold. This can be very expensive for large-scale problems. Hence, it is of much interest to develop efficient algorithms that solve (7) inexactly while maintaining the overall accuracy given in Theorem 2.1. In this work, we propose an efficient multigrid solver, to approximately solve the resulting linear systems. Given \(U_h^0\), \(U_h^1,\cdots ,U_h^{n-1}\), we use an iterative process to approximate the solution \({{\bar{U}}}_h^n\) of

$$\begin{aligned} ( I+ \tau ^\alpha A_h){\bar{U}}_h^n = \tau ^\alpha f_h^n - \sum _{j=1}^{n}b_j^{(\alpha )}U_h^{n-j} + \sum _{j=0}^{n}b_j^{(\alpha )} U_h^{0} , \end{aligned}$$

and the iteration at the nth time level uses a starting guess \(U_h^{n,0}\). The iteration can be carried out by, e.g., Krylov subspace methods and V-cycle multigrid method with the standard Gauss–Seidel smoother. Below, we use a simple extrapolation:

$$\begin{aligned} U_h^{n,0}= \sum _{j=1}^{k+1} (-1)^{j+1} \begin{pmatrix} k+1\\ j \end{pmatrix} U_h^{n-j} ,\quad n\ge k+1, \end{aligned}$$

where \(\begin{pmatrix}k+1 \\ j\end{pmatrix}\) denotes the standard binomial coefficients. It is straightforward to verify that the accuracy of the extrapolated approximation \(U_h^{n,0}\) is \(O(\tau ^{k+1})\) for sufficiently smooth solutions [1]. This approximation is sufficient to preserve the overall accuracy for smooth solutions; see Theorem 2.3 below. At each time level, the iterative method generates a sequence of iterates \(U_h^{n,m}\) converging to the exact solution \({\bar{U}}_h^n\) of the linear system as \(m\rightarrow \infty \). Then, the incomplete iteration algorithm is then defined by setting

$$\begin{aligned} U_h^n = U_h^{n,M_n} \end{aligned}$$

for some integer \(M_n\) which may vary with the time level n and is to be specified. The linear systems at the first k steps are solved exactly.

The convergence of the iteration requires a certain contraction condition. Specifically, we define a weighted (energy like) norm \(|\cdot |\) on the space \(X_h\) defined by

$$\begin{aligned} |\psi |= \Vert (I + \tau ^\alpha A_h)^\frac{1}{2} \psi \Vert _{L^2(\Omega )}\quad \text {for}~~\psi \in X_h, \end{aligned}$$

and denote the space by X. Below, we assume that there exist some \(\kappa \in (0,1)\) and \(c_0>0\) such that

$$\begin{aligned} |U_h^{n,m}-{\bar{U}}_h^n| \le c_0 \kappa ^m |U_h^{n,0}-{\bar{U}}_h^n| \quad \text {for} \ m\ge 1. \end{aligned}$$

The contraction property in the weighted norm \(|\cdot |\) arises naturally in the study of iterative solvers, e.g., Krylov subspace methods [21], multigrid methods [7] and domain decomposition methods [25]. The constant \(\kappa \) is related to the condition number of preconditioned linear systems. The error analysis of the scheme for general problem data is challenging, and it is beyond the scope of the present work. In the general case, the main complication arises from the limited smoothing property of problem (1) and, thus, the known techniques from [1] do not apply any more. The case of the backward Euler convolution quadrature, i.e., \(k=1\), was analyzed in [14]. In the work, it was shown that when the number of iterations is chosen properly at each time level, the incomplete iterative scheme can maintain the overall accuracy up to a logarithmic factor for both smooth and nonsmooth solutions.

Error Analysis for Smooth Solutions

We conclude this section with the error analysis for smooth solutions. The argument is nearly identical with that developed in [14, Theorems 3.1 and 3.2] for the backward Euler convolution quadrature, and is provided only for completeness. The analysis below relies on the following the maximal \(\ell ^p\) regularity. For any \(1\le p<\infty \), the norm \(\Vert \cdot \Vert _{\ell ^p(X)}\) of a sequence \((v_j)_{j=1}^n\subset X\) is defined by \(\Vert (v_j)_{j=1}^n\Vert _{\ell ^p(X)} = \big (\tau \sum \limits _{j=1}^n\Vert v_j\Vert _{X}^p\big )^{1/p}\).

Lemma 2.1

Let\(U_h^n\)be the solution of (5) with\(v_h=0\). Then, for any\(1<p<\infty \),

$$\begin{aligned} \Vert ({\bar{\partial }}_\tau ^\alpha U_h^j)_{j=1}^n\Vert _{\ell ^p(L^2(\Omega ))} + \Vert (A_h U_h^j)_{j=1}^n\Vert _{\ell ^p(L^2(\Omega ))} \le c\Vert (f_h^j)_{j=1}^n\Vert _{\ell ^p(L^2(\Omega ))}. \end{aligned}$$


The cases \(k=1,2,\) were discussed in [12, Theorems 5 and 6]. The proof of the remaining cases \(k=3,\cdots ,6\) is similarly, and hence it is omitted.

The next result gives the error estimates for the scheme (6) with exact linear solve at each time step.

Theorem 2.2

Letube the solution to problem (1), and\(U_h^n\)be the solution of the scheme (6) with\(v_h= R_h v\). If\(u\in C^{k+1}([0,T];H_0^1(\Omega ))\cap C([0,T];H_0^1(\Omega )\cap H^2(\Omega ))\)and\(u^{(m)}(0)=0\)with\(m=1,2,\cdots ,k\), then

$$\begin{aligned} \Vert U_h^n- u(t_n) \Vert _{L^2(\Omega )} \le c(u) (h^2 + \tau ^k). \end{aligned}$$


In a customary way, we split the error \(e^n\equiv U_h^n-u(t_n)\) into

$$\begin{aligned} e^n = (U_h^n-R_h u(t_n)) + (R_h u(t_n)-u(t_n)) =: \vartheta ^n + \varrho ^n. \end{aligned}$$

It suffices to bound the terms \(\varrho ^n\) and \(\vartheta ^n\). Clearly,

$$\begin{aligned} \Vert \varrho ^n \Vert _{L^2(\Omega )} \le ch^2\Vert u\Vert _{C([0,T];H^2(\Omega ))}. \end{aligned}$$

It remains to bound \(\vartheta ^n\). Note that \(\vartheta ^n\) satisfies \(\vartheta ^0=0\) and

$$\begin{aligned} {\bar{\partial }}_\tau ^\alpha \vartheta ^n + A_h \vartheta ^n&= ({\bar{\partial }}_\tau ^\alpha (U_h^n-v_h)+A_hU_h^n) - ({\bar{\partial }}_\tau ^\alpha R_h(u(t_n)-v_h) + A_hR_hu(t_n)). \end{aligned}$$

It follows from the identity (4) and Eqs. (6) and (1) that

$$\begin{aligned} {\bar{\partial }}_\tau ^\alpha \vartheta ^n + A_h \vartheta ^n&= - {\bar{\partial }}_\tau ^\alpha R_h(u(t_n)-v_h) + P_h\partial _t^\alpha u(t_n)\\&= ( P_h - R_h ) {\partial _t^\alpha }u(t_n) - R_h ({\bar{\partial }}_\tau ^\alpha - {\partial _t^\alpha })(u(t_n)-v). \end{aligned}$$

Since the solution u is smooth, by the approximation properties of \(R_h\) and \(P_h\), we have

$$\begin{aligned} \Vert (P_h-R_h){\partial _t^\alpha }u(t_n)\Vert _{L^2(\Omega )}\le c h^2\Vert u\Vert _{C^1([0,T];H_0^1(\Omega )\cap H^2(\Omega ))}, \end{aligned}$$

and by the approximation property of \({\bar{\partial }}_\tau ^\alpha \) to \(^{\text{R}}\partial _t^\alpha \)

$$\begin{aligned} \Vert R_h ({\bar{\partial }}_\tau ^\alpha - {\partial _t^\alpha })(u(t_n)-v)\Vert _{L^2(\Omega )}\le \,& {} \Vert ({\bar{\partial }}_\tau ^\alpha - {\partial _t^\alpha })(u(t_n)-v)\Vert _{H_0^1(\Omega )} \nonumber \\\le \,& {} c \tau ^{k}\Vert u\Vert _{C^{k+1}([0,T];H_0^1(\Omega ))}. \end{aligned}$$

Now since \(\vartheta ^0=0\), the desired estimate follows from the discrete maximal \(\ell ^p\) regularity in Lemma 2.1 and the triangle inequality.

The next result gives the error estimate for the iterative scheme (9).

Theorem 2.3

Letuand\(U^n\equiv U_h^{n,m}\)be the solutions of problem (1) and the scheme (9) with\(U_h^{n,0}\)given by (8) and\(v_h = R_h v\), respectively, and let\(U_h^n= {\bar{U}}_h^n\)for\(n=1,2,\cdots ,k\). If\(u\in C^{k+1}([0,T];\,H_0^1(\Omega ))\cap C([0,T];\,H_0^1(\Omega )\cap H^2(\Omega ))\)and\(u^{(m)}(0)=0\)with\(m=1,2,\cdots , k\). Then, there exists a\(\delta >0\)such that

$$\begin{aligned} \Vert U_h^{n}- u(t_n) \Vert _{L^2(\Omega )} \le c(u) (h^2 + \tau ^k) \quad for \ c_0 \kappa ^m \le \delta . \end{aligned}$$


The proof of the theorem is similar to that for the backward Euler convolution quadrature (\(k=1\)) [14, Theorem 3.2]. Hence, we give a proof in Appendix A for completeness.

Remark 2.1

In Theorems 2.2 and 2.3, the solution u is assumed to be \(u\in C^{k+1}([0,T];\,H_0^1(\Omega ))\cap C([0,T];\,H_0^1(\Omega )\cap H^2(\Omega ))\) and \(u^{(m)}(0)=0\) with \(m=1,2,\cdots, k\). Under this condition, the iterative scheme (9) can maintain the overall \(O(\tau ^k)\) accuracy, as long as a sufficient but fixed number of iterations is taken at all time levels. However, this regularity assumption is restrictive and implicitly imposes strong compatibility condition on the problem data, i.e., the initial condition and source term. In the absence of these conditions, the uniform convergence order \(O(\tau ^k)\) is not expected [18].

Remark 2.2

For general problem data, or nonsmooth solutions, it is expected that error estimates similar to Theorem 2.1 hold, so long as the number \(M_n\) is taken appropriately. The number of iterations at the initial times should be larger to compensate for the singular behavior. However, a rigorous convergence analysis of this case is missing, although the numerical experiments below fully support the conjecture.

Numerical Experiments and Discussions

To illustrate the efficiency and robustness of the scheme (9), we present numerical results for problem (1) on the square \(\Omega =(-1,1)^2\). In the computation, we first divide the interval \((-1,1)\) into K equally spaced subintervals of length \(h=2/K\) so that the domain \(\Omega =(-1,1)^2\) is divided into \(K^2\) small squares, and then a uniform triangulation is obtained by connecting the diagonal of each small square. We divide [0, T] into a uniform grid with a step size \(\tau =T/N\). Since the semidiscrete solution \(u_h\) is not available in a closed form, we compute a reference solution \(u_h(t_n)\) by the corrected convolution quadrature generated by BDF4 in time with a finer mesh, i.e., \(N=1\,000\) and \(K=256\) in space. We compute the temporal error at \(t_N=T\) by

$$\begin{aligned} e^N = \frac{\Vert U_h^N - u_h(t_N) \Vert _{L^2(\Omega )}}{\Vert u_h(t_N) \Vert _{L^2(\Omega )}}. \end{aligned}$$

The scheme (9) employs the V-cycle multigrid method with the standard Gauss–Seidel smoother to inexactly solve the linear systems, which is known to satisfy the condition (11) [24, Theorem 11.4, p. 199]. Throughout, the mesh size h is fixed with \(K=256\) to focus on the temporal error. Below we present only numerical results for \(k=1,\cdots ,4\), since the convergence behavior of BDF5 and BDF6 is not very steady and the desired high-order convergence rate can only be observed at fairly small time step sizes [11].

Example 1: Smooth Solutions

We begin with an example with a smooth solution, by taking \(A =-\Delta \), \(u_0 = 0\) and \(f(x,t) = t^{4}(1-x^2)(1-y^2)\) in problem (1). One may show that the data are smooth enough and also satisfy the compatibility condition, i.e., \(f\in C^{\infty }([0,T];\,L^2 (\Omega ))\) and \(f^{(k)}(0) = 0\) with \(k=0,1,2,3\). This further implies the following regularity on the solution \(u \in C^4([0,T];\,L^2(\Omega )) \), and \(u^{(k)}(0)=0\) with \(k=0,\cdots ,4\) [10]. Thus, one may apply Theorem 2.3 and deduce that the iterative scheme achieves the optimal convergence rate with a uniform iteration number, denoted by M, at all time levels. This is fully supported by the numerical results in Table 2, where the numbers in the second row under each fractional order refer to the convergence rate as the time step size \(\tau \) halves, i.e., \(\log _2 (\frac{e^N(\tau )}{e^N(\tau /2)})\). A fairly steady convergence is observed for two different fractional orders and all BDFk schemes, \(k=1,\cdots ,4\), and an \(O(\tau ^k)\) rate for the BDFk scheme. These numerical results fully confirm the analysis in Theorem 2.3, showing the potential of the scheme (9) for smooth solutions. In passing, we note that the multigrid iteration with a Jacobi smoother works equally well for smooth solutions, but requires a larger number of iterations at each time level, and thus we do not present relevant results.

Table 2 \(L^2\) errors \(e^N\) for Example 1 with \(K=128\), \(M=3\), Gauss–Seidel smoother

Example 2: Nonsmooth Solutions

Next, we consider problem (1) with \(A=-\Delta \), \(T=1\), \(f=0\) and \(v(x,y)=\chi _{(0,1)\times (0,1)}(x,y).\) The initial data v are piecewise constant and hence \(v\in H^{\frac{1}{2}-\epsilon }(\Omega )\) for any small \(\epsilon >0\). Note that the exact solution u has a weak singularity at \(t=0\), and thus Theorem 2.3 does not apply any more. The number \(M_n\) of iterations in the scheme (9) is taken to be (with integers \(a,b\ge 0\))

$$\begin{aligned} M_n = a + b \log _2(t_n^{-1}), \quad n > k+1. \end{aligned}$$

Such a choice is inspired by the analysis in [1, 14]. Below, we consider two different choices of \(M_n\), i.e., \(b=0\) and \(b=5\), and the corresponding numerical results are presented in Tables 3 and 4. With \(b=0\), \(M_n\) is constant over all time intervals, whereas for \(b>0\), more iterations are taken for \(t_n\) close to zero. It is observed that with \(b=0\), the scheme (9) fails to maintain the predicted convergence rate in Theorem 2.1, and the convergence is unsteady. In contrast, by choosing \(b=5\), the desired \(O(\tau ^k)\) convergence rate is restored, as well as the steady convergence, for all fractional orders and BDFk. This shows the necessity of more iterations at starting steps, and the potential of the scheme (9) for nonsmooth solutions.

Table 3 \(L^2\) errors \(e^N\) for Example 2 with \(K=128\), \(a=3\) and \(b=0\), Gauss–Seidel smoother
Table 4 \(L^2\) errors \(e^N\) for Example 2 with \(K=128\), \(a=3\) and \(b=5\), Gauss–Seidel smoother

Example 3: Time-Dependent Diffusion Coefficient

Finally, we present numerical results for the case that the operator A involves a time-dependent diffusion coefficient, i.e., \(A(t) = -(2+\cos t)\Delta \). We test the nonsmooth initial data \(v(x,y)=\chi _{(0,1)\times (0,1)}(x,y)\) and the incompatible source data \(f(x,y,t)=e^t \chi _{(-1,0)\times (-1,0)}(x,y)\). Note that the design and analysis of high-order numerical schemes for time-dependent elliptic operators remain poorly understood [10, 13]. However, the iterative scheme (9) extends straightforwardly to the case of a time-dependent elliptic operator. In our implementation, we employ the following schemes analogous to (6):

$$\begin{aligned} \left\{ \begin{array}{l} {\bar{\partial }}_\tau ^\alpha (U_h^n-U_h^0) +A_h(t_n) U_h^n = a_n^{(k)} (-A_h(t_n) v+f_h^0)+f_h^n+ \sum \limits _{\ell =1}^{k-2} b_{\ell ,n}^{(k)}\tau ^{\ell } \partial _t^{(\ell )}f_h^0, \\ \quad 1\le n\le k-1,\\ {\bar{\partial }}_\tau ^\alpha (U_h^n-U_h^0) + A_h(t_n) U_h^n = f_h^n, \\ \quad k\le n\le N. \end{array}\right. \end{aligned}$$

This scheme is obtained by adapting (6) heuristically, and its full theoretical justification is missing. The numerical results for the example are presented in Tables 5 and 6, respectively, for the cases \(b=0\) and \(b=5\). The overall behavior is very similar to Example 2, and the same observations remain largely valid. In particular, the results show clearly the desired \(O(\tau ^k)\) convergence rate when the number of iterations is chosen suitably. Thus, the corrected scheme (15) can achieve a convergence rate of \(O(\tau ^k)\), and the corresponding iterative scheme (9) can maintain the overall accuracy.

Table 5 \(L^2\) errors \(e^N\) for Example 3 with \(K=128\), \(a=3\) and \(b=0\), Gauss–Seidel smoother
Table 6 \(L^2\) errors \(e^N\) for Example 3 with \(K=128\), \(a=3\) and \(b=5\), Gauss–Seidel smoother

These numerical experiments show clearly that iterative solvers can maintain the overall accuracy of time-stepping schemes for subdiffusion with both smooth and nonsmooth solutions (and time-dependent elliptic operators), provided that the number of iterations at each time level is chosen properly. One outstanding issue is the rigorous theoretical justifications of the efficiency of the schemes, in order to gain deep insight into the choice of important algorithmic parameters.


  1. 1.

    Bramble, J.H., Pasciak, J.E., Sammon, P.H., Thomée, V.: Incomplete iterations in multistep backward difference methods for parabolic problems with smooth and nonsmooth data. Math. Comput. 52(186), 339–367 (1989)

  2. 2.

    Bramble, J.H., Sammon, P.H.: Efficient higher order single step methods for parabolic problems. I. Math. Comput. 35(151), 655–677 (1980)

  3. 3.

    Cuesta, E., Lubich, C., Palencia, C.: Convolution quadrature time discretization of fractional diffusion-wave equations. Math. Comput. 75(254), 673–696 (2006)

  4. 4.

    Douglas Jr., J., Dupont, T., Ewing, R.E.: Incomplete iteration for time-stepping a Galerkin method for a quasilinear parabolic problem. SIAM J. Numer. Anal. 16(3), 503–522 (1979)

  5. 5.

    Du, Q., Ming, P.: Cascadic multigrid methods for parabolic problems. Sci. China Ser. A 51(8), 1415–1439 (2008)

  6. 6.

    Gaspar, F.J., Rodrigo, C.: Multigrid waveform relaxation for the time-fractional heat equation. SIAM J. Sci. Comput. 39(4), A1201–A1224 (2017)

  7. 7.

    Hackbusch, W.: Multigrid Methods and Applications. Springer, Berlin (1985)

  8. 8.

    Hairer, E., Wanner, G.: Solving Ordinary Differential Equations II, second edn. Springer, Berlin (1996). (stiff and differential-algebraic problems)

  9. 9.

    Jin, B., Lazarov, R., Zhou, Z.: Two fully discrete schemes for fractional diffusion and diffusion-wave equations with nonsmooth data. SIAM J. Sci. Comput. 38(1), A146–A170 (2016)

  10. 10.

    Jin, B., Lazarov, R., Zhou, Z.: Numerical methods for time-fractional evolution equations with nonsmooth data: a concise overview. Comput. Methods Appl. Mech. Eng. 346, 332–358 (2019)

  11. 11.

    Jin, B., Li, B., Zhou, Z.: Correction of high-order BDF convolution quadrature for fractional evolution equations. SIAM J. Sci. Comput. 39(6), A3129–A3152 (2017)

  12. 12.

    Jin, B., Li, B., Zhou, Z.: Discrete maximal regularity of time-stepping schemes for fractional evolution equations. Numer. Math. 138(1), 101–131 (2018)

  13. 13.

    Jin, B., Li, B., Zhou, Z.: Subdiffusion with a time-dependent coefficient: analysis and numerical solution. Math. Comput. 88(319), 2157–2186 (2019)

  14. 14.

    Jin, B., Zhou, Z.: Incomplete iterative solution of subdiffusion. Preprint. arXiv:1906.06497 (2019)

  15. 15.

    Kilbas, A.A., Srivastava, H.M., Trujillo, J.J.: Theory and Applications of Fractional Differential Equations. Elsevier Science B.V., Amsterdam (2006)

  16. 16.

    Lin, X.-L., Lu, X., Ng, M.K., Sun, H.-W.: A fast accurate approximation method with multigrid solver for two-dimensional fractional sub-diffusion equation. J. Comput. Phys. 323, 204–218 (2016)

  17. 17.

    Lin, Y., Xu, C.: Finite difference/spectral approximations for the time-fractional diffusion equation. J. Comput. Phys. 225(2), 1533–1552 (2007)

  18. 18.

    Lubich, C.: Discretized fractional calculus. SIAM J. Math. Anal. 17(3), 704–719 (1986)

  19. 19.

    Lubich, C., Sloan, I.H., Thomée, V.: Nonsmooth data error estimates for approximations of an evolution equation with a positive-type memory term. Math. Comput. 65(213), 1–17 (1996)

  20. 20.

    Lv, C., Xu, C.: Error analysis of a high order method for time-fractional diffusion equations. SIAM J. Sci. Comput. 38(5), A2699–A2724 (2016)

  21. 21.

    Saad, Y.: Iterative Methods for Sparse Linear Systems, second edn. SIAM, Philadelphia (2003)

  22. 22.

    Stynes, M., O’Riordan, E., Gracia, J.L.: Error analysis of a finite difference method on graded meshes for a time-fractional diffusion equation. SIAM J. Numer. Anal. 55(2), 1057–1079 (2017)

  23. 23.

    Sun, Z.-Z., Wu, X.: A fully discrete difference scheme for a diffusion-wave system. Appl. Numer. Math. 56(2), 193–209 (2006)

  24. 24.

    Thomée, V.: Galerkin Finite Element Methods for Parabolic Problems, second edn. Springer, Berlin (2006)

  25. 25.

    Toselli, A., Widlund, O.: Domain Decomposition Methods—Algorithms and Theory. Springer, Berlin (2005)

  26. 26.

    Xing, Y., Yan, Y.: A higher order numerical method for time fractional partial differential equations with nonsmooth data. J. Comput. Phys. 357, 305–323 (2018)

  27. 27.

    Yan, Y., Khan, M., Ford, N.J.: An analysis of the modified L1 scheme for time-fractional partial differential equations with nonsmooth data. SIAM J. Numer. Anal. 56(1), 210–227 (2018)

Download references

Author information

Correspondence to Zhi Zhou.

Appendix A: Proof of Theorem 2.3

Appendix A: Proof of Theorem 2.3


In a customary way, we split the error \(e^{n,m}=U_h^{n,m}-u(t_n)\) into

$$\begin{aligned} e^{n,m}= (U_h^{n,m}-R_h u(t_n)) + (R_h u(t_n)-u(t_n)) =: \vartheta ^n + \varrho ^n. \end{aligned}$$

In view of (12), it suffices to bound \(\vartheta ^n\). Note that \(\vartheta ^n\) satisfies \(\vartheta ^0=0\) and

$$\begin{aligned}&{\bar{\partial }}_\tau ^\alpha \vartheta ^n + A_h\vartheta ^n = ({\bar{\partial }}_\tau ^\alpha (U_h^{n,m}-v_h)+ A_hU_h^{n,m}) -{\bar{\partial }}_\tau ^\alpha (R_hu(t_n)-v_h) - A_hR_hu(t_n), \\&\quad n=1,\cdots ,N. \end{aligned}$$

Let the auxiliary function \({\bar{U}}_h^n\in X_h\) satisfy \({\bar{U}}_h^0 = R_hv\) and

$$\begin{aligned} \tau ^{-\alpha } \left( {\bar{U}}_h^n + \sum _{j=1}^n b_{n-j}^{(\alpha )} U_h^{j,m} - \sum _{j=0}^n b_{n-j}^{(\alpha )} U_h^0\right) + A_h \bar{U}_h^n = f_h^n,\quad n=1,2,\cdots ,N. \end{aligned}$$

This together with the identities (4), (1) and (9) implies

$$\begin{aligned} {\bar{\partial }}_\tau ^\alpha \vartheta ^n + A_h \vartheta ^n= \sigma ^n \quad {\text {with }} \ \sigma ^n = (I+\tau ^\alpha A_h) \eta ^n + \omega ^n, \end{aligned}$$

with the errors \(\eta ^n\) and \(\omega ^n\) given by

$$\begin{aligned} \eta ^n&=\tau ^{-\alpha } (U_h^{n,m} - {\bar{U}}_h^n) \quad \text {and} \nonumber \\ \omega ^n&= ( P_h - R_h ) {\partial _t^\alpha }(u(t_n)-v) - R_h ({\bar{\partial }}_\tau ^\alpha - {\partial _t^\alpha })(u(t_n)-v). \end{aligned}$$

By the discrete maximal \(\ell ^p\) regularity in Lemma 2.1 and the triangle inequality, for any \(q\in (\frac{2}{\alpha },\infty )\) and \(n=1,2,\cdots ,N\), we have

$$\begin{aligned} \Vert \vartheta ^n \Vert _{L^2(\Omega )}&\le c\Vert (A_h^{-\frac{1}{2}}\sigma ^j)_{j=1}^n\Vert _{\ell ^q(L^2(\Omega ))} \\&\le c\Vert ((I+\tau ^{\alpha } A_h)A_h^{-\frac{1}{2}}\eta ^{j})_{j=1}^n\Vert _{\ell ^q(L^2(\Omega ))} + c\Vert (A_h^{-\frac{1}{2}}\omega ^j)_{j=1}^n\Vert _{\ell ^q((\Omega ))}. \end{aligned}$$

Since u is sufficiently smooth, (13) and (14) imply

$$\begin{aligned} \Vert A_h^{-\frac{1}{2}}\omega ^j\Vert _{L^2(\Omega )}\le c\Vert \omega ^j\Vert _{L^2(\Omega )}\le c(u)(h^2+\tau ^k). \end{aligned}$$

Further, direct computation gives

$$\begin{aligned} \Vert (I+\tau ^\alpha A_h)A_h^{-\frac{1}{2}}\eta ^j\Vert _{L^2(\Omega )} \le c|\eta ^j|. \end{aligned}$$

The preceding three estimates imply (with \(|\cdot |_X=|\cdot |\))

$$\begin{aligned} \Vert \vartheta ^n \Vert _{L^2(\Omega )} \le c \Vert (\eta ^{j})_{j=1}^n\Vert _{\ell ^q(X)} + c(u) (h^2 + \tau ^k). \end{aligned}$$

Next, we find a bound of the summand \(|\eta ^j|\). Given a tolerance \(\delta >0\) to be determined, under assumption (11), there exists an \(m\in {\mathbb {N}}\) such that \(c_0 \kappa ^m \le \delta \) and by the triangle inequality

$$\begin{aligned} |U_h^{n,m} - {\bar{U}}_h^n| \le \delta |U_h^{n,0}-{\bar{U}}_h^n| \le \delta ( |U_h^{n,0} - U_h^{n,m}| + |U_h^{n,m} - {\bar{U}}_h^n | ). \end{aligned}$$

With \(\epsilon =\delta (1-\delta )^{-1}\), rearranging the inequality gives \(|U_h^{n,m} - {\bar{U}}_h^n| \le \epsilon |U_h^{n,0} - U_h^{n,m} |\). Hence,

$$\begin{aligned} |\eta ^n| = \tau ^{-\alpha } |U_h^{n,m} - {\bar{U}}_h^n| \le \epsilon \tau ^{-\alpha } |U_h^{n,0} - U_h^{n,m} |. \end{aligned}$$

Meanwhile, the choice of \(U_h^{n,0}\) in (8) and the triangle inequality imply

$$\begin{aligned} |U_h^{n,m} - U_h^{n,0}| \le \tau ^{k+1} |{\tilde{\partial }}_\tau ^{k+1} \theta ^{n}| + \tau ^{k+1}|{\tilde{\partial }}_\tau ^{k+1} R_h u(t_n)| , \end{aligned}$$

where \({\tilde{\partial }}_\tau ^{k+1}\) denotes the \((k+1)\)th backward difference approximation (of the backward Euler type). The last two estimates together with the inverse inequality (in time) imply

$$\begin{aligned} \Vert (\eta ^{j})_{j=1}^n\Vert _{\ell ^q(X)}&\le c\epsilon \tau ^{1-\alpha }\Vert ({\bar{\partial }}_\tau \theta ^j)_{j=1}^n\Vert _{\ell ^q(X)} + c\epsilon \tau ^{k+1-\alpha }\Vert u\Vert _{C^{k+1}([0,T];H_0^1(\Omega ))} \nonumber \\&\le c\epsilon \Vert ({\bar{\partial }}_\tau ^\alpha \theta ^j)_{j=1}^n\Vert _{\ell ^q(X)} + c\epsilon \tau ^{k+1-\alpha }\Vert u\Vert _{C^{k+1}([0,T];H_0^1(\Omega ))}. \end{aligned}$$

Let \(I_h=(I+\tau ^{\alpha } A_h)^{-\frac{1}{2}}\). Then, the identity

$$\begin{aligned} |{\bar{\partial }}_\tau ^\alpha \vartheta ^j|= \Vert (I+\tau ^{\alpha } A_h) {\bar{\partial }}_\tau ^\alpha I_h\vartheta ^j\Vert _{L^2(\Omega )} \end{aligned}$$

and the triangle inequality imply

$$\begin{aligned} \Vert ({\bar{\partial }}_\tau ^\alpha \vartheta ^j)_{j=1}^n\Vert _{\ell ^q(X)}&\le \Vert ( {\bar{\partial }}_\tau ^\alpha I_h\vartheta ^j)_{j=1}^n\Vert _{\ell ^q(L^2(\Omega ))} + \tau ^\alpha \Vert ({\bar{\partial }}_\tau ^\alpha A_hI_h\vartheta ^j)_{j=1}^n\Vert _{\ell ^q(L^2(\Omega ))} \\&:=\mathrm{I}+\mathrm{II} . \end{aligned}$$

By the discrete maximal \(\ell ^p\) regularity in Lemma 2.1, we have

$$\begin{aligned} \mathrm{I}&\le c\Vert (I_h\sigma ^j)_{j=1}^n\Vert _{\ell ^q(L^2(\Omega ))}, \end{aligned}$$

and similarly, the inverse inequality (in time) and discrete maximal \(\ell ^p\) regularity yield

$$\begin{aligned} \mathrm{II}&\le c\Vert (A_hI_h\vartheta ^j)_{j=1}^n\Vert _{\ell ^q(L^2(\Omega ))} \le c\Vert (I_h\sigma ^j)_{j=1}^n\Vert _{\ell ^q(L^2(\Omega ))}. \end{aligned}$$

Combining the preceding three estimates with (A1), and the errors (13) and (14) gives

$$\begin{aligned} \Vert ({{\bar{\partial}}_{\tau}^{\alpha} \vartheta^{j})}_{j=1}^{n}\Vert_{\ell ^q(X)} \le c(u) (\tau +h^2) + c\epsilon \Vert ({{\bar{\partial}}_{\tau}^{\alpha}\theta^{j})}_{j=1}^n\Vert _{\ell ^q(X)}. \end{aligned}$$

Now, it follows from (A5) and (A6) that

$$\begin{aligned} \Vert ({\bar{\partial }}_\tau ^\alpha \vartheta ^j)_{j=1}^n\Vert _{\ell ^q(X)} \le c(u) (\tau +h^2) + c\epsilon \Vert ({\bar{\partial }}_\tau ^\alpha \theta ^j)_{j=1}^n\Vert _{\ell ^q(X)}. \end{aligned}$$

Thus, by choosing a sufficiently small \(\epsilon \), we get

$$\begin{aligned} \Vert ({\bar{\partial }}_\tau ^\alpha \vartheta ^j)_{j=1}^n\Vert _{\ell ^q(X)} \le c(u) (\tau +h^2). \end{aligned}$$

This, (A4) and (A5) give \(\Vert \vartheta ^n \Vert _{L^2(\Omega )} \le c(u) (\tau +h^2)\), which completes the proof.

Rights and permissions

Reprints and Permissions

About this article

Verify currency and authenticity via CrossMark

Cite this article

Jin, B., Zhou, Z. Multigrid Methods for Time-Fractional Evolution Equations: A Numerical Study. Commun. Appl. Math. Comput. 2, 163–177 (2020). https://doi.org/10.1007/s42967-019-00042-9

Download citation


  • Subdiffusion
  • Convolution quadrature
  • Multigrid
  • Incomplete iterative scheme

Mathematics Subject Classification

  • 65M60
  • 65N15
  • 65F10
  • 35R11