# A Survey of Low-Rank Updates of Preconditioners for Sequences of Symmetric Linear Systems
## 2 Low-Rank Updates  
### Deflation  
The idea to use deflation to accelerate the Conjugate Gradient (CG) method goes back to the middle of the 1980s. The most cited article on this subject is a paper by [PERSON] [4] who developed a deflated Conjugate Gradient method based on a three-term recurrence. Other similar formulations are presented in Reference [14; 15]. Some years later in Reference [6] a deflated Generalized Minimal Residual (GMRES) method was proposed by using an augmented basis. Rigorous bounds on the eigenvalues of the deflated-preconditioned matrices are given in Reference [16]. We finally mention a recent interesting survey on deflation methods in Reference [17].  
We will follow here the formulation of the Deflated-CG algorithm developed in Reference [5]. Given a full column rank \(n\times p\) matrix \(W=\begin{bmatrix}\mathbf{w}_{1}&\ldots&\mathbf{w}_{p}\end{bmatrix}\) the \(A\)-orthogonal projector \(H\) is defined as  
\[H=I-W(W^{T}AW)^{-1}W^{T}A, \tag{1}\]  
which maintains the CG residuals orthogonal to the subspace spanned by \(\{\mathbf{w}_{1},\ldots,\mathbf{w}_{p}\}\), provided that also \(\mathbf{r}_{0}\) satisfies \(W^{T}\mathbf{r}_{0}=0\). The Deflated-CG algorithm is described in Algorithm 1.  
Note that this algorithm is mathematically equivalent to the PCG method with preconditioner \(P=HP_{0}H^{T}\) since  
\[\mathbf{r}_{k}^{T}\mathbf{z}_{k}=\mathbf{r}_{k}^{T}P_{0}\mathbf{r}_{k}= \mathbf{r}_{k}^{T}HP_{0}H^{T}\mathbf{r}_{k},\]  
being \(W^{T}\mathbf{r}_{k}=0\) and therefore \(H^{T}\mathbf{r}_{k}=\mathbf{r}_{k}\). \(P\) is only symmetric positive semidefinite, however PCG could not breakdown as stated in the following result ([5], Theorem 4.2).  
```
Choose an \(n\times p\) full column rank matrix \(W\). Compute \(\Pi=W^{T}AW\). Choose \(\tilde{\mathbf{x}}_{0}\); Set \(\mathbf{r}_{0}=\mathbf{b}-A\mathbf{x}_{0}\) and \(\mathbf{x}_{0}=\tilde{\mathbf{x}}_{0}+W\Pi^{-1}W^{T}\mathbf{r}_{0}\). Compute \(\mathbf{z}_{0}=P_{0}\mathbf{r}_{0}\); Set \(k=0\), \(\mathbf{p}_{0}=\mathbf{z}_{0}-W\Pi^{-1}W^{T}A\mathbf{z}_{0}\) \(\rho_{0}=\mathbf{r}_{0}^{T}\mathbf{z}_{0}\) repeat until convergence \(\alpha_{k}=\frac{\rho_{k}}{\mathbf{p}_{k}^{T}A\mathbf{p}_{k}}\) \(\mathbf{x}_{k+1}=\mathbf{x}_{k}+\alpha_{k}\mathbf{p}_{k}\) \(k=k+1\) \(\mathbf{z}_{k}=P_{0}\mathbf{r}_{k}\) \(\rho_{k}=\mathbf{r}_{k}^{T}\mathbf{z}_{k}\) \(\beta_{k}=\frac{\rho_{k}}{\rho_{k-1}}\) \(\mathbf{p}_{k+1}=\beta_{k}\mathbf{p}_{k}+\mathbf{z}_{k}-W\Pi^{-1}W^{T}A \mathbf{z}_{k}\) end repeat.
```  
**Algorithm 1** Deflated CG.  
**Theorem 1**.: _Let \(A\) be an SPD matrix and \(W\) an \(n\times p\) matrix with full column rank. The Deflated-CG algorithm applied to the linear system \(A\mathbf{x}=\mathbf{b}\) will not break down at any step. The approximate solution \(\mathbf{x}^{(k)}\) is the unique minimizer of \(\|\mathbf{x}^{(k)}-\mathbf{x}^{(*)}\|_{A}\) over the affine space \(\mathbf{x}_{0}+\text{span}(W,\mathcal{K}_{k}(\mathbf{r}_{0}))\)._  
The action of this deflated preconditioner is to put some of the eigenvalues of the preconditioner matrix to zero in fact:  
\[PAW=HP_{0}H^{T}AW=0,\]  
that is, all \(p\) columns of \(W\) are eigenvectors of \(PA\) corresponding to the zero eigenvalue. Deflated CG guarantees that (at least in infinite precision arithmetic) all residuals satisfy \(W^{T}\mathbf{r}_{k}=0\). If the columns of \(W\) are (approximate) eigenvectors of \(P_{0}A\) corresponding to the smallest eigenvalues, then these eigenvalues are removed from the spectrum of \(PA\) with obvious decrease of the condition number.