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 $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.

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