2
$\begingroup$

I have coded up a toy implementation of Conjugate Residual and have been testing it. Both wikipedia and the Saad claim that Conjugate Residual and Conjugate Gradient have similar convergence behavior. For some examples I have been doing I haven't found this to be true. For a $128 \times 128$ symmetric indefinite matrix, I don't get (machine) convergence at 400 iterations. This is at odds with my understanding of Conjugate residual being a Krylov space method that should converge in at most 128 iterations. (The condition number of this matrix is about 120 and every singular value is repeated since the eigenvalues come in positive and negative pairs.)

I am guessing the statement about similar convergence properties refers to the performance on symmetric positive definite matrices, and numerical experiments are consistent with this.

So my question is, what determines the convergence rate of conjugate residual for a symmetric but indefinite matrix? Also, is the conjugate residual method supposed to converge in at most $n$ iterations, where $n$ is the size of the system?

|cite|improve this question
$\endgroup$
  • 1
    $\begingroup$ My guess would be that whenever someone compares two methods they implicitly refer to situations in which applying both methods is meaningful. Since CG cannot guarantee to find a meaningful solution for indefinite cases, they probably refer only to the positive definite case with this remark. Is there a theoretical result that states the guaranteed convergence of the conjugate residual method for anything else than spd? $\endgroup$ – Christian Waluga Oct 28 '15 at 20:20
  • 1
    $\begingroup$ It is my (probably faulty) understanding that the $i$'th iterate of the CR algorithm is the vector in the $i$'th Krylov subspace that minimizes the residual with respect to a certain inner product. Now, if $A\in \mathbb{R}^{n\times n}$, the $n$'th Krylov space should span all of $\mathbb{R}^n$ so we should have an exact solution by then. $\endgroup$ – fred Oct 28 '15 at 21:32
  • $\begingroup$ Does "indefinite" mean anything specific like "positive semi-definite" or just "no known property at all" ? $\endgroup$ – shuhalo Apr 5 '17 at 15:14

Your Answer

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

Browse other questions tagged or ask your own question.