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𝐱=𝐛$, 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𝐱=𝐛$ consists of a known matrix $A$ and a known vector $𝐛$. To solve the system is to find the value of the unknown vector $𝐱$. A direct method for solving a system of linear equations is to take the inverse of the matrix $A$, then calculate $𝐱=A^{-1}𝐛$. However, computing the inverse is computationally expensive. Hence, iterative methods are commonly used. Iterative methods begin with a guess ${𝐱}^{(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 ${𝐱}^{(0)}$
2. Compute the residual ${𝐫}^{(0)}=𝐛-A{𝐱}^{(0)}$
3. Choose ${\widetilde{𝐫}}^{(0)}={𝐫}^{(0)}$
4. For $i=1,2,3,\dots$ do:
   1. ${\rho }^{(i-1)}={\widetilde{𝐫}}^{T(i-1)}{𝐫}^{(i-1)}$
   2. If ${\rho }^{(i-1)}=0$, the method fails.
   3. If $i=1$:
      1. ${𝐩}^{(1)}={𝐮}^{(1)}={𝐫}^{(0)}$
   4. Else:
      1. ${\beta }^{(i-1)}={\rho }^{(i-1)}/{\rho }^{(i-2)}$
      2. ${𝐮}^{(i)}={𝐫}^{(i-1)}+{\beta }_{i-1}{𝐪}^{(i-1)}$
      3. ${𝐩}^{(i)}={𝐮}^{(i)}+{\beta }^{(i-1)}({𝐪}^{(i-1)}+{\beta }^{(i-1)}{𝐩}^{(i-1)})$
   5. Solve $M\widehat{𝐩}={𝐩}^{(i)}$, where $M$ is a pre-conditioner.
   6. $\widehat{𝐯}=A\widehat{𝐩}$
   7. ${\alpha }^{(i)}={\rho }^{(i-1)}/{\widetilde{𝐫}}^T\widehat{𝐯}$
   8. ${𝐪}^{(i)}={𝐮}^{(i)}-{\alpha }^{(i)}\widehat{𝐯}$
   9. Solve $M\widehat{𝐮}={𝐮}^{(i)}+{𝐪}^{(i)}$
   10. ${𝐱}^{(i)}={𝐱}^{(i-1)}+{\alpha }^{(i)}\widehat{𝐮}$
   11. $\widehat{𝐪}=A\widehat{𝐮}$
   12. ${𝐫}^{(i)}={𝐫}^{(i-1)}-{\alpha }^{(i)}\widehat{𝐪}$
   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