On \(\tau\)-preconditioner for a novel fourth-order difference scheme of two-dimensional Riesz space-fractional diffusion equations. (English) Zbl 1538.65246

Huang, Yuan-Yuan; Qu, Wei; Lei, Siu-Long

Comput. Math. Appl. 145, 124-140 (2023).

Summary: In this paper, a \(\tau\)-preconditioner for a novel fourth-order finite difference scheme of two-dimensional Riesz space-fractional diffusion equations (2D RSFDEs) is considered, in which a fourth-order fractional centered difference operator is adopted for the discretizations of spatial Riesz fractional derivatives, while the Crank-Nicolson method is adopted to discretize the temporal derivative. The scheme is proven to be unconditionally stable and has a convergence rate of \(\mathcal{O}(\Delta t^2+\Delta x^4+\Delta y^4)\) in the discrete \(L^2\)-norm, where \(\Delta t\), \(\Delta x\) and \(\Delta y\) are the temporal and spatial step sizes, respectively. In addition, the preconditioned conjugate gradient (PCG) method with \(\tau\)-preconditioner is applied to solve the discretized symmetric positive definite linear systems arising from 2D RSFDEs. Theoretically, we show that the \(\tau\)-preconditioner is invertible by a new technique, and analyze the spectrum of the corresponding preconditioned matrix. Moreover, since the \(\tau\)-preconditioner can be diagonalized by the discrete sine transform matrix, the total operation cost of the PCG method is \(\mathcal{O}(N_xN_y\log N_xN_y)\), where \(N_x\) and \(N_y\) are the number of spatial unknowns in \(x\)- and \(y\)-directions. Finally, numerical experiments are performed to verify the convergence orders, and show that the PCG method with the \(\tau\)-preconditioner for solving the discretized linear system has a convergence rate independent of discretization stepsizes.

MSC:

65M06	Finite difference methods for initial value and initial-boundary value problems involving PDEs
65N06	Finite difference methods for boundary value problems involving PDEs
35R11	Fractional partial differential equations
65M12	Stability and convergence of numerical methods for initial value and initial-boundary value problems involving PDEs
65F08	Preconditioners for iterative methods
65F10	Iterative numerical methods for linear systems
26A33	Fractional derivatives and integrals

Keywords:

Riesz space-fractional diffusion equations; \(\tau\)-preconditioner; stability and convergence; spectral analysis; preconditioned conjugate gradient method

References:

[1]	Çelik, C.; Duman, M., Crank-Nicolson method for the fractional diffusion equation with the Riesz fractional derivative, J. Comput. Phys., 231, 4, 1743-1750 (2012) · Zbl 1242.65157
[2]	Benson, D. A.; Wheatcraft, S. W.; Meerschaert, M. M., Application of a fractional advection-dispersion equation, Water Resour. Res., 36, 6, 1403-1412 (2000)
[3]	Benson, D. A.; Wheatcraft, S. W.; Meerschaert, M. M., The fractional-order governing equation of Lévy motion, Water Resour. Res., 36, 6, 1413-1423 (2000)
[4]	Raberto, M.; Scalas, E.; Mainardi, F., Waiting-times and returns in high-frequency financial data: an empirical study, Physica A, 314, 1-4, 749-755 (2002) · Zbl 1001.91033
[5]	Du, N.; Wang, H.; Liu, W. B., A fast gradient projection method for a constrained fractional optimal control, J. Sci. Comput., 68, 1, 1-20 (2016) · Zbl 1344.65056
[6]	Pougkakiotis, S.; Pearson, J. W.; Leveque, S.; Gondzio, J., Fast solution methods for convex quadratic optimization of fractional differential equations, SIAM J. Matrix Anal. Appl., 41, 3, 1443-1476 (2020) · Zbl 1458.65026
[7]	Magin, R. L., Fractional Calculus in Bioengineering (2006), Begell House: Begell House Redding, New York
[8]	Zhu, C.; Zhang, B. Y.; Fu, H. F.; Liu, J., Efficient second-order ADI difference schemes for three-dimensional Riesz space-fractional diffusion equations, Comput. Math. Appl., 98, 24-39 (2021) · Zbl 1524.65447
[9]	Xing, Z. Y.; Wen, L. P., Numerical analysis and fast implementation of a fourth-order difference scheme for two-dimensional space-fractional diffusion equations, Appl. Math. Comput., 346, 155-166 (2019) · Zbl 1429.65203
[10]	Liu, H.; Zheng, X. C.; Wang, H.; Fu, H. F., Analysis and efficient implementation of ADI finite volume method for Riesz space-fractional diffusion equations in two space dimensions, Numer. Methods Partial Differ. Equ., 37, 818-835 (2021) · Zbl 1534.65205
[11]	Qu, W.; Li, Z., Fast direct solver for CN-ADI-FV scheme to two-dimensional Riesz space-fractional diffusion equations, Appl. Math. Comput., 401, Article 126033 pp. (2021) · Zbl 1508.65114
[12]	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
[13]	Li, J. C.; Chen, Y. T.; Liu, G. Q., High-order compact ADI methods for parabolic equations, Comput. Math. Appl., 52, 8-9, 1343-1356 (2006) · Zbl 1121.65092
[14]	Li, J. C.; Chen, M.; Chen, M., Developing and analyzing fourth-order difference methods for the metamaterial Maxwell’s equations, Adv. Comput. Math., 45, 213-241 (2019) · Zbl 1428.65011
[15]	Meerschaert, M. M.; Tadjeran, C., Finite difference approximations for fractional advection-dispersion flow equations, J. Comput. Appl. Math., 172, 1, 65-77 (2004) · Zbl 1126.76346
[16]	Meerschaert, M. M.; Tadjeran, C., Finite difference approximations for two-sided space-fractional partial differential equations, Appl. Numer. Math., 56, 1, 80-90 (2006) · Zbl 1086.65087
[17]	Tian, W. Y.; Zhou, H.; Deng, W. H., A class of second order difference approximations for solving space fractional diffusion equations, Math. Comput., 84, 294, 1703-1727 (2015) · Zbl 1318.65058
[18]	Sousa, E.; Li, C., A weighted finite difference method for the fractional diffusion equation based on the Riemann-Liouville derivative, Appl. Numer. Math., 90, 22-37 (2015) · Zbl 1326.65111
[19]	Chen, M. H.; Deng, W. H., Fourth order accurate scheme for the space fractional diffusion equations, SIAM J. Numer. Anal., 52, 3, 1418-1438 (2014) · Zbl 1318.65048
[20]	Chen, M. H.; Deng, W. H., Fourth order difference approximations for space Riemann-Liouville derivatives based on weighted and shifted Lubich difference operators, Commun. Comput. Phys., 16, 2, 516-540 (2014) · Zbl 1388.65130
[21]	Hao, Z. P.; Sun, Z. Z.; Cao, W. R., A fourth-order approximation of fractional derivatives with its applications, J. Comput. Phys., 281, 787-805 (2015) · Zbl 1352.65238
[22]	Lin, F. R.; She, Z. H., Stability and convergence of 3-point WSGD schemes for two-sided space fractional advection-diffusion equations with variable coefficients, Appl. Numer. Math., 167, 281-307 (2021) · Zbl 1481.65144
[23]	She, Z. H., A class of unconditioned stable 4-point WSGD schemes and fast iteration methods for space fractional diffusion equations, J. Sci. Comput., 92, 1, 1-35 (2022) · Zbl 07549606
[24]	Ding, H. F.; Li, C. P., High-order numerical algorithms for Riesz derivatives via constructing new generating functions, J. Sci. Comput., 71, 2, 759-784 (2017) · Zbl 1398.65030
[25]	Ding, H. F.; Li, C. P.; Chen, Y. Q., High-order algorithms for Riesz derivative and their applications (II), J. Comput. Phys., 293, 218-237 (2015) · Zbl 1349.65284
[26]	Ding, H. F.; Li, C. P., High-order algorithms for Riesz derivative and their applications (III), Fract. Calc. Appl. Anal., 19, 1, 19-55 (2016) · Zbl 1332.65122
[27]	Ding, H. F.; Li, C. P., High-order algorithms for Riesz derivative and their applications (V), Numer. Methods Partial Differ. Equ., 33, 5, 1754-1794 (2017) · Zbl 1376.65024
[28]	Ortigueira, M. D., Riesz potential operators and inverses via fractional centred derivatives, Int. J. Math. Math. Sci. (2006) · Zbl 1122.26007
[29]	Zhao, X.; Sun, Z. Z.; Hao, Z. P., A fourth-order compact ADI scheme for two-dimensional nonlinear space fractional Schrodinger equation, SIAM J. Sci. Comput., 36, 6, A2865-A2886 (2014) · Zbl 1328.65187
[30]	Xiao, A. G.; Wang, J. J., Symplectic scheme for the Schrödinger equation with fractional Laplacian, Appl. Numer. Math., 146, 469-487 (2019) · Zbl 1423.81070
[31]	Hu, D. D.; Cai, W. J.; Song, Y. Z.; Wang, Y. S., A fourth-order dissipation-preserving algorithm with fast implementation for space fractional nonlinear damped wave equations, Commun. Nonlinear Sci. Numer. Simul., 91, Article 105432 pp. (2020) · Zbl 1448.65105
[32]	Fu, Y. Y.; Cai, W. J.; Wang, Y. S., An explicit structure-preserving algorithm for the nonlinear fractional Hamiltonian wave equation, Appl. Math. Lett., 102, Article 106123 pp. (2020) · Zbl 1440.65087
[33]	Xing, Z. Y.; Wen, L. P.; Xiao, H. Y., A fourth-order conservative difference scheme for the Riesz space-fractional Sine-Gordon equations and its fast implementation, Appl. Numer. Math., 159, 221-238 (2021) · Zbl 1459.65161
[34]	Wang, H.; Wang, K. X.; Sircar, T., A direct \(\mathcal{O}(N \log^2 N)\) finite difference method for fractional diffusion equations, J. Comput. Phys., 229, 21, 8095-8104 (2010) · Zbl 1198.65176
[35]	Wang, K. X.; Wang, H., A fast characteristic finite difference method for fractional advection-diffusion equations, Adv. Water Resour., 34, 7, 810-816 (2011)
[36]	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, 6, A2698-A2719 (2014) · Zbl 1314.65112
[37]	Pang, H. K.; Sun, H. W., Multigrid method for fractional diffusion equations, J. Comput. Phys., 231, 2, 693-703 (2012) · Zbl 1243.65117
[38]	Lei, S. L.; Sun, H. W., A circulant preconditioner for fractional diffusion equations, J. Comput. Phys., 242, 715-725 (2013) · Zbl 1297.65095
[39]	Donatelli, M.; Krause, R.; Mazza, M.; Trotti, K., All-at-once multigrid approaches for one-dimensional space-fractional diffusion equations, Calcolo, 58, 4, 1-25 (2021) · Zbl 1528.65044
[40]	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
[41]	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
[42]	Breiten, T.; Simoncini, V.; Stoll, M., Low-rank solvers for fractional differential equations, Electron. Trans. Numer. Anal., 45, 107-132 (2016) · Zbl 1338.65071
[43]	Lei, S. L.; Chen, X.; Zhang, X. H., Multilevel circulant preconditioner for high-dimensional fractional diffusion equations, East Asian J. Appl. Math., 6, 2, 109-130 (2016) · Zbl 1481.65140
[44]	Jin, X. Q.; Lin, F. R.; Zhao, Z., Preconditioned iterative methods for two-dimensional space-fractional diffusion equations, Commun. Comput. Phys., 18, 2, 469-488 (2015) · Zbl 1388.65057
[45]	Chan, R. H.; Strang, G., Toeplitz equations by conjugate gradients with circulant preconditioner, SIAM J. Sci. Stat. Comput., 10, 1, 104-119 (1989) · Zbl 0666.65030
[46]	Chan, R. H.; Ng, M. K., Conjugate gradient methods for Toeplitz systems, SIAM Rev., 38, 3, 427-482 (1996) · Zbl 0863.65013
[47]	Serra, S., Superlinear PCG methods for symmetric Toeplitz systems, Math. Comput., 68, 226, 793-803 (1999) · Zbl 1043.65066
[48]	Sun, L. Y.; Fang, Z. W.; Lei, S. L.; Sun, H. W.; Zhang, J. L., A fast algorithm for two-dimensional distributed-order time-space fractional diffusion equations, Appl. Math. Comput., 425, Article 127095 pp. (2022) · Zbl 1510.65210
[49]	Barakitis, N.; Ekström, S.-E.; Vassalos, P., Preconditioners for fractional diffusion equations based on the spectral symbol, Numer. Linear Algebra Appl., Article e2441 pp. (2022) · Zbl 07584149
[50]	Shao, X. H.; Kang, C. B., A preconditioner based on sine transform for space fractional diffusion equations, Appl. Numer. Math., 178, 248-261 (2022) · Zbl 1497.65065
[51]	Zhang, C. H.; Yu, J. W.; Wang, X., A fast second-order scheme for nonlinear Riesz space-fractional diffusion equations, Numer. Algorithms, 1-24 (2022)
[52]	Zeng, M. L.; Yang, J. F.; Zhang, G. F., On τ matrix-based approximate inverse preconditioning technique for diagonal-plus-Toeplitz linear systems from spatial fractional diffusion equations, J. Comput. Appl. Math., Article 114088 pp. (2022) · Zbl 1485.65029
[53]	Lu, X.; Fang, Z. W.; Sun, H. W., Splitting preconditioning based on sine transform for time-dependent Riesz space fractional diffusion equations, J. Appl. Math. Comput., 66, 1, 673-700 (2021) · Zbl 1475.65015
[54]	Lin, X. L.; Huang, X.; Ng, M. K.; Sun, H. W., A τ-preconditioner for a non-symmetric linear system arising from multi-dimensional Riemann-Liouville fractional diffusion equation, Numer. Algorithms, 1-19 (2022)
[55]	Bini, D.; Benedetto, F., A new preconditioner for the parallel solution of positive definite Toeplitz systems, (Proceedings of the Second Annual ACM Symposium on Parallel Algorithms and Architectures (1990)), 220-223
[56]	Bini, D.; Capovani, M., Spectral and computational properties of band symmetric Toeplitz matrices, Linear Algebra Appl., 52, 99-126 (1983) · Zbl 0549.15005
[57]	Golub, G. H.; Van Loan, C. F., Matrix Computations (2013), JHU Press · Zbl 1268.65037
[58]	Chan, H. F.; Jin, X. Q., An Introduction to Iterative Toeplitz Solvers (2007), SIAM · Zbl 1146.65028
[59]	Grenander, U.; Szegö, G., Toeplitz Forms and Their Applications (1958), Univ. of California Press · Zbl 0080.09501
[60]	Huang, X.; Lin, X. L.; Ng, M. K.; Sun, H. W., Spectral analysis for preconditioning of multi-dimensional Riesz fractional diffusion equations, Numer. Math., Theory Methods Appl., 15, 565-591 (2022) · Zbl 1513.65054
[61]	Jin, X. Q., Preconditioning Techniques for Toeplitz Systems (2010), Higher Education Press: Higher Education Press Beijing
[62]	Du, N.; Wang, H.; Wang, C., A fast method for a generalized nonlocal elastic model, J. Comput. Phys., 297, 72-83 (2015) · Zbl 1349.76455
[63]	Horn, R. A.; Johnson, C. R., Matrix Analysis (2012), Cambridge University Press