  In this paper, we develop fast procedures for solving linear systems arising
from discretization of ordinary and partial differential equations with Caputo
fractional derivative w.r.t time variable. First, we consider a finite
difference scheme to solve a two-sided fractional ordinary equation.
Furthermore, we present a fast solution technique to accelerate Toeplitz
matrix-vector multiplications arising from finite difference discretization.
This fast solution technique is based on a fast Fourier transform and depends
on the special structure of coefficient matrices, and it helps to reduce the
computational work from $O(N^{3})$ required by traditional methods to
$O(Nlog^{2}N)$ and the memory requirement from $O(N^{2})$ to $O(N)$ without
using any lossy compression, where $N$ is the number of unknowns. Two finite
difference schemes to solve time fractional hyperbolic equations with different
fractional order $\gamma$ are considered. We present a fast solution technique
depending on the special structure of coefficient matrices by rearranging the
order of unknowns. It helps to reduce the computational work from $O(N^2M)$
required by traditional methods to $O(N$log$^{2}N)$ and the memory requirement
from $O(NM)$ to $O(N)$ without using any lossy compression, where $N=\tau^{-1}$
and $\tau$ is the size of time step, $M=h^{-1}$ and $h$ is the size of space
step. Importantly, a fast method is employed to solve the classical time
fractional diffusion equation with a lower coast at $O(MN$log$^2N)$, where the
direct method requires an overall computational complexity of $O(N^2M)$.
Moreover, the applicability and accuracy of the scheme are demonstrated by
numerical experiments to support our theoretical analysis.
