Conjugate gradient squared method


In numerical linear algebra, the conjugate gradient squared method is an iterative algorithm for solving systems of linear equations of the form, particularly in cases where computing the transpose is impractical. The CGS method was developed as an improvement to the biconjugate gradient method.

Background

A system of linear equations consists of a known matrix 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, then calculate. However, computing the inverse is computationally expensive. Hence, iterative methods are commonly used. Iterative methods begin with a guess, 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
  2. Compute the residual
  3. Choose
  4. For do:
  5. #
  6. # If, the method fails.
  7. # If :
  8. ##
  9. # Else:
  10. ##
  11. ##
  12. ##
  13. # Solve, where is a pre-conditioner.
  14. #
  15. #
  16. #
  17. # Solve
  18. #
  19. #
  20. #
  21. # Check for convergence: if there is convergence, end the loop and return the result