Tell me more ×
Computational Science Stack Exchange is a question and answer site for scientists using computers to solve scientific problems. It's 100% free, no registration required.
up vote 10 down vote favorite
2

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

share|improve this question

1 Answer

up vote 4 down vote accepted

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.

share|improve this answer
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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