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 ${\displaystyle A{\mathbf {x}}={\mathbf {b}}}${\displaystyle A{\mathbf {x}}={\mathbf {b}}}, particularly in cases where computing the transpose ${\displaystyle A^{T}}${\displaystyle A^{T}} is impractical.^[1] The CGS method was developed as an improvement to the biconjugate gradient method.^{[2] [3] [4]}

A system of linear equations ${\displaystyle A{\mathbf {x}}={\mathbf {b}}}${\displaystyle A{\mathbf {x}}={\mathbf {b}}} consists of a known matrix ${\displaystyle A}${\displaystyle A} and a known vector ${\displaystyle {\mathbf {b}}}${\displaystyle {\mathbf {b}}}. To solve the system is to find the value of the unknown vector ${\displaystyle {\mathbf {x}}}${\displaystyle {\mathbf {x}}}.^{[3] [5]} A direct method for solving a system of linear equations is to take the inverse of the matrix ${\displaystyle A}${\displaystyle A}, then calculate ${\displaystyle {\mathbf {x}}=A^{-1}{\mathbf {b}}}${\displaystyle {\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 ${\displaystyle {\mathbf {x}}^{(0)}}${\displaystyle {\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.^{[6] [7]}

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.^[8]

The algorithm is as follows:^[9]

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

• Biconjugate gradient method
• Biconjugate gradient stabilized method
• Generalized minimal residual method

• Numerical linear algebra
• Gradient methods

• CS1 maint: DOI inactive as of July 2025
• Articles with short description
• Short description matches Wikidata
• Pages that use a deprecated format of the math tags