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:

Choose an initial guess $𝐱^{(0)}$
Compute the residual $𝐫^{(0)} = 𝐛 - A 𝐱^{(0)}$
Choose $\tilde{𝐫} = 𝐫^{(0)}$
For i=1,2,3,… do:
1. $ρ^{(i - 1)} = {\tilde{𝐫}}^{T} 𝐫^{(i - 1)}$
2. If $ρ^{(i - 1)} = 0$ , the method fails.
3. If i=1:
  1. $𝐩^{(1)} = 𝐮^{(1)} = 𝐫^{(0)}$
4. Else:
  1. $β^{(i - 1)} = ρ^{(i - 1)} / ρ^{(i - 2)}$
  2. $𝐮^{(i)} = 𝐫^{(i - 1)} + β_{i - 1} 𝐪^{(i - 1)}$
  3. $𝐩^{(i)} = 𝐮^{(i)} + β^{(i - 1)} (𝐪^{(i - 1)} + β^{(i - 1)} 𝐩^{(i - 1)})$
5. Solve $M \hat{𝐩} = 𝐩^{(i)}$ , where $M$ is a pre-conditioner.
6. $\hat{𝐯} = A \hat{𝐩}$
7. $α^{(i)} = ρ^{(i - 1)} / {\tilde{𝐫}}^{T} \hat{𝐯}$
8. $𝐪^{(i)} = 𝐮^{(i)} - α^{(i)} \hat{𝐯}$
9. Solve $M \hat{𝐮} = 𝐮^{(i)} + 𝐪^{(i)}$
10. $𝐱^{(i)} = 𝐱^{(i - 1)} + α^{(i)} \hat{𝐮}$
11. $\hat{𝐪} = A \hat{𝐮}$
12. $𝐫^{(i)} = 𝐫^{(i - 1)} - α^{(i)} \hat{𝐪}$
13. Check for convergence: if there is convergence, end the loop and return the result

References

↑ Noel Black; Shirley Moore. "Conjugate Gradient Squared Method". Wolfram Mathworld.
↑ Mathworks. "cgs". Matlab documentation.
1 2 Henk van der Vorst (2003). "Bi-Conjugate Gradients". Iterative Krylov Methods for Large Linear Systems. Cambridge University Press. ISBN 0-521-81828-1.
↑ 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.
↑ "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 on 2004-06-10, retrieved 2023-12-18{{citation}}: CS1 maint: DOI inactive as of July 2025 (link)
↑ "Iterative Methods for Linear Systems". Mathworks.
↑ Jean Gallier. "Iterative Methods for Solving Linear Systems" (PDF). UPenn.
↑ Alexandra Roberts; Anye Shi; Yue Sun. "Conjugate gradient methods". Cornell University. Retrieved 2023-12-26.
↑ 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.

[mathworld-1] Noel Black; Shirley Moore. "Conjugate Gradient Squared Method". Wolfram Mathworld.

[matlab-2] Mathworks. "cgs". Matlab documentation.

[vorst03-3] 1 2 Henk van der Vorst (2003). "Bi-Conjugate Gradients". Iterative Krylov Methods for Large Linear Systems. Cambridge University Press. ISBN 0-521-81828-1.

[SIAM-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 on 2004-06-10, retrieved 2023-12-18{{citation}}: CS1 maint: DOI inactive as of July 2025 (link)

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

Conjugate gradient squared method

Background

Algorithm

See also

References