these techniques result in convergence which is almost identical to exact deflation, but the cost per iteration increases significantly. In this paper, we focus only on the init-CG method.

Locally optimal restarting for eigensolvers
-------------------------------------------

We conclude this background section with a restarting technique for eigensolvers that plays a central role in the method we develop in this paper. Because the Hermitian eigenvalue problem can be considered a constrained quadratic minimization problem, many eigenvalue methods have been developed as variants of the non-linear Conjugate Gradient (NLCG) method on the Grassman manifold [@EdelmanAriasSmith]. However, it is natural to consider a method that minimizes the Rayleigh quotient on the whole space $\left\{ u^{(m-1)}, u^{(m)}, g^{(m)} \right\},$ instead of only along one search direction. By $\theta^{(m)}, u^{(m)}$ we denote the eigenvalue and eigenvector approximations at the $m$th step and $g^{(m)} = Au^{(m)} - \theta^{(m)} u^{(m)}$ the corresponding residual. The method: $$\begin{aligned}
  u^{(m+1)} & = & 
   \mbox{RayleighRitz}\left(\{ u^{(m-1)}, u^{(m)}, g^{(m)} \}\right),\ m>1,
  \label{eq:locg}\end{aligned}$$ is often called locally optimal Conjugate Gradient (LOCG) [@DYAKONOV_83; @Knyazev_91], and seems to consistently outperform other NLCG type methods. For numerical stability, the basis can be kept orthonormal, or $u^{(m)}-\tau^{(m)} u^{(m-1)}$ can be used instead of $u^{(m-1)}$, for some weight $\tau^{(m)}$. 