Abstract
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.
Similar content being viewed by others
References
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)
Bramble, J.H., Sammon, P.H.: Efficient higher order single step methods for parabolic problems. I. Math. Comput. 35(151), 655–677 (1980)
Cuesta, E., Lubich, C., Palencia, C.: Convolution quadrature time discretization of fractional diffusion-wave equations. Math. Comput. 75(254), 673–696 (2006)
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)
Du, Q., Ming, P.: Cascadic multigrid methods for parabolic problems. Sci. China Ser. A 51(8), 1415–1439 (2008)
Gaspar, F.J., Rodrigo, C.: Multigrid waveform relaxation for the time-fractional heat equation. SIAM J. Sci. Comput. 39(4), A1201–A1224 (2017)
Hackbusch, W.: Multigrid Methods and Applications. Springer, Berlin (1985)
Hairer, E., Wanner, G.: Solving Ordinary Differential Equations II, second edn. Springer, Berlin (1996). (stiff and differential-algebraic problems)
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)
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)
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)
Jin, B., Li, B., Zhou, Z.: Discrete maximal regularity of time-stepping schemes for fractional evolution equations. Numer. Math. 138(1), 101–131 (2018)
Jin, B., Li, B., Zhou, Z.: Subdiffusion with a time-dependent coefficient: analysis and numerical solution. Math. Comput. 88(319), 2157–2186 (2019)
Jin, B., Zhou, Z.: Incomplete iterative solution of subdiffusion. Preprint. arXiv:1906.06497 (2019)
Kilbas, A.A., Srivastava, H.M., Trujillo, J.J.: Theory and Applications of Fractional Differential Equations. Elsevier Science B.V., Amsterdam (2006)
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)
Lin, Y., Xu, C.: Finite difference/spectral approximations for the time-fractional diffusion equation. J. Comput. Phys. 225(2), 1533–1552 (2007)
Lubich, C.: Discretized fractional calculus. SIAM J. Math. Anal. 17(3), 704–719 (1986)
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)
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)
Saad, Y.: Iterative Methods for Sparse Linear Systems, second edn. SIAM, Philadelphia (2003)
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)
Sun, Z.-Z., Wu, X.: A fully discrete difference scheme for a diffusion-wave system. Appl. Numer. Math. 56(2), 193–209 (2006)
Thomée, V.: Galerkin Finite Element Methods for Parabolic Problems, second edn. Springer, Berlin (2006)
Toselli, A., Widlund, O.: Domain Decomposition Methods—Algorithms and Theory. Springer, Berlin (2005)
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)
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)
Author information
Authors and Affiliations
Corresponding author
Appendix A: Proof of Theorem 2.3
Appendix A: Proof of Theorem 2.3
Proof
In a customary way, we split the error \(e^{n,m}=U_h^{n,m}-u(t_n)\) into
In view of (12), it suffices to bound \(\vartheta ^n\). Note that \(\vartheta ^n\) satisfies \(\vartheta ^0=0\) and
Let the auxiliary function \({\bar{U}}_h^n\in X_h\) satisfy \({\bar{U}}_h^0 = R_hv\) and
This together with the identities (4), (1) and (9) implies
with the errors \(\eta ^n\) and \(\omega ^n\) given by
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
Since u is sufficiently smooth, (13) and (14) imply
Further, direct computation gives
The preceding three estimates imply (with \(|\cdot |_X=|\cdot |\))
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
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,
Meanwhile, the choice of \(U_h^{n,0}\) in (8) and the triangle inequality imply
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
Let \(I_h=(I+\tau ^{\alpha } A_h)^{-\frac{1}{2}}\). Then, the identity
and the triangle inequality imply
By the discrete maximal \(\ell ^p\) regularity in Lemma 2.1, we have
and similarly, the inverse inequality (in time) and discrete maximal \(\ell ^p\) regularity yield
Combining the preceding three estimates with (A1), and the errors (13) and (14) gives
Now, it follows from (A5) and (A6) that
Thus, by choosing a sufficiently small \(\epsilon \), we get
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
About this article
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
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s42967-019-00042-9