Conjugate gradient squared method

In numerical linear algebra, the conjugate gradient squared method (CGS) is an iterative algorithm for solving systems of linear equations of the form $Ax=b$, particularly in cases where computing $A^{T}$ is impractical. The CGS method was developed as an improvement to the Biconjugate gradient method.

The Algorithm

The algorithm is as follows:

1. Choose an initial guess $x_{0}$
2. $r_{0}=b-Ax_{0}$
3. Choose ${\tilde {r}}_{0}=r_{0}$
4. For $i=1,2,3,\dots$ do:
   1. $\rho _{i-1}={\tilde {r}}_{i-1}^{T}r_{i-1}$
   2. If $\rho _{i-1}=0$, the method fails.
   3. If $i=1$:
      1. $p_{1}=u_{1}=r_{0}$
   4. Else:
      1. $\beta _{i-1}=\rho _{i-1}/\rho _{i-2}$
      2. $u_{i}=r_{i-1}+\beta _{i-1}q_{i-1}$
      3. $p_{i}=u_{i}+\beta _{i-1}(q_{i-1}+\beta _{i-1}p_{i-1})$
   5. Solve $M{\hat {p}}=p_{i}$, where $M$ is a pre-conditioner.
   6. ${\hat {v}}=A{\hat {p}}$
   7. $\alpha _{i}=\rho _{i-1}/{\tilde {r}}^{T}{\hat {v}}$
   8. $q_{i}=u_{i}-\alpha _{i}{\hat {v}}$
   9. Solve $M{\hat {u}}=u_{i}+q_{i}$
   10. $x_{i}=x_{i-1}+\alpha _{i}{\hat {u}}$
   11. ${\hat {q}}=A{\hat {u}}$
   12. $r_{i}=r_{i-1}-\alpha _{i}{\hat {q}}$
   13. Check for convergence: if there is convergence, end the loop and return the result

See Also

• Biconjugate gradient method
• Biconjugate gradient stabilized method
• Generalized minimal residual method

References

Category:Numerical linear algebra Category:Gradient methods