# A Survey of Low-Rank Updates of Preconditioners for Sequences of Symmetric Linear Systems
## 4 Choice of the Vectors \(\{\mathbf{w}_{j}\}\)
#### Using Previous Solution Vectors  
Computing a subset of the extremal eigenvectors of a given large and sparse matrix may reveal computationally costly. In the next Section we will develop some methods to save on this cost. However another possibility for the vectors \(\mathbf{w}_{j}\) is to use a number of the solutions to the previous linear systems in the sequence. Assume now that the matrices in the sequence are allowed to (slightly) change, that is, we want to solve  
\[A_{k}\mathbf{x}_{k}=\mathbf{b}_{k},\qquad k=1,\ldots,N.\]  
In this case computing the leftmost eigenvectors of \(A_{k}\) is inefficient since this preprocessing should be done at each linear system.  
We then use, for the \(j\)th linear system (\(1<j\leq N\)), the \(j_{eff}=\min\{j-1,p\}\) solutions to the previous linear systems as columns of \(W\equiv W_{j}\), thus yielding:  
\[W_{j}=\left[\mathbf{x}_{j-j_{eff}}\quad\ldots\quad\mathbf{x}_{j-1}\right]. \tag{11}\]  
The idea beyond this choice, which is completely cost-free, comes from the reasoning that:  
1. A solution \(\mathbf{x}_{k}\) of the \(k\)-th linear system has with high probability non-negligible components in the directions of the leftmost eigenvectors of \(A_{k}\) since, if \(\mathbf{b}_{k}=\sum\limits_{i=1}^{n}\alpha_{i}\mathbf{u}_{i}^{(k)}\), then \(\mathbf{x}_{k}=\sum\limits_{i=1}^{n}\dfrac{\alpha_{i}}{\lambda_{i}^{(k)}} \mathbf{u}_{i}^{(k)}\), with the largest weights provided by the smallest eigenvalues.
2. The leftmost eigenvector of \(A_{k},k=j_{eff},\ldots j-1\) are good approximation of the leftmost eigenvectors of \(A_{j}\).  
To give experimental evidence of the efficiency of this approach we report some results in solving a sequence of 30 linear systems arising from the Finite Element/Backward Euler discretization of the branched transport equation [35] which gives raise to a sequence of \((2\times 2)\) block nonlinear systems in turn solved by the Inexact Newton method. After linearization and block Gaussian Elimination the problem reduces to the solution of a sequences of symmetric linear systems of the form  
\[(A+B^{T}EB)_{k}\mathbf{x}=\mathbf{b}_{k},\quad k=1,\ldots,\]  
where \(A\) is SPD, \(B\) is rectangular with full row rank, \(E\) is diagonal and possibly indefinite. We take 30 consecutive linear systems from this sequence, and solve them with the minimum residual (MINRES)  
Figure 1: Eigenvalues and angle between eigenvectors of \(A\) and IC-preconditioned \(A\).  
iterative method using as the initial preconditioner the incomplete Cholesky factorization of \(A\) with drop tolerance \(10^{-2}\) and the following updates  
1. BFGS, with update directions as in (11).
2. Spectral preconditioner, with update directions as in (11).
3. BFGS, with the accurate leftmost eigenvectors of \(A_{k}\) as the update directions.  
The results are reported in Figure 2 where we can appreciate reduction of the number of iterations provided by the low-rank update. The (cheaper) spectral preconditioner provides as good acceleration as the BFGS approach with update directions as in (11). Moreover the number of iterations is comparable to those obtained with the \"ideal\" eigenvectors (which are obtained by the Matlab eigs function).