3
$\begingroup$

I would greatly appreciate it if you could share some reasons the Conjugate Gradient iteration for Ax = b does not converge? My matrix A is symmetric positive definite.

Thank you so much!

Edit with more information: My matrix is the reduced Hessian in the optimization algorithms for problems with simple constraints. The matrix is 50% sparse and I am using matlab.

$\endgroup$
  • $\begingroup$ Can you provide any extra information? What is the structure of your matrix, is it dense or sparse? Where the matrix come from, is from FEM, FDM? Which programming language are you using? $\endgroup$ – nicoguaro Aug 12 '14 at 23:06
  • 1
    $\begingroup$ Thanks. I edited my question. Let me know if I need to provide more information. $\endgroup$ – coding Aug 12 '14 at 23:25
  • $\begingroup$ What's the condition number of your matrix? $\endgroup$ – Brian Borchers Aug 13 '14 at 2:24
  • $\begingroup$ And how do you know the matrix is in fact spd (as opposed to "should be spd")? Is it explicitly given, or are you using a matrix-free CG (i.e., you have a procedure to compute $Ax$ for given $x$)? And finally, what do you mean by "does not converge"? Are you sure it's not just converging (very) slowly? $\endgroup$ – Christian Clason Aug 13 '14 at 7:27
  • 1
    $\begingroup$ Could you elaborate a little more about the reduced Hessian? Matrices that arise from the Karush-Kuhn-Tucker conditions can be symmetric indefinite, for instance. How much do you know about the spectrum of your matrix? $\endgroup$ – Geoff Oxberry Aug 13 '14 at 18:51
7
$\begingroup$

If your matrix is symmetric, positive definite, the CG method may converge slowly, but it converges for $n\to\infty$. The only reason it does not converge on a computer are round-off errors, in particular if the condition number of the matrix, the quotient of largest and smallest eigenvalue is large.

Experience is, that with double precision arithmetic, even with moderate condition numbers convergence stalls at around $10^{-12}$ to $10^{-14}$ of the original error.

$\endgroup$
  • $\begingroup$ In the case of symmetric positive definite matrix, the CG method converges (in theory) in $k$ iterations, where $k$ is the size of $b$. Like you said, it will stall much earlier than that in practice with finite precision. $\endgroup$ – LKlevin Aug 15 '14 at 15:37
  • 2
    $\begingroup$ To add to LKlevin, if CG executes enough iterations, the produced conjugate vectors can lose orthogonality numerically, which can also lead to nonconvergence. CG may be "restarted" to offset this. $\endgroup$ – Jesse Chan Aug 15 '14 at 15:39
3
$\begingroup$

Probabily the CG fails to converge because your problem is ill conditioned, the condition number of your matrix is too large. For SPD matrix A you can get the condition number calculating the eigenvalues

codition_number = largest_eigenvalue/smallest_eigenvalue

Ill conditioned means that small changes on some entries of the matrix could give large changes in the result when solving the system of equations (in a well conditioned matrix a small change in any entry of the matrix gives a small change in the result).

To reduce the condition number of the problem you can use a preconditioned CG, there are several preconditioners. The Jacobi preconditioner (also known as diagonal preconditioner) is easy to implement but not robust.

$\endgroup$

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.