Conjugate gradient squared method

Short description: Algorithm for solving matrix-vector equations

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