Conjugate gradient squared method explained

In numerical linear algebra, the conjugate gradient squared method (CGS) is an iterative algorithm for solving systems of linear equations of the form

A{\bold x} = {\bold b} , particularly in cases where computing the transpose A ^{T} is impractical.^[1] The CGS method was developed as an improvement to the biconjugate gradient method.^{[2] [3] [4]}

Background

A{\bold x} = {\bold b} consists of a known matrix A and a known vector {\bold b} . To solve the system is to find the value of the unknown vector {\bold x} . A direct method for solving a system of linear equations is to take the inverse of the matrix A , then calculate \bold x = A ^{-1} \bold b . However, computing the inverse is computationally expensive. Hence, iterative methods are commonly used. Iterative methods begin with a guess \bold 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.^{[5] [6]}

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

Algorithm

The algorithm is as follows:^[8]

1. Choose an initial guess

{\bold x} ^{(0)}

1. Compute the residual

{\bold r} ^{(0)} = {\bold b} - A{\bold x} ^{(0)}

1. Choose

\tilde {\bold r} ^{(0)} = {\bold r} ^{(0)}

1. For

i = 1 , 2 , 3 , ... do:\rho ^{(i-1)} = \tilde {\bold r} ^{T(i-1)} {\bold r} ^{(i-1)}

1. 1. If

\rho ^{(i-1)} = 0 , the method fails.

1. 1. If

i =1 :{\bold p} ^{(1)} = {\bold u} ^{(1)} = {\bold r} ^{(0)}

1. 1. Else:

\beta ^{(i-1)} = \rho ^{(i-1)} /\rho ^{(i-2)} {\bold u} ^{(i)} = {\bold r} ^{(i-1)} + \beta _{i-1} {\bold q} ^{(i-1)} {\bold p} ^{(i)} = {\bold u} ^{(i)} + \beta ^{(i-1)} ({\bold q} ^{(i-1)} + \beta ^{(i-1)} {\bold p} ^{(i-1)} )

1. 1. Solve

M\hat {\bold p} = {\bold p} ^{(i)} , where M is a pre-conditioner.\hat {\bold v} = A\hat {\bold p} \alpha ^{(i)} = \rho ^{(i-1)} / \tilde {\bold r} ^{T} \hat {\bold v} {\bold q} ^{(i)} = {\bold u} ^{(i)} - \alpha ^{(i)} \hat {\bold v}

1. 1. Solve

M\hat {\bold u} = {\bold u} ^{(i)} + {\bold q} ^{(i)} {\bold x} ^{(i)} = {\bold x} ^{(i-1)} + \alpha ^{(i)} \hat {\bold u} \hat {\bold q} = A\hat {\bold u} {\bold r} ^{(i)} = {\bold r} ^{(i-1)} - \alpha ^{(i)} \hat {\bold q}

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

Notes and References

1. Web site: Conjugate Gradient Squared Method. Noel Black. Shirley Moore. Wolfram Mathworld.
2. Web site: cgs. Mathworks. Matlab documentation.
3. Book: Henk van der Vorst. Iterative Krylov Methods for Large Linear Systems. Bi-Conjugate Gradients. 2003. Cambridge University Press . 0-521-81828-1.
4. CGS, A Fast Lanczos-Type Solver for Nonsymmetric Linear systems. Peter Sonneveld. SIAM Journal on Scientific and Statistical Computing. 10. 1. 36–52. 1989. limited. 10.1137/0910004. .
5. Web site: Iterative Methods for Linear Systems. Mathworks.
6. Web site: Iterative Methods for Solving Linear Systems. Jean Gallier. UPenn.
7. Web site: Conjugate gradient methods. Alexandra Roberts. Anye Shi. Yue Sun. 2023-12-26. Cornell University.
8. Book: R. Barrett. M. Berry. T. F. Chan. J. Demmel. J. Donato. J. Dongarra. V. Eijkhout. R. Pozo. C. Romine. H. Van der Vorst. Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods, 2nd Edition. SIAM. 1994.