A fast numerical method for block lower triangular Toeplitz with dense Toeplitz blocks system with applications to time-space fractional diffusion equations

Based on the circulant-and-skew-circulant representation of Toeplitz matrix inversion and the divide-and-conquer technique, a fast numerical method is developed for solving N-by-N block lower triangular Toeplitz with M-by-M dense Toeplitz blocks system with \(\mathcal {O}(MN\log N(\log N+\log M))\) complexity and \(\mathcal {O}(NM)\) storage. Moreover, the method is employed for solving the linear system that arises from compact finite difference scheme for time-space fractional diffusion equations with significant speedup. Numerical examples are given to show the efficiency of the proposed method.