1
$\begingroup$

In the standard formulation of Krylov subspace methods, you always have to divide by 0 somewhere in a solution, e.g., in CG, $$ x_{k+1} = x_k + \frac{r_k^T r_k}{p_k^T A p_k} p_k\\ p_{k+1} = r_{k+1} + \frac{r^T_{k+1} r_{k+1}}{r^T_k r_k} p_k $$ (Normally, of course, you never get there because the stopping criterion hits before this.)

Are there formulations of CG that avoid this division, e.g., by computing the coefficients in a recurrence?

$\endgroup$
  • 1
    $\begingroup$ Why do you think that you have to divide by zero? The terms you divide by are, by definition of the CG iteration, positive unless you have a singular or indefinite matrix. $\endgroup$ – Wolfgang Bangerth Sep 1 at 0:28
3
$\begingroup$

Either of $p_k$ or $r_k$ being zero implies exact convergence in exact arithmetic, so that is never a problem. Conjugate gradient was used as a direct solver for linear systems of equations much before it was used as an iterative solver, because we know that for an $n\times n$ symmetric positive definite linear system CG will converge to the exact solution in $n$ iterations and the breakdown you are worried about happens at $n+1$-st iteration.

On computer arithmetic, I suppose you can encounter early breakdown if either quantity underflows and becomes zero. I find it very unlikely though, because either denominator be should be less than ~$10^{-308}$ for underflow. Alternatively, it may happen if some entries of the vectors are many magnitudes larger than others, and it can result in wrong arithmetic due to the gaps between representable numbers. You may observe false convergence in that case. The solution is to symmetrically normalize the coefficient matrix in most cases.

| cite | improve this answer | |
$\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.