CGS-Verfahren

Das CGS-Verfahren ist ein iteratives numerisches Verfahren zur approximativen Lösung großer, dünnbesetzter linearer Gleichungssystem Ax = b mit einer reellen $n \times n$ Matrix A. CGS ist aus der Klasse der Krylow-Unterraum-Verfahren und ist insbesondere auch für nichtsymmetrische Matrizen geeignet. Es wird eingesetzt, wenn die Matrix zu groß für die Verwendung von direkten Methoden ist und nicht auf die Transponierte der Systemmatrix zugegriffen werden kann.

CGS steht für conjugate gradient squared, auf deutsch quadrierte konjugierte Gradienten und wird aus dem BiCG-Verfahren hergeleitet. Ausgehend von der Darstellung der Residuen r_j und Suchrichtungen p_j im BiCG-Verfahren mittels Polynomen lassen sich neuartige Residuen als Quadrate der Polynome angewendet auf das Startresiduum definieren, wobei die benötigten Skalare α_j und β_j aus dem BiCG-Verfahren sich durch einen Trick aus den neu konstruierten Vektoren ausrechnen lassen, ohne den im BiCG-Verfahren benötigten zweiten Krylowraum aufzubauen.

Die Anwendung der quadrierten Residuenpolynome kann in den Fällen, in denen das BiCG-Verfahren rasch konvergiert, zu einer noch rascheren Konvergenz führen. Wenn das BiCG-Verfahren langsam konvergiert, so hat das CGS-Verfahren meist noch stärkere Probleme. Ebenso wie Bi-CG weist das CGS-Verfahren keinen monotonen Residuenverlauf auf und bricht in manchen Fällen vorzeitig ab.

Das CGS-Verfahren wurde 1984 von Peter Sonneveld entwickelt und 1989 veröffentlicht. Es basiert auf den Ideen des IDR-Verfahrens, welches einige Jahre vorher von ihm entwickelt wurde.

Literatur

• Sonneveld: CGS: A fast Lanczos-Type Solver for Nonsymmetric Linear Systems. SIAM J. Sci. Stat. Comput., 10(1):36-52, 1989
• A. Meister: Numerik linearer Gleichungssysteme. 2. Auflage, Vieweg 2005, ISBN 3528131357