  In the paper, we present a high order fast algorithm with almost optimum
memory for the Caputo fractional derivative, which can be expressed as a
convolution of $u'(t)$ with the kernel $(t_n-t)^{-\alpha}$. In the fast
algorithm, the interval $[0,t_{n-1}]$ is split into nonuniform subintervals.
The number of the subintervals is in the order of $\log n$ at the $n$-th time
step. The fractional kernel function is approximated by a polynomial function
of $K$-th degree with a uniform absolute error on each subinterval. We save
$K+1$ integrals on each subinterval, which can be written as a convolution of
$u'(t)$ with a polynomial base function. As compared with the direct method,
the proposed fast algorithm reduces the storage requirement and computational
cost from $O(n)$ to $O((K+1)\log n)$ at the $n$-th time step. We prove that the
convergence rate of the fast algorithm is the same as the direct method even a
high order direct method is considered. The convergence rate and efficiency of
the fast algorithm are illustrated via several numerical examples.
