Conjugate gradient squared method

• Comment: Thanks for your submission! I'm going to have to decline this for now as the draft is essentially just a statement of the algorithm with no explanation. This is not useful as an encyclopedic reference, as the significant technical language makes it difficult to read for anyone other than people familiar with the subject. Let me know if you have any questions! —TechnoSquirrel69 (sigh) 20:01, 4 November 2023 (UTC)

---

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 the transpose $A^{T}$ is impractical. The CGS method was developed as an improvement to the Biconjugate gradient method.

As with other methods for solving matrix-vector equations, the CGS method can be used to solve optimisation problems

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