An ADI Iteration Method for Solving Discretized Two-Dimensional Space-Fractional Diffusion Equations

Abstract

The two-dimensional (2D) space-fractional diffusion equations can be effectively discretized by an implicit finite difference scheme with the shifted Grünwald formula. The coefficient matrices of the discretized linear systems are equal to the sum of the identity matrix and a block-Toeplitz with a Toeplitz-block matrix. In this paper, one variant of the alternating direction implicit (ADI) iteration method is proposed to solve the discretized linear systems. By making use of suitable permutations, each iteration of the ADI iteration method requires the solutions of two linear subsystems whose coefficient matrices are block diagonal matrices with diagonal blocks being Toeplitz matrices. These two linear subsystems can be solved block by block by fast or superfast direct methods. Theoretical analyses show that the ADI iteration method is convergent. In particular, we derive a sharp upper bound about its asymptotic convergence rate and deduce the optimal value of its iteration parameter. Numerical results exhibit that the corresponding ADI preconditioner can improve the computational efficiency of the Krylov subspace iteration methods.

Keywords

Space-fractional diffusion equations / Block-Toeplitz with Toeplitz-block (BTTB) matrix / Alternating direction implicit (ADI) iteration / Preconditioning / Krylov subspace method / 65F08 / 65F10 / 65L12 / 65M22

References

[1] AxelssonOIterative Solution Methods, 1994, Cambridge. Cambridge University Press.

[2] BaiJ, FengX-C. Fractional-order anisotropic diffusion for image denoising. IEEE T. Image Process., 2007, 16: 2492-2502

[3] BaiZ-Z. Several splittings for non-Hermitian linear systems. Sci. China, Ser. A Math., 2008, 51(8): 1339-1348

[4] BaiZ-Z. Respectively scaled HSS iteration methods for solving discretized spatial fractional diffusion equations. Numer. Linear Algebra Appl., 2018, 25e2157

[5] Bai, Z.-Z.: A two-step matrix splitting iteration paradigm based on one single splitting for solving systems of linear equations. Numer. Linear Algebra Appl. 31, e2510 (2024)

[6] BaiZ-Z, GolubGH, LuL-Z, YinJ-F. Block triangular and skew-Hermitian splitting methods for positive-definite linear systems. SIAM J. Sci. Comput., 2005, 26: 844-863

[7] BaiZ-Z, GolubGH, NgMK. Hermitian and skew-Hermitian splitting methods for non-Hermitian positive definite linear systems. SIAM J. Matrix Anal. Appl., 2003, 24: 603-626

[8] BaiZ-Z, LuK-Y. On banded $M$-splitting iteration methods for solving discretized spatial fractional diffusion equations. BIT Numer. Math., 2019, 59: 1-33

[9] BaiZ-Z, LuK-Y. On regularized Hermitian splitting iteration methods for solving discretized almost-isotropic spatial fractional diffusion equations. Numer. Linear Algebra Appl., 2020, 27e2274

[10] BaiZ-Z, LuK-Y. Fast matrix splitting preconditioners for higher dimensional spatial fractional diffusion equations. J. Comput. Phys., 2020, 404: 1-13

[11] BaiZ-Z, LuK-Y, PanJ-Y. Diagonal and Toeplitz splitting iteration methods for diagonal-plus-Toeplitz linear systems from spatial fractional diffusion equations. Numer. Linear Algebra Appl., 2017, 24e2093

[12] BaiZ-Z, PanJ-YMatrix Analysis and Computations, 2021, Philadelphia. SIAM.

[13] CarrerasBA, LynchVE, ZaslavskyGM. Anomalous diffusion and exit time distribution of particle tracers in plasma turbulence models. Phys. Plasmas, 2001, 8: 5096-5103

[14] ChenF, LiT-Y, MuratovaGV. Lopsided scaled HSS preconditioner for steady-state space-fractional diffusion equations. Calcolo, 2021, 5826

[15] ChenF, RenB-C. On preconditioning of double saddle point linear systems arising from liquid crystal director modeling. Appl. Math. Lett., 2023, 136108445

[16] ChenH, LyuW, ZhangT-T. A Kronecker product splitting preconditioner for two-dimensional space-fractional diffusion equations. J. Comput. Phys., 2018, 360: 1-14

[17] LeiS-L, SunH-W. A circulant preconditioner for fractional diffusion equations. J. Comput. Phys., 2013, 242: 715-725

[18] LinF-R, YangS-W, JinX-Q. Preconditioned iterative methods for fractional diffusion equation. J. Comput. Phys., 2014, 256: 109-117

[19] MaginRLFractional Calculus in Bioengineering, 2006, Danbury. Begell House Publishers.

[20] MurioDA. Implicit finite difference approximation for time fractional diffusion equations. Appl. Math. Comput., 2008, 56: 1138-1145

[21] NgMK, BaiZ-Z. A hybrid preconditioner of banded matrix approximation and alternating direction implicit iteration for symmetric Sinc-Galerkin linear systems. Linear Algebra Appl., 2003, 366: 317-335

[22] OldhamKB. Fractional differential equations in electrochemistry. Adv. Engrg. Software, 2010, 41: 9-12

[23] PanJ-Y, BaiZ-Z, NgMK. Two-step waveform relaxation methods for implicit linear initial value problems. Numer. Linear Algebra Appl., 2005, 12: 293-304

[24] PanJ-Y, KeR-H, NgMK, SunH-W. Preconditioning techniques for diagonal-times-Toeplitz matrices in fractional diffusion equations. SIAM J. Sci. Comput., 2014, 36: A2698-A2719

[25] PanJ-Y, NgMK, WangH. Fast iterative solvers for linear systems arising from time-dependent space-fractional diffusion equations. SIAM J. Sci. Comput., 2016, 38: A2806-A2826

[26] RabertoM, ScalasE, MainardiF. Waiting-times and returns in high-frequency financial data: an empirical study. Phys. A, 2002, 314: 749-755

[27] SokolovIM, KlafterJ, BlumenA. Fractional kinetics. Phys. Today, 2002, 55: 28-53

[28] TadjeranC, MeerschaertMM, SchefflerHP. A second-order accurate numerical approximation for the fractional diffusion equation. J. Comput. Phys., 2006, 213: 205-213

[29] WangH, WangK-X. An $O(N\log {2N})$ alternating-direction finite difference method for two-dimensional fractional diffusion equations. J. Comput. Phys., 2011, 230: 7830-7839

[30] WangH, WangK-X, SircarT. A direct $O(N\log {2N})$ finite difference method for fractional diffusion equations. J. Comput. Phys., 2010, 229: 8095-8104

RIGHTS & PERMISSIONS

Shanghai University