# How do low rank modifications affect Krylov method convergence?

Say I have a linear system $A x = b$, which converges quickly using a suitable Krylov method (such as CG or GMRES) for all $b$. If $B$ is a matrix with low rank $r$, will the same Krylov method on the system $(A + B) x = b$ also converge quickly (ideally with an extra number of iterations that roughly depends only on $r$)?

An example of such a system would be well preconditioned membrane elasticity and bending plus unpreconditioned air pressure terms with dense outer product structure.

Note that the question is the same with or without preconditioning, since $P(A + B)Q = PAQ + PBQ$ is a rank $r$ modification of $PAQ$.

-

If your Krylov subspace is based on powers of $A$, convergence will be delayed by a number of iterations at most the rank of the correction. If it is based on powers of $A^TA$ then at most twice this number.
 Can you explain what you mean by "based on powers of $A$"? The Krylov solver is given information about $A+B$ only, not $A$ directly. – Geoffrey Irving Sep 21 '12 at 14:40 Never mind: presumably you mean powers of the matrix in question, so $A+B$ in this case. – Geoffrey Irving Sep 21 '12 at 17:16 Yes. The method has a matrix as a parameter, and this matrix is usually denoted by $A$. – Arnold Neumaier Sep 21 '12 at 18:01 Maybe for further interest you could rewrite your equation (or the solution) with some requirements on $\boldsymbol{B}$ to $\boldsymbol{x}=\left(\boldsymbol{E}+\sum_{k=1}^\infty\left(\boldsymbol{A}^{-1} \boldsymbol{B}\right)^k\right) \boldsymbol{A}^{-1} \boldsymbol{b}$ which might help if $\boldsymbol{B}$ is nilpotent or $\boldsymbol{A}^{-1}\boldsymbol{B}$ of small norm. One also recognizes the dependence on the solution of the undisturbed problem. – Bastian Ebeling Sep 26 '12 at 9:13