Summary: A fast algorithm with almost optimal memory for the computation of Caputo's fractional derivative is developed. It is based on a nonuniform splitting of the time interval \([0, t_n]\) and a polynomial approximation of the kernel function \((1 - \tau)^{-\alpha}\). Both the storage requirements and the computational cost are reduced from \(\mathscr O (n)\) to \((K + 1) \mathscr O (\log n)\) with \(K\) being the degree of the approximated polynomial. The algorithm is applied to linear and nonlinear fractional diffusion equations. Numerical results show that this scheme and the corresponding direct methods have the same order of convergence but the method proposed performs better in terms of computational time.