Fast alternating-direction finite difference methods for three-dimensional space-fractional diffusion equations

Fractional diffusion equations model phenomena exhibiting anomalous diffusion that cannot be modeled accurately by second-order diffusion equations. Because of the nonlocal property of fractional differential operators, numerical methods for space-fractional diffusion equations generate dense or even full coefficient matrices with complicated structures. Traditionally, these methods were solved via Gaussian elimination, which requires computational work of O(N3) per time step and O(N2) of memory to store where N is the number of spatial grid points in the discretization. The significant computational work and memory requirement of these methods makes a numerical simulation of three-dimensional space-fractional diffusion equations computationally prohibitively expensive. We present an alternating-direction implicit (ADI) finite difference formulation for space-fractional diffusion equations in three space dimensions and prove its unconditional stability and convergence rate provided that the fractional partial difference operators along x-, y-, z-directions commute. We base on the ADI formulation to develop a fast iterative ADI finite difference method, which has a computational work count of O(NlogN) per iteration at each time step and a memory requirement of O(N). We also develop a fast multistep ADI finite difference method, which has a computational work count of O(Nlog2N) per time step and a memory requirement of O(NlogN). Numerical experiments of a three-dimensional space-fractional diffusion equation show that these both fast methods retain the same accuracy as the regular three-dimensional implicit finite difference method, but have significantly improved computational cost and memory requirement. These numerical experiments show the utility of the fast method.