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 - Journal article
AN - SCOPUS:85009250133
SN - 0898-1221
VL - 73
SP - 1233
EP - 1242
JO - Computers and Mathematics with Applications
JF - Computers and Mathematics with Applications
IS - 6
ER -