Parallel-in-time multigrid for space-time finite element approximations of two-dimensional space-fractional diffusion equations. (English) Zbl 1443.65231
Summary: The paper investigates a non-intrusive parallel time integration with multigrid for space-fractional diffusion equations in two spatial dimensions, which is discretized by the space-time finite element method to propagate solutions. We develop a multigrid-reduction-in-time (MGRIT) algorithm with time-dependent time-grid propagators and provide its two-level convergence theory under the assumptions of the stability and simultaneous diagonalizability on time-grid propagators. Numerical results show that the proposed method possesses the saturation error order, theoretical results of the two-level variant deliver good predictions for our model problems, and significant speedups of the MGRIT can be achieved when compared to the two-level variant with F-relaxation (an equivalent version of the parareal algorithm) and the sequential time-stepping approach.
MSC:
| 65M60 | Finite element, Rayleigh-Ritz and Galerkin methods for initial value and initial-boundary value problems involving PDEs |
| 35R11 | Fractional partial differential equations |
Keywords:
space-fractional diffusion equations; space-time finite element; parallel-in-time; reduction-based multigrid; pararealSoftware:
MGRITReferences:
| [1] | Kilbas, A. A.; Srivastava, H. M.; Trujillo, J. J., Theory and Applications of Fractional Differential Equations (2006), Elsevier · Zbl 1092.45003 |
| [2] | Metzler, R.; Klafter, J., The random walk’s guide to anomalous diffusion: a fractional dynamics approach, Phys. Rep., 339, 1-77 (2000) · Zbl 0984.82032 |
| [3] | Wang, H.; Basu, T. S., A fast finite difference method for two-dimensional space-fractional diffusion equations, SIAM J. Sci. Comput., 34, A2444-A2458 (2012) · Zbl 1256.35194 |
| [4] | Ding, Z. Q.; Xiao, A. G.; Li, M., Weighted finite difference methods for a class of space fractional partial differential equations with variable coefficients, J. Comput. Appl. Math., 233, 1905-1914 (2010) · Zbl 1185.65146 |
| [5] | Cao, X. N.; Fu, J. L.; Huang, H., Numerical method for the time fractional Fokker-Planck equation, Adv. Appl. Math. Mech., 4, 848-863 (2012) · Zbl 1262.65087 |
| [6] | Gao, G. H.; Sun, Z. Z., A compact finite difference scheme for the fractional sub-diffusion equations, J. Comput. Phys., 230, 586-595 (2011) · Zbl 1211.65112 |
| [7] | Sousa, E., Numerical approximations for fractional diffusion equations via splines, Comput. Math. Appl., 62, 938-944 (2011) · Zbl 1228.65153 |
| [8] | Chen, M. H.; Deng, W. H., Fourth order accurate scheme for the space fractional diffusion equations, SIAM J. Numer. Anal., 52, 1418-1438 (2014) · Zbl 1318.65048 |
| [9] | Hao, Z. P.; Fan, K.; Cao, W. R.; Sun, Z. Z., A finite difference scheme for semilinear space-fractional diffusion equations with time delay, Appl. Math. Comput., 275, 238-254 (2016) · Zbl 1410.65310 |
| [10] | Yang, W.; Wang, D. L.; Yang, L., A stable numerical method for space fractional Landau-Lifshitz equations, Appl. Math. Lett., 61, 149-155 (2016) · Zbl 1347.65139 |
| [11] | Chen, S.; Liu, F.; Jiang, X.; Turner, I.; Burrage, K., Fast finite difference approximation for identifying parameters in a two-dimensional space-fractional nonlocal model with variable diffusivity coefficients, SIAM J. Numer. Anal., 54, 606-624 (2016) · Zbl 1382.65290 |
| [12] | Chen, A.; Li, C. P., Numerical solution of fractional diffusion-wave equation, Numer. Funct. Anal. Optim., 37, 19-39 (2016) · Zbl 1382.65236 |
| [13] | He, D. D.; Pan, K. J., An unconditionally stable linearized difference scheme for the fractional Ginzburg-Landau equation, Numer. Algorithms, 79, 899-925 (2018) · Zbl 1402.65088 |
| [14] | Feng, L. B.; Zhuang, P.; Liu, F.; Turner, I.; Anh, V.; Li, J., A fast second-order accurate method for a two-sided space-fractional diffusion equation with variable coefficients, Comput. Math. Appl., 73, 1155-1171 (2017) · Zbl 1412.65072 |
| [15] | Cheng, X. J.; Duan, J. Q.; Li, D. F., A novel compact ADI scheme for two-dimensional Riesz space fractional nonlinear reaction-diffusion equations, Appl. Math. Comput., 346, 452-464 (2019) · Zbl 1429.65216 |
| [16] | Arshad, S.; Bu, W. P.; Huang, J. F.; Tang, Y. F.; Zhao, Y., Finite difference method for time-space linear and nonlinear fractional diffusion equations, Int. J. Comput. Math., 95, 202-217 (2018) · Zbl 1387.65080 |
| [17] | Wang, J. J.; Xiao, A. G., An efficient conservative difference scheme for fractional Klein-Gordon-Schrödinger equations, Appl. Math. Comput., 320, 691-709 (2018) · Zbl 1427.65189 |
| [18] | Wang, D. L.; Xiao, A. G.; Yang, W., Maximum-norm error analysis of a difference scheme for the space fractional CNLS, Appl. Math. Comput., 257, 241-251 (2015) · Zbl 1339.65137 |
| [19] | Wang, J. J.; Xiao, A. G.; Wang, C. X., A conservative difference scheme for space fractional Klein-Gordon-Schrödinger equations with a high-degree Yukawa interaction, East Asia. J. Appl. Math., 8, 715-745 (2018) · Zbl 1468.65114 |
| [20] | Ervin, V. J.; Roop, J. P., Variational formulation for the stationary fractional advection dispersion equation, Numer. Methods Partial Differential Equations, 22, 558-576 (2006) · Zbl 1095.65118 |
| [21] | Bu, W. P.; Tang, Y. F.; Yang, J. Y., Galerkin finite element method for two-dimensional Riesz space fractional diffusion equations, J. Comput. Phys., 276, 26-38 (2014) · Zbl 1349.65441 |
| [22] | Du, N.; Wang, H., A fast finite element method for space-fractional dispersion equations on bounded domains in \(R^2\), SIAM J. Sci. Comput., 37, A1614-A1635 (2015) · Zbl 1331.65175 |
| [23] | Zheng, Y. Y.; Li, C. P.; Zhao, Z. G., A note on the finite element method for the space-fractional advection diffusion equation, Comput. Math. Appl., 59, 1718-1726 (2010) · Zbl 1189.65288 |
| [24] | Bu, W. P.; Tang, Y. F.; Wu, Y. C.; Yang, J. Y., Crank-Nicolson ADI Galerkin finite element method for two-dimensional fractional FitzHugh-Nagumo monodomain model, Appl. Math. Comput., 257, 355-364 (2015) · Zbl 1339.65170 |
| [25] | Yang, Z.; Yuan, Z.; Nie, Y.; Wang, J.; Zhu, X.; Liu, F., Finite element method for nonlinear Riesz space fractional diffusion equations on irregular domains, J. Comput. Phys., 330, 863-883 (2017) · Zbl 1378.35330 |
| [26] | Zhao, Y.; Bu, W. P.; Zhao, X.; Tang, Y. F., Galerkin finite element method for two-dimensional space and time fractional Bloch-Torrey equation, J. Comput. Phys., 350, 117-135 (2017) · Zbl 1380.65294 |
| [27] | Yue, X. Q.; Bu, W. P.; Shu, S.; Liu, M. H.; Wang, S., Fully finite element adaptive AMG method for time-space Caputo-Riesz fractional diffusion equations, Adv. Appl. Math. Mech., 10, 1103-1125 (2018) · Zbl 1488.65484 |
| [28] | Bu, W. P.; Shu, S.; Yue, X. Q.; Xiao, A. G.; Zeng, W., Space-time finite element method for the multi-term time-space fractional diffusion equation on a two-dimensional domain, Comput. Math. Appl. (2018) |
| [29] | Bu, W. P.; Xiao, A. G., An \(h-p\) version of the continuous Petrov-Galerkin finite element method for Riemann-Liouville fractional differential equation with novel test basis functions, Numer. Algorithms (2018) |
| [30] | Liu, F.; Zhuang, P.; Turner, I.; Burrage, K.; Anh, V., A new fractional finite volume method for solving the fractional diffusion equation, Appl. Math. Model., 38, 3871-3878 (2014) · Zbl 1429.65213 |
| [31] | Jia, J. H.; Wang, H., A fast finite volume method for conservative space-fractional diffusion equations in convex domains, J. Comput. Phys., 310, 63-84 (2016) · Zbl 1349.65562 |
| [32] | Karaa, S.; Mustapha, K.; Pani, A. K., Finite volume element method for two-dimensional fractional subdiffusion problems, IMA J. Appl. Math., 37, 945-964 (2017) · Zbl 1433.65214 |
| [33] | Song, F. Y.; Xu, C. J., Spectral direction splitting methods for two-dimensional space fractional diffusion equations, J. Comput. Phys., 299, 196-214 (2015) · Zbl 1352.65400 |
| [34] | Yang, Y., Jacobi spectral Galerkin methods for fractional integro-differential equations, Calcolo, 52, 519-542 (2015) · Zbl 1331.65179 |
| [35] | Yang, Y., Jacobi spectral Galerkin methods for Volterra integral equations with weakly singular kernel, Bull. Korean Math. Soc., 53, 247-262 (2016) · Zbl 1341.65053 |
| [36] | Bhrawy, A. H.; Zaky, M. A.; Baleanu, D.; Abdelkawy, M. A., A novel spectral approximation for the two-dimensional fractional sub-diffusion problems, Romanian J. Phys., 60, 344-359 (2015) |
| [37] | Pindza, E.; Owolabi, K. M., Fourier spectral method for higher order space fractional reaction-diffusion equations, Commun. Nonlinear Sci. Numer. Simul., 40, 112-128 (2016) · Zbl 1524.65676 |
| [38] | Yang, S. P.; Xiao, A. G., An efficient numerical method for fractional differential equations with two Caputo derivatives, J. Comput. Math., 34, 113-134 (2016) · Zbl 1363.65120 |
| [39] | Yang, Y.; Huang, Y. Q.; Zhou, Y., Numerical solutions for solving time fractional Fokkr-Planck equations based on spectral collocation methods, J. Comput. Appl. Math., 339, 389-404 (2018) · Zbl 1393.65037 |
| [40] | Heydari, M. H.; Avazzadeh, Z.; Yang, Y., A computational method for solving variable-order fractional nonlinear diffusion-wave equation, Appl. Math. Comput., 352, 235-248 (2019) · Zbl 1429.65240 |
| [41] | Wang, J. J.; Xiao, A. G., Conservative fourier spectral method and numerical investigation of space fractional Klein-Gordon-Schrödinger equations, Appl. Math. Comput., 350, 348-365 (2019) · Zbl 1429.65254 |
| [42] | Gong, C. Y.; Bao, W. M.; Tang, G. J.; Jiang, Y. W.; Liu, J., Computational challenge of fractional differential equations and the potential solutions: a survey, Math. Probl. Eng., 2015, Article 258265 pp. (2015) · Zbl 1394.65072 |
| [43] | Pang, H. K.; Sun, H. W., Multigrid method for fractional diffusion equations, J. Comput. Phys., 231, 693-703 (2012) · Zbl 1243.65117 |
| [44] | Pan, J. Y.; Ke, R. H.; Ng, M. K.; Sun, H. W., Preconditioning techniques for diagonal-times-Toeplitz matrices in fractional diffusion equations, SIAM J. Sci. Comput., 36, A2698-A2719 (2014) · Zbl 1314.65112 |
| [45] | Gu, X. M.; Huang, T. Z.; Zhao, X. L.; Li, H. B.; Li, L., Strang-type preconditioners for solving fractional diffusion equations by boundary value methods, J. Comput. Appl. Math., 277, 73-86 (2015) · Zbl 1302.65212 |
| [46] | Jin, X. Q.; Lin, F. R.; Zhao, Z., Preconditioned iterative methods for two-dimensional space-fractional diffusion equations, Commun. Comput. Phys., 18, 469-488 (2015) · Zbl 1388.65057 |
| [47] | Simmons, A.; Yang, Q. Q.; Moroney, T., A preconditioned numerical solver for stiff nonlinear reaction-diffusion equations with fractional Laplacians that avoids dense matrices, J. Comput. Phys., 287, 254-268 (2015) · Zbl 1352.65265 |
| [48] | Chen, H.; Lv, W.; Zhang, T. T., A Kronecker product splitting preconditioner for two-dimensional space-fractional diffusion equations, J. Comput. Phys., 360, 1-14 (2018) · Zbl 1395.65007 |
| [49] | Gong, C. Y.; Bao, W. M.; Tang, G. J., A parallel algorithm for the Riesz fractional reaction-diffusion equation with explicit finite difference method, Fract. Calc. Appl. Anal., 16, 654-669 (2013) · Zbl 1312.65134 |
| [50] | Q.L. Wang, J. Liu, C.Y. Gong, Y. Zhang, Z.C. Xing, A GPU-based fast solution for Riesz space fractional reaction-diffusion equation, Proc. 18th Int’l. Conf. Network-Based Information Systems, 2015, pp. 317-323.; Q.L. Wang, J. Liu, C.Y. Gong, Y. Zhang, Z.C. Xing, A GPU-based fast solution for Riesz space fractional reaction-diffusion equation, Proc. 18th Int’l. Conf. Network-Based Information Systems, 2015, pp. 317-323. |
| [51] | Lions, J. L.; Maday, Y.; Turinici, G., Résolution D’EDP par un schéma en tempspararéel, C. R. Math. Acad. Sci. Paris, 332, 661-668 (2001) · Zbl 0984.65085 |
| [52] | Falgout, R. D.; Friedhoff, S.; Kolev, Tz. V.; Maclachlan, S. P.; Schroder, J. B., Parallel time integration with multigrid, SIAM J. Sci. Comput., 36, C635-C661 (2014) · Zbl 1310.65115 |
| [53] | Wu, S. L., A second-order parareal algorithm for fractional PDEs, J. Comput. Phys., 307, 280-290 (2016) · Zbl 1352.65276 |
| [54] | Wu, S. L.; Zhou, T., Fast parareal iterations for fractional diffusion equations, J. Comput. Phys., 329, 210-226 (2017) · Zbl 1406.65077 |
| [55] | Gander, M. J.; Vandewalle, S., Analysis of the parareal time-parallel time-integration method, SIAM J. Sci. Comput., 29, 556-578 (2007) · Zbl 1141.65064 |
| [56] | XBraid: Parallel multigrid in time, http://llnl.gov/casc/xbraid; XBraid: Parallel multigrid in time, http://llnl.gov/casc/xbraid |
| [57] | Dobrev, V. A.; Kolev, Tz.; Petersson, N. A.; Schroder, J. B., Two-level convergence theory for multigrid reduction in time (MGRIT), SIAM J. Sci. Comput., 39, S501-S527 (2017) · Zbl 1416.65329 |
| [58] | Grisvard, P., Elliptic Problems in Nonsmooth Domains (2011), SIAM · Zbl 1231.35002 |
| [59] | Nievergelt, J., Parallel methods for integrating ordinary differential equations, Commun. ACM, 7, 731-733 (1964) · Zbl 0134.32804 |
| [60] | Miranker, W.; Liniger, W., Parallel methods for the numerical integration of ordinary differential equations, Math. Comp., 21, 303-320 (1967) · Zbl 0155.47204 |
| [61] | Gander, M. J., 50 years of time parallel time integration, Contrib. Math. Comput. Sci., 9, 69-114 (2015) · Zbl 1337.65127 |
| [62] | Ries, M.; Trottenberg, U., MGR-Ein Blitzschneller Elliptischer LöserTech. Report Preprint 277 SFB 72 (1979), Universität Bonn |
| [63] | HYPRE: Scalable linear solvers and multigrid methods, http://www.llnl.gov/casc/hypre; HYPRE: Scalable linear solvers and multigrid methods, http://www.llnl.gov/casc/hypre |
| [64] | Shishkin, G., Optimal difference schemes on piecewise-uniform meshes for a singularly perturbed parabolic convection-diffusion equation, Math. Model. Anal., 13, 99-112 (2008) · Zbl 1145.65059 |
| [65] | Bu, W. P.; Xiao, A. G.; Zeng, W., Finite difference/finite element methods for distributed-order time fractional diffusion equations, J. Sci. Comput., 72, 422-441 (2017) · Zbl 1375.65110 |
| [66] | Yang, Y.; Huang, Y. Q.; Zhou, Y., Numerical simulation of time fractional Cable equations and convergence analysis, Numer. Methods Partial Differential Equations, 34, 1556-1576 (2018) · Zbl 1407.65233 |
| [67] | Yang, Y.; Chen, Y. P.; Huang, Y. Q.; Wei, H. Y., Spectral collocation method for the time-fractional diffusion-wave equation and convergence analysis, Comput. Math. Appl., 73, 1218-1232 (2017) · Zbl 1412.65168 |
| [68] | Zhao, X.; Sun, Z. Z.; Hao, Z. P., A fourth-order compact ADI scheme for two-dimensional nonlinear space fractional Schrödinger equation, SIAM J. Sci. Comput., 36, A2865-A2886 (2014) · Zbl 1328.65187 |
| [69] | He, D. D.; Pan, K. J., An unconditionally stable linearized CCD-ADI method for generalized nonlinearSchrödinger equations with variable coefficients in two and three dimensions, Comput. Math. Appl., 73, 2360-2374 (2017) · Zbl 1373.65056 |
| [70] | Huang, Y. Q.; Li, X. Y.; Xiao, A. G., Fourier pseudospectral method on generalized sparse grids for the space-fractional Schrödinger equation, Comput. Math. Appl., 75, 4241-4255 (2018) · Zbl 1419.65079 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
