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.

Milestones:

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

Authors:

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.

Download:

Print Version