Fast solvers for finite difference scheme of two-dimensional time-space fractional differential equations

Generally, solving linear systems from finite difference alternating direction implicit scheme of two-dimensional time-space fractional differential equations with Gaussian elimination requires $\mathcal {O}\left ({NM}_{1}M_{2}\left ({M_{1}^{2}}+{M_{2}^{2}}+NM_{1}M_{2}\right )\right )$ complexity and $\mathcal {O}\left ({N{M_{1}^{2}}{M_{2}^{2}}}\right )$ storage, where N is the number of temporal unknown and M1, M2 are the numbers of spatial unknown in x, y directions respectively. By exploring the structure of the coefficient matrix in fully coupled form, it possesses block lower-triangular Toeplitz structure and its blocks are block-dense Toeplitz matrices with dense-Toeplitz blocks. Based on this special structure and cooperating with time-marching or divide-and-conquer technique, two fast solvers with storage $\mathcal {O}\left ({NM}_{1}M_{2}\right )$ are developed. The complexity for the fast solver via time-marching is $\mathcal {O}\left ({NM}_{1}M_{2}\left (N+\log \left (M_{1}M_{2}\right )\right )\right )$ and the one via divide-and-conquer technique is $\mathcal {O}\left ({NM}_{1}M_{2}\left (\log ^{2} N+ \log \left (M_{1}M_{2}\right )\right )\right )$. It is worth to remark that the proposed solvers are not lossy. Some discussions on achieving convergence rate for smooth and non-smooth solutions are given. Numerical results show the high efficiency of the proposed fast solvers.