# A Survey of Low-Rank Updates of Preconditioners for Sequences of Symmetric Linear Systems
## 2 Low-Rank Updates
### Tuning
The Broyden tuning strategy must be used for nonsymmetric problems, the BFGS formula is well suited to accelerate the PCG method due to the following result:  
Theorem 2: _The preconditioner \(P\) yielded by the BFGS update formula is SPD provided \(P_{0}\) is so._  
Proof: For every nonzero \(\mathbf{x}\in\mathbb{R}^{n}\) we set \(\mathbf{z}=H^{T}\mathbf{x}\) and \(\mathbf{u}=W^{T}\mathbf{x}\). Then we have  
\[PAW=W.\]2  
the last inequality holding since both \(\Pi^{-1}\) and \(P_{0}\) are SPD matrices. The inequality is strict since if \(\mathbf{u}=0\) then \(W^{T}\mathbf{x}=0\) and hence \(\mathbf{z}=(I-AW\Pi^{-1}W^{T})\mathbf{x}=\mathbf{x}\
eq 0\). Finally, the SR1 update provides clearly symmetric matrices, upon symmetry of \(P_{0}\). If in addition \(P_{0}\) is SPD the new update \(P\) is also likely to be SPD as well, depending on the quality of the initial preconditioner \(P_{0}\), as stated in the following result ([PERSON] and [PERSON], 2016) (Section 3.2). \[PAW=W.\]3  
which has however a modest practical use as \(\|(W^{T}AW)^{-1}\|\) may be large. Whenever the columns of \(W\) approximate the smallest eigenvalues of \(P_{0}A\) something more can be said. Assume that \(P_{0}AW=W\Theta\), with \(\Theta=\text{diag}\left(\mu_{1},\ldots,\mu_{p}\right)\) the diagonal matrix with the eigenvalues of the initially preconditioned matrix. Assume further that \(\mu_{j}<1,j=1,\ldots,p\). Since \(P_{0}A\) is not symmetric but \(P_{0}^{1/2}AP_{0}^{1/2}\) is so it follows that \(W\) must satisfy \(W^{T}P_{0}^{-1}W=I\) and hence \(W^{T}AW=\Theta\). In such a case we have that matrix  
\[PAW=W.\]4  
is obviously SPD and therefore so is \(P\) which is the sum of an SPD matrix (\(P_{0}\)) and a symmetric positive semidefinite matrix \((-Z(Z^{T}AW)^{-1}Z^{T})\). \begin{table}
\begin{tabular}{l c c} \hline \hline direct & \(M=M_{0}+\dfrac{(A-M_{0})\mathbf{w}\mathbf{w}^{T}}{\mathbf{w}^{T}\mathbf{w}}\) & \(M\mathbf{w}=A\mathbf{w}\) \\ \hline inverse & \(P=P_{0}-\dfrac{(P_{0}A\mathbf{w}-\mathbf{w})\mathbf{w}^{T}P_{0}}{\mathbf{w}^{T} P_{0}A\mathbf{w}}\) & \(PA\mathbf{w}=\mathbf{w}\) \\ block & \(P=P_{0}-\left(P_{0}AW-W\right)\left(W^{T}P_{0}AW\right)^{-1}W^{T}P_{0}\) & \(PAW=W\) \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Direct, inverse and block versions of the Broyden (nonsymmetric) update. \begin{table}
\begin{tabular}{l c c} \hline \hline direct & \(M=M_{0}+\dfrac{(A-M_{0})\mathbf{w}\mathbf{w}^{T}}{\mathbf{w}^{T}\mathbf{u}}\), & \(\mathbf{u}=(A-M_{0})\mathbf{w}\) \\ \hline inverse & \(P=P_{0}-\dfrac{\mathbf{z}\mathbf{z}^{T}}{\mathbf{z}^{T}A\mathbf{w}}\), & \(\mathbf{z}=P_{0}A\mathbf{w}-\mathbf{w}\) \\ block & \(P=P_{0}-Z\left(Z^{T}AW\rightThe Broyden tuned preconditioner was used in Reference [26] to accelerate the GMRES for the inner linear systems within the Arnoldi method for eigenvalue computation. The SR1 preconditioner appeared in References [19; 25] and also in Reference [27]. This low-rank update has also been employed to accelerate the PCG method in the solution of linear systems involving SPD Jacobian matrices. In Reference [28] some conditions are proved under which the SR1 update maintains the symmetric positive definiteness of a given initial preconditioner. The BFGS preconditioner was used (under the name of _balancing preconditioner_) in Reference [29], in Reference[30] for eigenvalue computation and also in Reference [31] to update the Constraint Preconditioner for sequences of KKT linear systems. It has been successfully employed (under the name of limited memory preconditioner) to accelerate sequences of symmetric indefinite linear systems in Reference [32]. We finally mention the work in Reference [33], where the author used this correction to update an Inexact Constraint Preconditioner, by damping the largest eigenvalues of the preconditioned matrices.