×

zbMATH — the first resource for mathematics

Fast solvers for finite difference scheme of two-dimensional time-space fractional differential equations. (English) Zbl 1442.65162
Summary: Generally, solving linear systems from finite difference alternating direction implicit scheme of two-dimensional time-space fractional differential equations with Gaussian elimination requires \(\mathcal{O}\left({NM}_1M_2\left({M_1^2}+{M_2^2}+NM_1M_2\right)\right)\) complexity and \(\mathcal{O}\left({N{M_1^2}{M_2^2}}\right)\) storage, where \(N\) is the number of temporal unknown and \(M_1, M_2\) are the numbers of spatial unknown in \(x, y\) directions respectively. By exploring the structure of the coefficient matrix in fully coupled form, it possesses block lower-triangular Toeplitz structure and its blocks are block-dense Toeplitz matrices with dense-Toeplitz blocks. Based on this special structure and cooperating with time-marching or divide-and-conquer technique, two fast solvers with storage \(\mathcal{O}\left ({NM}_1M_2\right)\) are developed. The complexity for the fast solver via time-marching is \(\mathcal{O}\left({NM}_1M_2\left(N+\log\left(M_1M_2\right)\right)\right)\) and the one via divide-and-conquer technique is \(\mathcal{O}\left({NM}_1M_2\left(\log^2 N+\log\left(M_1M_2\right)\right)\right)\). It is worth to remark that the proposed solvers are not lossy. Some discussions on achieving convergence rate for smooth and non-smooth solutions are given. Numerical results show the high efficiency of the proposed fast solvers.
MSC:
65M06 Finite difference methods for initial value and initial-boundary value problems involving PDEs
65M22 Numerical solution of discretized equations for initial value and initial-boundary value problems involving PDEs
35R11 Fractional partial differential equations
65Y20 Complexity and performance of numerical algorithms
65F05 Direct numerical methods for linear systems and matrix inversion
Software:
FODE
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Alikhanov, AA, A new difference scheme for the time fractional diffusion equation, J. Comput. Phys., 280, 424-438 (2015) · Zbl 1349.65261
[2] Bertaccini, D.; Durastante, F., Limited memory block preconditioners for fast solution of fractional partial differential equations, J. Sci. Comput., 77, 2, 950-970 (2018) · Zbl 1404.65014
[3] Breiten, T.; Simoncini, V.; Stoll, M., Low-rank solvers for fractional differential equations, Electron. T. Numer. Anal., 45, 107-132 (2016) · Zbl 1338.65071
[4] Capizzano, SS; Tyrtyshnikov, E., Any circulant-like preconditioner for multilevel matrices is not superlinear, SIAM J. Matrix Anal. Appl., 21, 2, 431-439 (2000) · Zbl 0952.65037
[5] Chan, RH; Ng, MK, Conjugate gradient methods for Toeplitz systems, SIAM Rev., 38, 3, 427-482 (1996) · Zbl 0863.65013
[6] Chen, X.; Wang, WF; Ding, D.; Lei, SL, A fast preconditioned policy iteration method for solving the tempered fractional HJB equation governing American options valuation, Comput. Math. Appl., 73, 9, 1932-1944 (2017) · Zbl 1372.91115
[7] Chen, X.; Zeng, F.; Karniadakis, GE, A tunable finite difference method for fractional differential equations with non-smooth solutions, Comput. Methods Appl. Mech. Eng., 318, 193-214 (2017) · Zbl 1439.65082
[8] Deng, WH, Finite element method for the space and time fractional Fokker-Planck equation, SIAM J. Numer. Anal., 47, 1, 204-226 (2008) · Zbl 1416.65344
[9] Donatelli, M.; Mazza, M.; Serra-Capizzano, S., Spectral analysis and structure preserving preconditioners for fractional diffusion equations, J. Comput. Phys, 307, 262-279 (2016) · Zbl 1352.65305
[10] Ford, NJ; Yan, Y., An approach to construct higher order time discretisation schemes for time fractional partial differential equations with nonsmooth data, Fract. Calc. Appl. Anal., 20, 5, 1076-1105 (2017) · Zbl 1377.65102
[11] Fu, HF; Ng, MK; Wang, H., A divide-and-conquer fast finite difference method for space-time fractional partial differential equation, Comput. Math. Appl., 73, 6, 1233-1242 (2017) · Zbl 1412.65073
[12] Gao, GH; Sun, ZZ, A compact finite difference scheme for the fractional sub-diffusion equations, J. Comput. Phys., 230, 3, 586-595 (2011) · Zbl 1211.65112
[13] Gohberg, I.; Olshevsky, V., Circulants, displacements and decompositions of matrices, Integr. Equat. Oper. Th., 15, 5, 730-743 (1992) · Zbl 0772.15010
[14] Hao, Z.; Cao, W., An improved algorithm based on finite difference schemes for fractional boundary value problems with nonsmooth solution, J. Sci. Comput., 73, 1, 395-415 (2017) · Zbl 1377.26009
[15] Hilfer, R., Applications of Fractional Calculus in Physics (2000), Singapore: World Scientific, Singapore · Zbl 0998.26002
[16] Huang, YC; Lei, SL, A fast numerical method for block lower triangular Toeplitz with dense Toeplitz blocks system with applications to time-space fractional diffusion equations, Numer. Algor., 76, 3, 605-616 (2017) · Zbl 1377.65038
[17] Jiang, SD; Zhang, JW; Zhang, Q.; Zhang, ZM, Fast evaluation of the Caputo fractional derivative and its applications to fractional diffusion equations, Commun. Comput. Phys., 21, 3, 650-678 (2017)
[18] 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) · Zbl 1440.65138
[19] Ke, RH; Ng, MK; Sun, HW, A fast direct method for block triangular Toeplitz-like with tri-diagonal block systems from time-fractional partial differential equations, J. Comput. Phys., 303, 203-211 (2015) · Zbl 1349.65404
[20] Kopteva, N.; Stynes, M., Analysis and numerical solution of a Riemann-Liouville fractional derivative two-point boundary value problem, Adv. Comput. Math., 43, 1, 77-99 (2017) · Zbl 1381.65057
[21] Langlands, T.; Henry, BI, The accuracy and stability of an implicit solution method for the fractional diffusion equation, J. Comput. Phys., 205, 2, 719-736 (2005) · Zbl 1072.65123
[22] Lei, SL; Huang, YC, Fast algorithms for high-order numerical methods for space fractional diffusion equations, Int. J. Comput. Math., 94, 5, 1062-1078 (2017) · Zbl 1378.65160
[23] Lei, SL; Sun, HW, A circulant preconditioner for fractional diffusion equations, J. Comput. Phys., 242, 715-725 (2013) · Zbl 1297.65095
[24] Liu, FW; Zhuang, PH; Turner, I.; Burrage, K.; Anh, V., A new fractional finite volume method for solving the fractional diffusion equation, Appl. Math. Modell., 38, 15, 3871-3878 (2014) · Zbl 1429.65213
[25] Lu, X.; Pang, HK; Sun, HW, Fast approximate inversion of a block triangular Toeplitz matrix with applications to fractional sub-diffusion equations, Numer. Linear Algebra Appl., 22, 5, 866-882 (2015) · Zbl 1349.65104
[26] Lu, X., Pang, H.K., Sun, H.W., Vong, S.: Approximate inversion method for time-fractional subdiffusion equations. Numer. Linear Algebra Appl. 10.1002/nla.2132 · Zbl 06861604
[27] Lubich, C., Discretized fractional calculus, SIAM J. Math. Anal., 17, 3, 704-719 (1986) · Zbl 0624.65015
[28] Magin, RL, Fractional Calculus in Bioengineering (2006), Danbury: Begell House Redding, Danbury
[29] Moghaderi, H.; Dehghan, M.; Donatelli, M.; Mazza, M., Spectral analysis and multigrid preconditioners for two-dimensional space-fractional diffusion equations, J. Comput. Phys, 350, 992-1011 (2017) · Zbl 1380.65240
[30] Pan, JY; Ke, RH; Ng, MK; Sun, HW, Preconditioning techniques for diagonal-times-Toeplitz matrices in fractional diffusion equations, SIAM J. Sci. Comput., 36, 6, A2698-A2719 (2014) · Zbl 1314.65112
[31] Pang, HK; Sun, HW, Multigrid method for fractional diffusion equations, J. Comput. Phys., 231, 2, 693-703 (2012) · Zbl 1243.65117
[32] Pang, HK; Sun, HW, Fourth order finite difference schemes for time-space fractional sub-diffusion equations, Comput. Math. Appl., 71, 6, 1287-1302 (2016)
[33] Podlubny, I., Fractional Differential Equations, vol. 198 (1999), New York: Academic Press, New York · Zbl 0918.34010
[34] Song, J.; Yu, Q.; Liu, FW; Turner, I., A spatially second-order accurate implicit numerical method for the space and time fractional Bloch-Torrey equation, Numer. Algor., 66, 4, 911-932 (2014) · Zbl 1408.65057
[35] Sun, H.; Sun, ZZ; Gao, GH, Some high order difference schemes for the space and time fractional Bloch-Torrey equations, Appl. Math. Comput., 281, 356-380 (2016) · Zbl 1410.65329
[36] Sun, ZZ; Wu, XN, A fully discrete difference scheme for a diffusion-wave system, Appl. Numer. Math., 56, 2, 193-209 (2006) · Zbl 1094.65083
[37] Yan, Y.; Sun, ZZ; Zhang, J., Fast evaluation of the Caputo fractional derivative and its applications to fractional diffusion equations: a second-order scheme, Commun. Comput. Phys., 22, 4, 1028-1048 (2017)
[38] Yu, Q.; Liu, FW; Turner, I.; Burrage, K., A computationally effective alternating direction method for the space and time fractional Bloch-Torrey equation in 3-D, Appl. Math. Comput., 219, 8, 4082-4095 (2012) · Zbl 1311.65114
[39] Zayernouri, M.; Karniadakis, GE, Fractional spectral collocation method, SIAM J. Sci. Comput., 36, 1, A40-A62 (2014) · Zbl 1294.65097
[40] Zeng, F.; Mao, Z.; Karniadakis, GE, A generalized spectral collocation method with tunable accuracy for fractional differential equations with end-point singularities, SIAM J. Sci. Comput., 39, 1, A360-A383 (2017) · Zbl 1431.65193
[41] Zeng, F., Turner, I., Burrage, K.: A stable fast time-stepping method for fractional integral and derivative operators. J. Sci. Comput. 10.1007/s10915-018-0707-9 (2018) · Zbl 1406.65047
[42] Zeng, F.; Zhang, Z.; Karniadakis, GE, Second-order numerical methods for multi-term fractional differential equations: smooth and non-smooth solutions, Comput. Methods Appl. Mech. Eng., 327, 478-502 (2017) · Zbl 1439.65081
[43] Zhao, L.; Deng, W., High order finite difference methods on non-uniform meshes for space fractional operators, Adv. Comput. Math., 42, 2, 425-468 (2016) · Zbl 1347.65130
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.