15
$\begingroup$

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$.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
7
$\begingroup$

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.

I haven't seen such a statement in the literature. But to see the validity in the first case, it is sufficient to show that the $k$th Krylov space of the matrix $A+USV^T$ where $U,V$ have $r$ columns is contained in the corresponding space without low rank corrections but with a correspondingly higher index $k+r$. This is straightforward to verify.

Improve this answer
$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$
    – Geoffrey Irving
    Sep 21, 2012 at 14:40
  • $\begingroup$ Never mind: presumably you mean powers of the matrix in question, so $A+B$ in this case. $\endgroup$
    – Geoffrey Irving
    Sep 21, 2012 at 17:16
  • $\begingroup$ Yes. The method has a matrix as a parameter, and this matrix is usually denoted by $A$. $\endgroup$
    – Arnold Neumaier
    Sep 21, 2012 at 18:01
  • $\begingroup$ 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. $\endgroup$
    – Bastian Ebeling
    Sep 26, 2012 at 9:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.