Preconditioned iterative methods for fractional diffusion equation☆
Introduction
Fractional differential equations emerge from numerous topics such as turbulent flow [7], [27], chaotic dynamics of classical conservative systems [39], groundwater contaminant transport [4], [5], and applications in physics [28], finance [25], biology [18], and image processing [2]. Since there are very few fractional differential equations whose analytical closed-form solutions are available, the research on numerical methods for the solution of the equation has attracted many researchers, and a lot of research results have been obtained; see [3], [6], [11], [12], [13], [15], [16], [17], [19], [20], [21], [22], [23], [29], [30], [31], [32], [33], [34], [35] and references therein. The existence and uniqueness of the solution also have been studied, e.g., Wang and Yang proved the existence and uniqueness of the solutions to variable-coefficient space-fractional diffusion equations [38].
In this paper, we consider the following initial–boundary value problem for a one-dimensional space fractional diffusion equation (FDE): where , is the source term, and . In this paper, we use the Grünwald–Letnikov form [24] to define the left-sided and the right-sided fractional derivatives as follows: where denotes the largest integer that is not larger than a, , and
We now briefly review recent developments of numerical methods for the solution of FDEs. In 2004 and 2006, Meerschaert and Tadjeran proposed a shifted Grünwald discretization to approximate the FDE with a left-sided fractional derivative and the FDE with two-sided fractional derivatives, respectively [20], [21]. In 2006, Tadjeran, Meerschaert, and Scheffler proposed a second-order accurate numerical scheme by using the classical Crank–Nicholson method and the Richardson extrapolation scheme [32]. The above methods were proved to be unconditionally stable. Nevertheless, the above-mentioned methods, as well as other finite difference and finite element methods [11], [12], [13], yield full coefficient matrices, which result in storage and complexity.
Recently, Wang, Wang, and Sircar [36] discovered that the coefficient matrix of Meerschaert–Tadjeranʼs method [21] possesses a Toeplitz-like structure: it can be written as a sum of diagonal-multiply-Toeplitz matrices. Thus the storage requirement is reduced from to , and the matrix–vector multiplications can be done with complexity by using a fast algorithm based on the fast Fourier transform (FFT) [9], [10], [14]. By using the Toeplitz-like structure, Wang et al. proposed a fast finite difference scheme by approximating the coefficient matrix with a banded matrix of bandwidth . As a result, the computational cost per time step is only , which is much lower than other methods. However, the unconditional stability of their scheme has not been proved.
Most recently, iterative solvers for the discretized system of the FDE by Meerschaert–Tadjeranʼs method have been proposed and studied [23], [37]. Wang and Wang, two authors of [36], proposed the conjugate gradient normal residual (CGNR) method [37] to solve the discretized system. Their numerical results show that the CGNR method converges fast if the diffusion coefficients are very small (in that case the coefficient matrix is well-conditioned). However, if the diffusion coefficients are not sufficiently small, the resulting system becomes ill-conditioned and hence the CGNR method converges very slowly; see for instance, [23] and numerical results in Section 4. Pang and Sun developed an efficient multigrid method by following the idea in [8] and using the Toeplitz-like structure of the coefficient matrices, which only requires operations at each time step [23]. Fast algorithms for two-dimensional space fractional diffusion equations also have been studied; see [34], [35] and references therein.
In this paper, we use the well-known Crank–Nicholson method to discretize the FDE and then use the spatial extrapolation method to obtain temporally and spatially second-order accurate numerical estimates. We propose preconditioned conjugate gradient normal residual (preconditioned CGNR) method and preconditioned generalized minimal residual (preconditioned GMRES) method for the discretized systems, with preconditioners being constructed based on banded matrices of fixed bandwidth. As the multigrid method [23], the cost per iteration of the above preconditioned iterative methods is operations.
The paper is organized as follows. In Section 2, we discretize the FDE (1) by the Crank–Nicholson method and give the structure of the coefficient matrix. In Section 3, we propose the preconditioned CGNR method and the preconditioned GMRES for the discretized system of (1). In Section 4 we present numerical results to illustrate the efficiency of the proposed algorithms.
Section snippets
The Crank–Nicholson finite difference scheme
Let N and M be positive integers, and let and be the sizes of spatial grid and time step, respectively. We define a spatial and temporal partition: Let The Crank–Nicholson finite difference scheme (CN scheme) is given by
Preconditioned CGNR method and preconditioned GMRES method
Since the coefficient matrix in (5) is not symmetric positive definite, we consider solving it by using the preconditioned CGNR method or the preconditioned GMRES method.
We require the following proposition [20], [21], [36] about the properties of .
Proposition 1 Let and be defined in (2). Then we have
We see from Proposition 1 that which implies that is strongly
Numerical results
In this section, we employ the preconditioned CGNR method and the preconditioned GMRES method proposed in the previous section to solve the linear system (5). For all methods, we choose the initial guess as We set as an initial guess since it is a good approximation of [36]. The stopping criterion is where is the residual vector after j iterations. In our tests, we set the half bandwidth of the
Concluding remarks
We present two preconditioned iterative methods for the solution of initial–boundary value problems of anomalous diffusion of order in one space-dimension. We propose banded matrices as preconditioners for the discretization linear systems by exploiting the off-diagonal decay property of the coefficient matrices. Numerical results show that the proposed methods are very efficient.
We would like to make comments on related recent works and possible extension of our methods.
- 1.
In [34], a
Acknowledgements
We thank the anonymous referees for providing valuable comments and suggestions.
References (39)
Compact finite difference method for the fractional diffusion equation
J. Comput. Phys.
(2009)- et al.
The accuracy and stability of an implicit solution method for the fractional diffusion equation
J. Comput. Phys.
(2005) - et al.
Finite difference/spectral approximations for the time-fractional diffusion equation
J. Comput. Phys.
(2007) - et al.
Numerical solution of the space fractional Fokker–Planck equation
J. Comput. Appl. Math.
(2004) - et al.
Finite difference methods for two-dimensional fractional dispersion equation
J. Comput. Phys.
(2006) - et al.
Finite difference approximations for fractional advection–dispersion flow equations
J. Comput. Appl. Math.
(2004) - et al.
Finite difference approximations for two-sided space-fractional partial differential equations
Appl. Numer. Math.
(2006) Implicit finite difference approximation for time fractional diffusion equations
Comput. Math. Appl.
(2008)- et al.
Multigrid method for fractional diffusion equations
J. Comput. Phys.
(2012) - et al.
Waiting-times and returns in high-frequency financial data: An empirical study
Physica A
(2002)
Finite difference approximates for a fractional advection diffusion problem
J. Comput. Phys.
A characteristic finite difference method for transient fractional advection–diffusion equations
Appl. Numer. Math.
Finite difference approximations for the fractional advection–diffusion equation
Phys. Lett. A
A second-order accurate numerical approximation for the fractional diffusion equation
J. Comput. Phys.
A superfast-preconditioned iterative method for steady-state space-fractional diffusion equations
J. Comput. Phys.
An alternating-direction finite difference method for two-dimensional fractional diffusion equations
J. Comput. Phys.
A direct finite difference method for fractional diffusion equations
J. Comput. Phys.
A fast characteristic finite difference method for fractional advection–diffusion equations
Adv. Water Resour.
Iterative Solution Methods
Cited by (110)
A fast preconditioning iterative method for solving the discretized second-order space-fractional advection–diffusion equations
2024, Journal of Computational and Applied MathematicsA rational preconditioner for multi-dimensional Riesz fractional diffusion equations
2023, Computers and Mathematics with ApplicationsFast TTTS iteration methods for implicit Runge-Kutta temporal discretization of Riesz space fractional advection-diffusion equations
2023, Computers and Mathematics with ApplicationsFast solution methods for Riesz space fractional diffusion equations with non-separable coefficients
2023, Applied Mathematics and ComputationAn efficient multigrid method with preconditioned smoother for two-dimensional anisotropic space-fractional diffusion equations
2022, Computers and Mathematics with ApplicationsCitation Excerpt :The discretization on uniform mesh leads to a Toeplitz-like coefficient matrix [15] which brings out the design of iterative solvers for FDEs. For one-dimensional (1D) FDEs, we list some numerical methods such as the multigrid method [16], band preconditioning [17], circulant preconditioning [18], and the tridiagonal preconditioning [19]. In terms of the 2D case, we outline the splitting preconditioner presented in [20], the multigrid method employing banded-splitting smoother in [21], and the extrapolation cascadic multigrid (EXCMG) method investigated in [22].
On τ matrix-based approximate inverse preconditioning technique for diagonal-plus-Toeplitz linear systems from spatial fractional diffusion equations
2022, Journal of Computational and Applied MathematicsCitation Excerpt :People use the FDEs to provide an adequate and accurate description for these anomalous diffusion, which include modeling chaotic dynamic of classical conservation systems [5], groundwater contaminant transport [6], turbulent flow [7], applications in biology [8], finance [9], image processing [10], physics [11] and flow in human meniscus [12–14]. As closed-form analytical solutions of fractional differential equations are usually unavailable especially in the presence of variable coefficients, hence, a lot of useful numerical approximations have been developed for these fractional derivatives, see, for instance, [15–20]. Owing to the Toeplitz-like structure of the resulting discretized systems, one may consider the circulant preconditioners for solving such systems.
- ☆
The research was supported by NSF of China No. 11271238 and the Guangdong Provincial NSF under contract No. 10151503101000023 and the research grant UL020/08-Y5/MAT/JXQ01/FST from University of Macau.