A divide-and-conquer fast finite difference method for space–time fractional partial differential equation. (15th March 2017) - Fu, Hongfei
Abstract: 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 ( N 2 + M N ) memory and O ( M N 3 + M 2 N ) 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 ( M N ) and an approximately linear computational complexity of O ( N M ( log N + log 2 M ) ), without resorting to any lossy compression. Numerical experiments show the utility of the method.