Improving algebraic updates of preconditioners Co-authored by:

We consider the solution of sequences of linear systems A(i)x = b(i), i = 1,..., where A(i) ∈ Rn×n are general nonsingular sparse matrices and b(i) ∈ Rn are corresponding right-hand sides. Such sequences arise in many applications. For example, a system of nonlinear equations F (x) = 0 for F: IRn → IRn solved by a Newton or Broyden-type method leads to a sequence of problems J(xi)(xi+1 − xi) = −F (xi), i = 1,..., where J(xi) is the Jacobian evaluated in the current iteration xi or its approximation. The solution of such sequences of linear systems is often one of the main bottlenecks in appli-cations. Preconditioned iterative Krylov subspace solvers are often methods of choice when the systems are large. Computing preconditioners for individual systems separately may be rather expensive in many practical situations, in particular in matrix-free or parallel computational environment. In recent years, a few attempts to update preconditioners for sequences of large and sparse systems have been made. In particular, straightforward approximations by updates of small rank were presented in [2] and [8]. Sequences of shifted SPD linear systems were studied in [1] and [7]; see also extensions for complex symmetric linear systems [3]. Our contribution is targeted to improvements of techniques for algebraic updates of general nonsymmetric preconditioners in the form of LDU decomposition. The basic approach from [5] and its improvements will be described. In particular, we will cover both more efficient implementation of the basic triangular updates from [5] and their extension. Our experiments demonstrate that the general updates can be used in a black-box fashion