# A Survey of Low-Rank Updates of Preconditioners for Sequences of Symmetric Linear Systems
## 5 Cost-Free Approximation of the Leftmost Eigenpairs
### The Lanczos-PCG Connection  
A simple way to recover some of the extremal eigenpairs of the preconditioned matrix is to exploit the so called _Lanczos connection_[36; 37]. During the PCG method, preconditioned with \(P_{0}\), it is possible to save the first \(m\) (scaled) preconditioned residuals as columns of a matrix \(V_{m}\):  
\[V_{m}=\left[\frac{P_{0}\mathbf{r}_{0}}{\sqrt{\mathbf{r}_{0}^{T}P_{0}\mathbf{r }_{0}}},\frac{P_{0}\mathbf{r}_{1}}{\sqrt{\mathbf{r}_{1}^{T}P_{0}\mathbf{r}_{ 1}}},\ldots,\frac{P_{0}\mathbf{r}_{m-1}}{\sqrt{\mathbf{r}_{m-1}^{T}P_{0} \mathbf{r}_{m-1}}}\right].\]  
Matrix \(V_{m}\) is such that \(V_{m}^{T}P_{0}^{-1}V_{m}=I_{m}\), in view of the \(P_{0}-\)orthogonality of the residuals generated by the PCG method. The Lanczos tridiagonal matrix can be formed using the PCG coefficients \(\alpha_{k}\), \(\beta_{k}\)  
Figure 2: Number of iterations to solve each linear system in the sequence by MINRES with: no update, BFGS update with previous solutions, spectral update with previous solutions, BFGS update with leftmost eigenvectors. On the right also the CPU time is reported.  
\[T_{m}=\begin{bmatrix}\dfrac{1}{\alpha_{0}}&-\dfrac{\sqrt{\beta_{1}}}{\alpha_{0}}\\ -\dfrac{\sqrt{\beta_{1}}}{\alpha_{0}}&\dfrac{1}{\alpha_{1}}+\dfrac{\beta_{1}}{ \alpha_{0}}&-\dfrac{\sqrt{\beta_{2}}}{\alpha_{1}}\\ &\ddots\\ &&&-\dfrac{\sqrt{\beta_{m-1}}}{\alpha_{m-2}}\\ &-\dfrac{\sqrt{\beta_{m-1}}}{\alpha_{m-2}}&\dfrac{1}{\alpha_{m-1}}+\dfrac{ \beta_{m-1}}{\alpha_{m-2}}\end{bmatrix}\]  
Matrices \(V_{m}\) and \(T_{m}\) obey to the classical Lanczos relation that is:  
\[V_{m}^{T}AV_{m}=T_{m}.\]  
The eigensolution of \(T_{m}\) provides the eigendecomposition \(T_{m}\Lambda_{m}=\Lambda_{m}Q_{m}\). Then, the eigenvectors corresponding to the \(p\) smallest eigenvalues are selected as \(p\) columns of matrix \(Q_{p}\). Finally, the columns of \(W_{p}=V_{m}Q_{p}\) are expected to approximate the \(p\) leftmost eigenvectors of \(P_{0}A\).  
This procedure can be implemented to a very little computational cost but it has a number of disadvantages: First, it requires the storage of \(m\) preconditioned residuals, Second, as the convergence for the Lanczos process to the smallest eigenvalues is relatively slow, it sometimes happens that PCG convergence takes place before eigenvector convergence. Third, some of the leftmost eigenpairs can be missing by the non-restarted Lanczos procedure.  
To partially overcome these drawbacks in Reference [38] the authors suggest implementing a thick restart within the PCG iteration (without affecting it) and incrementally correct the eigenvector approximations during subsequent linear system solvers. The final set of directions is, in that paper, used only to deflate the initial vector and not to form a preconditioner (eigCG algorithm) in the solution of a sequence of hundreds of linear systems in lattice quantum chromodynamics.  
A number of alternative ways to approximate eigenvectors during the PCG iteration can be found in the literature. In Reference [5], a technique is suggested to refine them during subsequent linear systems with the same matrix but different right-hand-sides by using the \(p\) smallest harmonic Ritz values. In this approach the vector stored within the PCG iteration are the conjugate directions \(\mathbf{p}_{k}\) instead of the preconditioned residuals (they actually lie in the same Krylov subspace).