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 $A{\mathbf {x}}={\mathbf {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.

Background

A system of linear equations $A{\mathbf {x}}={\mathbf {b}}$ consists of a known matrix $A$ and a known vector ${\mathbf {b}}$. To solve the system is to find the value of the unknown vector ${\mathbf {x}}$. A direct method for solving a system of linear equations is to take the inverse of the matrix $A$, then calculate ${\mathbf {x}}=A^{-1}{\mathbf {b}}$. However, computing the inverse is computationally expensive. Hence, iterative methods are commonly used. Iterative methods begin with a guess ${\mathbf {x}}^{(0)}$, and on each iteration the guess is improved. Once the difference between successive guesses is sufficiently small, the method has converged to a solution.

As with the conjugate gradient method, biconjugate gradient method, and similar iterative methods for solving systems of linear equations, the CGS method can be used to find solutions to multi-variable optimisation problems, such as power-flow analysis, hyperparameter optimisation, and facial recognition.

The Algorithm

The algorithm is as follows:

1. Choose an initial guess ${\mathbf {x}}^{(0)}$
2. Compute the residual ${\mathbf {r}}^{(0)}={\mathbf {b}}-A{\mathbf {x}}^{(0)}$
3. Choose ${\tilde {\mathbf {r}}}^{(0)}={\mathbf {r}}^{(0)}$
4. For $i=1,2,3,\dots$ do:
   1. $\rho ^{(i-1)}={\tilde {\mathbf {r}}}^{T(i-1)}{\mathbf {r}}^{(i-1)}$
   2. If $\rho ^{(i-1)}=0$, the method fails.
   3. If $i=1$:
      1. ${\mathbf {p}}^{(1)}={\mathbf {u}}^{(1)}={\mathbf {r}}^{(0)}$
   4. Else:
      1. $\beta ^{(i-1)}=\rho ^{(i-1)}/\rho ^{(i-2)}$
      2. ${\mathbf {u}}^{(i)}={\mathbf {r}}^{(i-1)}+\beta _{i-1}{\mathbf {q}}^{(i-1)}$
      3. ${\mathbf {p}}^{(i)}={\mathbf {u}}^{(i)}+\beta ^{(i-1)}({\mathbf {q}}^{(i-1)}+\beta ^{(i-1)}{\mathbf {p}}^{(i-1)})$
   5. Solve $M{\hat {\mathbf {p}}}={\mathbf {p}}^{(i)}$, where $M$ is a pre-conditioner.
   6. ${\hat {\mathbf {v}}}=A{\hat {\mathbf {p}}}$
   7. $\alpha ^{(i)}=\rho ^{(i-1)}/{\tilde {\mathbf {r}}}^{T}{\hat {\mathbf {v}}}$
   8. ${\mathbf {q}}^{(i)}={\mathbf {u}}^{(i)}-\alpha ^{(i)}{\hat {\mathbf {v}}}$
   9. Solve $M{\hat {\mathbf {u}}}={\mathbf {u}}^{(i)}+{\mathbf {q}}^{(i)}$
   10. ${\mathbf {x}}^{(i)}={\mathbf {x}}^{(i-1)}+\alpha ^{(i)}{\hat {\mathbf {u}}}$
   11. ${\hat {\mathbf {q}}}=A{\hat {\mathbf {u}}}$
   12. ${\mathbf {r}}^{(i)}={\mathbf {r}}^{(i-1)}-\alpha ^{(i)}{\hat {\mathbf {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