A direct O(N log2 N) finite difference method for fractional diffusion equations

Fractional diffusion equations model phenomena exhibiting anomalous diffusion that can not be modeled accurately by the second-order diffusion equations. Because of the nonlocal property of fractional differential operators, the numerical methods have full coefficient matrices which require storage of O(N2) and computational cost of O(N3) where N is the number of grid points.In this paper we develop a fast finite difference method for fractional diffusion equations, which only requires storage of O(N) and computational cost of O(N log2 N) while retaining the same accuracy and approximation property as the regular finite difference method. Numerical experiments are presented to show the utility of the method.