# A Survey of Low-Rank Updates of Preconditioners for Sequences of Symmetric Linear Systems
## 1 Introduction  
The solution of sequences of large and sparse linear systems \(A_{k}\mathbf{x}_{k}=\mathbf{b}_{k}\), \(k=1,\ldots\), is a problem arising in many realistic applications including time-dependent solution of Partial Differential Equations (PDEs), computation of a part of the spectrum of large matrices, solution to nonlinear systems by the Newton methods and its variants, evaluation of a matrix function on a vector, by rational Krylov methods. The large size and sparsity of the matrices involved make iterative methods as the preeminent solution methods for these systems and therefore call for robust preconditioners. Standard--full purpose--preconditioners for SPD matrices, such as the Incomplete Cholesky (IC) factorization or approximate inverses [1; 2], as well as Multigrid Methods [3] are aimed at clustering eigenvalues of the preconditioned matrices around one.  
In this paper, we will analyze a number of techniques of updating a given IC preconditioner (which we denote as \(P_{0}\) in the sequel) by a low-rank matrix with the aim of further improving this clustering. The most popular low-rank strategies are aimed at removing the smallest eigenvalues (deflation, see e.g., References [4; 5; 6; 7] for the nonsymmetric case) or at shifting them towards the middle of the spectrum. The low-rank correction is based on a (small) number of linearly independent vectors whose choice is crucial for the effectiveness of the approach. In many cases these vectors are approximations of eigenvectors corresponding to the smallest eigenvalues of the preconditioned matrix \(P_{0}\)A [8; 9].  
We will also review some techniques to efficiently approximate these vectors when incorporated within a sequence of linear systems all possibly having constant (or slightly changing) coefficient matrices. Numerical results concerning sequences arising from discretization of linear/nonlinear PDEsand iterative solution of eigenvalue problems show that the performance of a given iterative solver can be very much enhanced by the use of low-rank updates.  
The issue of updating (not necessarily by a low-rank matrix) a given preconditioner for solving sequences of linear systems has been considered by many authors, among which I would mention Reference [10; 11], in which the authors modify a given LU factorization to precondition many systems in the sequence, and the work related to the solution of sequences of _shifted linear systems_, namely systems with matrices of the form \(A_{k}=A_{0}+\alpha_{k}I\). Among the others we mention the works in Reference [12; 13] and also Reference [7] when \(A_{k}\) is nonsymmetric.  
The synopsis of the paper is as follows: In Section 2 we will discuss various low-rank updates, namely, the deflation technique, the _tuning_ strategy, described in an original fashion on the basis of a revisited _secant condition_; and the _spectral preconditioners_. In Section 3 we will be concerned with the computational complexity of the low-rank updates. Section 4 discusses the choice of the vectors which form the low-rank matrices while Section 5 will address the issue to cheaply assessing some of the leftmost eigenpairs of the coefficient matrix. In Section 6 we will give some hint on the possibility of extending these techniques to sequences of nonsymmetric linear systems. Section 7 is devoted to reporting some, partly new, numerical experiments in the framework of discretization of transient PDES and solution to eigenvalue problems. The conclusions are drawn in Section 8.  
**Notation.** Throughout the paper we use the Euclidean norm for vectors and the induced spectral norm for matrices.