  In this paper, we investigate a spectral Petrov-Galerkin method for
fractional initial value problems. Singularities of the solution at the origin
inherited from the weakly singular kernel of the fractional derivative are
considered, and the regularity is constructed for the solution in weighted
Sobolev space. We present an optimal error estimate of the spectral
Petrov-Galerkin method, and prove that the convergence order of the method in
the weighted $L^2$-norm is $3\alpha+1$ for smooth source term, where $\alpha$
is the order of the fractional derivative.
  An iteration algorithm with a quasi-linear complexity is considered to solve
the produced linear system. Numerical experiments verify the theoretical
findings and show the efficiency of the proposed algorithm, and exhibit that
the presented numerical method works well for some time-fractional diffusion
equations after suitable temporal semi-discrete.
