CGS procedure

The CGS method is an iterative numerical method for the approximate solution of large sparse linear system of equations with a real matrix A . CGS is from the class of the Krylow subspace method and is also particularly suitable for non-symmetrical matrices. It is used when the matrix is too large to use direct methods and the transpose of the system matrix cannot be accessed. ${\displaystyle Ax=b}$ ${\displaystyle n\times n}$

CGS stands for conjugate gradient squared , on German squared conjugate gradient and from the BiCG process derived. Based on the representation of the residuals and search directions in the BiCG method by means of polynomials, new types of residuals can be defined as squares of the polynomials applied to the starting residual, whereby the required scalars and from the BiCG method can be calculated from the newly constructed vectors using a trick, without building up the second cryogenic space required in the BiCG process . ${\displaystyle r_{j}}$ ${\displaystyle p_{j}}$ ${\displaystyle \alpha _{j}}$ ${\displaystyle \beta _{j}}$

The application of the squared residual polynomials can lead to an even faster convergence in cases in which the BiCG method converges quickly. If the BiCG method converges slowly, the CGS method usually has even greater problems. Like Bi-CG, the CGS method does not have a monotonous residual curve and in some cases breaks off prematurely.

The CGS method was developed by Peter Sonneveld in 1984 and published in 1989. It is based on the ideas of the IDR process , which he developed a few years earlier.

literature

• Sonneveld: CGS: A fast Lanczos-Type Solver for Nonsymmetric Linear Systems. SIAM J. Sci. Stat. Comput., 10 (1): 36-52, 1989
• A. Meister: Numerics of linear systems of equations. 2nd edition, Vieweg 2005, ISBN 3528131357