The cycle-convergence of restarted GMRES for normal matrices is   sublinear
  We prove that the cycle-convergence of the restarted GMRES applied to a system of linear equations with a normal coefficient matrix is sublinear. 
Eugene Vecharynski and Julien Langou