TY - JOUR

T1 - A divide-and-conquer fast finite difference method for space–time fractional partial differential equation

AU - Fu, Hongfei

AU - Ng, Michael Kwok Po

AU - Wang, Hong

N1 - Funding Information:
This work was supported in part by the OSD/ARO MURI Grant W911NF-15-1-0562, by the National Science Foundation under Grants DMS-1216923 and DMS-1620194, by HKRGC ? GRF HKBU 12301214, by the National Natural Science Foundation of China under Grants 11201485, 91130010, 11471194 and 11571115, by the Fundamental Research Funds for the Central Universities under Grant 16CX02050A, and by the China Scholarship Council under Grant 201506455014. The authors would like to express their sincere thanks to the referees for their very helpful comments and suggestions, which greatly improved the quality of this paper.

PY - 2017/3/15

Y1 - 2017/3/15

N2 - Fractional partial differential equations (FPDEs) provide better modeling capabilities for challenging phenomena with long-range time memory and spatial interaction than integer-order PDEs do. A conventional numerical discretization of space–time FPDEs requires O(N2+MN) memory and O(MN3+M2N) computational work, where N is the number of spatial freedoms per time step and M is the number of time steps. We develop a fast finite difference method (FDM) for space–time FPDE: (i) We utilize the Toeplitz-like structure of the coefficient matrix to develop a matrix-free preconditioned fast Krylov subspace iterative solver to invert the coefficient matrix at each time step. (ii) We utilize a divide-and-conquer strategy, a recursive direct solver, to handle the temporal coupling of the numerical scheme. The fast method has an optimal memory requirement of O(MN) and an approximately linear computational complexity of O(NM(logN+log2M)), without resorting to any lossy compression. Numerical experiments show the utility of the method.

AB - Fractional partial differential equations (FPDEs) provide better modeling capabilities for challenging phenomena with long-range time memory and spatial interaction than integer-order PDEs do. A conventional numerical discretization of space–time FPDEs requires O(N2+MN) memory and O(MN3+M2N) computational work, where N is the number of spatial freedoms per time step and M is the number of time steps. We develop a fast finite difference method (FDM) for space–time FPDE: (i) We utilize the Toeplitz-like structure of the coefficient matrix to develop a matrix-free preconditioned fast Krylov subspace iterative solver to invert the coefficient matrix at each time step. (ii) We utilize a divide-and-conquer strategy, a recursive direct solver, to handle the temporal coupling of the numerical scheme. The fast method has an optimal memory requirement of O(MN) and an approximately linear computational complexity of O(NM(logN+log2M)), without resorting to any lossy compression. Numerical experiments show the utility of the method.

KW - Anomalous diffusion

KW - Divide-and-conquer method

KW - Finite difference method

KW - Krylov subspace iterative solver

KW - Space–time fractional partial differential equation

UR - http://www.scopus.com/inward/record.url?scp=85009250133&partnerID=8YFLogxK

U2 - 10.1016/j.camwa.2016.11.023

DO - 10.1016/j.camwa.2016.11.023

M3 - Article

AN - SCOPUS:85009250133

VL - 73

SP - 1233

EP - 1242

JO - Computers and Mathematics with Applications

JF - Computers and Mathematics with Applications

SN - 0898-1221

IS - 6

ER -