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

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.