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

Background

A system of linear equations ${\displaystyle A{\mathbf {x}}={\mathbf {b}}}$ consists of a known matrix ${\displaystyle A}$ and a known vector ${\displaystyle {\mathbf {b}}}$. To solve the system is to find the value of the unknown vector ${\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}$, then calculate ${\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)}}$, 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]

Algorithm

The algorithm is as follows: ^[9]

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

See also

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

References

1. Noel Black; Shirley Moore. "Conjugate Gradient Squared Method". Wolfram Mathworld.
2. Mathworks. "cgs". Matlab documentation.
3. Henk van der Vorst (2003). "Bi-Conjugate Gradients". Iterative Krylov Methods for Large Linear Systems. Cambridge University Press. ISBN   0-521-81828-1.
4. Peter Sonneveld (1989). "CGS, A Fast Lanczos-Type Solver for Nonsymmetric Linear systems" . SIAM Journal on Scientific and Statistical Computing. 10 (1): 36–52. doi:10.1137/0910004. ProQuest   921988114.
5. "Linear equations" (PDF), Matrix Analysis and Applied Linear Algebra, Philadelphia, PA: SIAM, 2000, pp. 1–40, doi:10.1137/1.9780898719512.ch1 (inactive 11 July 2025), ISBN   978-0-89871-454-8, archived from the original (PDF) on 2004-06-10, retrieved 2023-12-18
6. "Iterative Methods for Linear Systems". Mathworks.
7. Jean Gallier. "Iterative Methods for Solving Linear Systems" (PDF). UPenn.
8. Alexandra Roberts; Anye Shi; Yue Sun. "Conjugate gradient methods". Cornell University . Retrieved 2023-12-26.
9. R. Barrett; M. Berry; T. F. Chan; J. Demmel; J. Donato; J. Dongarra; V. Eijkhout; R. Pozo; C. Romine; H. Van der Vorst (1994). Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods, 2nd Edition. SIAM.