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

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

$\endgroup$
  • $\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 '12 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 '12 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 '12 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 '12 at 9:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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