A fast O(N log N) second-order numerical method for space-fractional diffusion equations

Treena Basu and Gregory Capra – GJM, Volume 3, Issue 2 (2018), 98-107.

Fractional diffusion equations have been proven to accurately model anomalous diffusion processes in nature. However, numerical schemes applied to space-fractional diffusion equations result in dense or full coefficient matrices with computational complexity and storage capacity of O(N^3) per time step and O(N^2) respectively, which is increasingly problematic for larger N. This paper seeks to provide a more efficient and robust algorithm for numerically approximating a second-order accurate numerical solution to the discretized one-dimensional two-sided space-fractional diffusion equation that requires only O(N\log N) computational work per time step and O(N) memory by utilizing the Crank-Nicolson scheme and studying the structure of the resulting coefficient matrix. A fast iterative scheme is used to solve the resulting system of equations. Numerical results are shown to illustrate the second-order accuracy and efficiency of the new method.


Received: July 27, 2018.
Published online: October 21, 2018.


Treena Basu
1600 Campus Road, Department of Mathematics, Occidental College, Los Angeles, CA 90041, USA.
Gregory Capra
1908 California Street, Apt 10, Berkeley, CA 94703, USA.


Print Version