# A Survey of Low-Rank Updates of Preconditioners for Sequences of Symmetric Linear Systems
## 2 Low-Rank Updates
### Tuning  
The adjective _tuned_ associated with a preconditioner was introduced in Reference [18] in the framework of iterative eigensolvers. In our context we redefine it in the following way:  
**Definition 1**. : _Given a preconditioner \(P_{0}\) and a vector \(\mathbf{w}\), a tuned preconditioner for matrix \(A\) is a matrix \(P\equiv M^{-1}\) obtained by correcting \(P_{0}\) by a rank one or rank two matrix depending on \(A\) and \(\mathbf{w}\) and satisfying_  
\[PA\mathbf{w}=\mathbf{w}\qquad(M\mathbf{w}=A\mathbf{w}). \tag{2}\]  
In this way matrix \(M\) agrees with \(A\) in the direction \(\mathbf{w}\) and also the preconditioned matrix has the eigenvalue \(1\) corresponding to the eigenvector \(\mathbf{w}\). This definition can be easily extended to multiple vectors:  
**Definition 2**. : _Given a preconditioner \(P_{0}\) and an \(n\times p\) matrix \(W\) with full column rank, a block tuned preconditioner for matrix \(A\) is a matrix \(P\) obtained by correcting \(P_{0}\) by a low-rank matrix depending on \(A\) and \(W\) and satisfying_  
\[PAW=W.\]In Reference [19], the following single-vector tuned preconditioned for SPD linear systems was proposed (here \(M_{0}=LL^{T}\approx A\) and \(P=M^{-1}\) is computed by the Sherman-Morrison formula). \[\mathbf{u}=(A-M_{0})\mathbf{w} \mathbf{z}=P_{0}\mathbf{u}=P_{0}A\mathbf{w}-\mathbf{w} \tag{4}\] \[M=M_{0}+\frac{\mathbf{u}\mathbf{u}^{T}}{\mathbf{u}^{T}\mathbf{w} }P=P_{0}-\frac{\mathbf{z}\mathbf{z}^{T}}{\mathbf{z}^{T}A\mathbf{w}} \tag{5}\]  
It is easily checked that \(PA\mathbf{w}=P_{0}A\mathbf{w}-\mathbf{z}=\mathbf{w}\). Digression  
This tuned preconditioner, as many others, has however an older derivation. Let us now consider the solution of a nonlinear system of equations  
\[\mathbf{F}(\mathbf{x})=0,\qquad\mathbf{F}:\mathbb{R}^{n}\to\mathbb{R}^{n}\]  
by the Newton method  
\[F^{\prime}(\mathbf{x}_{k})\mathbf{s}_{k} = -\mathbf{F}(\mathbf{x}_{k}) \tag{6}\] \[\mathbf{x}_{k+1} = \mathbf{x}_{k}+\mathbf{s}_{k}.\]  
Quasi-Newton methods construct a sequence of approximations of the Jacobians \(B_{k}\approx F^{\prime}(\mathbf{x}_{k})\). Each \(B_{k}\) is defined by a low-rank update of the previous matrix in the sequence \(B_{k-1}\). Such sequences are also used to correct a given initial preconditioner to accelerate the iterative solution of systems like (6) [20; 21; 22; 23; 24]. Among those Quasi-Newton methods we recall three of the most commonly used one (note that \(\mathbf{y}_{k}=\mathbf{F}(\mathbf{x}_{k+1})-\mathbf{F}(\mathbf{x}_{k})\)):  
\[\text{Broyden's method: }B_{k+1}=B_{k}+\frac{(\mathbf{y}_{k}-B_{k} \mathbf{s}_{k})\mathbf{s}_{k}^{T}}{\mathbf{s}_{k}^{T}\mathbf{s}_{k}}\] \[\text{SR1 (Symmetric Rank-1): }B_{k+1}=B_{k}+\frac{(\mathbf{y}_{k}-B_{k} \mathbf{s}_{k})(\mathbf{y}_{k}-B_{k}\mathbf{s}_{k})^{T}}{(\mathbf{y}_{k}-B_{k} \mathbf{s}_{k})^{T}\mathbf{s}_{k}}\]  
BFGS (Named after [PERSON], [PERSON], [PERSON] and [PERSON], who all discovered the same formula independently in 1970, by different approaches) update: \(B_{k+1}=B_{k}+\frac{\mathbf{y}_{k}\mathbf{y}_{k}^{T}}{\mathbf{y}_{k}^{T} \mathbf{s}_{k}}-\frac{B_{k}\mathbf{s}_{k}\mathbf{s}_{k}^{T}B_{k}}{\mathbf{s}_ {k}^{T}B_{k}\mathbf{s}_{k}}\). All these updates satisfy the so called _secant condition_ which reads  
\[B_{k+1}\mathbf{s}_{k}=\mathbf{y}_{k}. \tag{7}\]  
The first update is nonsymmetric, the SR1 and BFGS formulae define a symmetric sequence provided \(B_{0}\) is so. Consider now the problem of updating a given preconditioner \(P_{0}=M_{0}^{-1}\). We can use all the preceding equations after employing the following substitutions:  
\[PAW=W.\]0  
which transform the secant condition into  
\[PAW=W.\]1  
that is the _tuning property_. We can then develop three different tuning strategies. For each of them, in Tables 1-3, we write the \"direct\" formula (with \(M,M_{0}\)) the inverse representation (with \(P,P_{0}\)), by the Shermann-Morrison inversion formula, and develop the corresponding inverse block formula.