Conjugate gradient squared method: Difference between revisions

Revision as of 00:15, 5 November 2023

Latest revision as of 22:43, 11 July 2025

(40 intermediate revisions by 10 users not shown)

Line 1:

{{Short description|Algorithm for solving matrix-vector equations}}

{{AFC submission|d|context|u=MtPenguinMonster|ns=118|decliner=TechnoSquirrel69|declinets=20231104200137|ts=20230923053512}} <!-- Do not remove this line! -->

In [[numerical linear algebra]], the '''conjugate gradient squared method (CGS)''' is an [[iterative method|iterative]] algorithm for solving [[systems of linear equations]] of the form <math>AxA{\bold x} = {\bold b}</math>, particularly in cases where computing the [[transpose]] <math>A^T</math> is impractical.<ref name="mathworld">{{cite web|title=Conjugate Gradient Squared Method|author1=Noel Black|author2=Shirley Moore|publisher=[[MathWorld|Wolfram Mathworld]]|url=https://mathworld.wolfram.com/ConjugateGradientSquaredMethod.html}}</ref> The CGS method was developed as an improvement to the [[Biconjugatebiconjugate gradient method]].<ref name="matlab">{{cite web|title=cgs|author=[[Mathworks]]|website=[[Matlab]] documentation|url=https://au.mathworks.com/help/matlab/ref/cgs.html}}</ref><ref name="vorst03">{{cite book|author=[[Henk van der Vorst]]|title=Iterative Krylov Methods for Large Linear Systems|chapter=Bi-Conjugate Gradients|year=2003|publisher=Cambridge University Press |isbn=0-521-81828-1}}</ref><ref name="SIAM">{{cite journal|title=CGS, A Fast Lanczos-Type Solver for Nonsymmetric Linear systems|author=Peter Sonneveld|journal=SIAM Journal on Scientific and Statistical Computing|volume=10|issue=1|pages=36–52|date=1989|url=https://www.proquest.com/docview/921988114|url-access=limited|doi=10.1137/0910004|id={{ProQuest|921988114}} }}</ref>

{{AFC comment|1=Thanks for your submission! I'm going to have to decline this for now as the draft is essentially just a statement of the algorithm with no explanation. This is not useful as an encyclopedic reference, as the [[WP:MTAU|significant technical language]] makes it difficult to read for anyone other than people familiar with the subject. Let me know if you have any questions! <span class="nowrap">—[[User:TechnoSquirrel69|TechnoSquirrel69]]</span> ([[User talk:TechnoSquirrel69|sigh]]) 20:01, 4 November 2023 (UTC)}}

== Background ==

----

A [[system of linear equations]] <math>A{\bold x} = {\bold b}</math> consists of a known [[Matrix (mathematics)|matrix]] <math>A</math> and a known [[Vector (mathematics)|vector]] <math>{\bold b}</math>. To solve the system is to find the value of the unknown vector <math>{\bold x}</math>.<ref name="vorst03" /><ref>{{Citation |title=Matrix Analysis and Applied Linear Algebra |pages=1–40 |access-date=2023-12-18 |archive-url=https://web.archive.org/web/20040610221137/http://www.matrixanalysis.com/Chapter1.pdf |chapter=Linear equations |date=2000 |chapter-url=http://www.matrixanalysis.com/Chapter1.pdf |place= Philadelphia, PA |publisher=SIAM |doi=10.1137/1.9780898719512.ch1 |doi-broken-date=11 July 2025|isbn=978-0-89871-454-8 |archive-date=2004-06-10 }}</ref> A direct method for solving a system of linear equations is to take the inverse of the matrix <math>A</math>, then calculate <math>\bold x = A^{-1}\bold b</math>. However, computing the inverse is computationally expensive. Hence, iterative methods are commonly used. Iterative methods begin with a guess <math>\bold x^{(0)}</math>, and on each iteration the guess is improved. Once the difference between successive guesses is sufficiently small, the method has converged to a solution.<ref>{{cite web|title=Iterative Methods for Linear Systems|publisher=[[Mathworks]]|url=https://au.mathworks.com/help/matlab/math/iterative-methods-for-linear-systems.html}}</ref><ref>{{cite web|title=Iterative Methods for Solving Linear Systems|author=Jean Gallier|publisher=[[UPenn]]|url=https://www.cis.upenn.edu/~cis5150/cis515-12-sl5.pdf}}</ref>

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 study|power-flow analysis]], [[hyperparameter optimisation]], and [[facial recognition system|facial recognition]].<ref>{{cite web|title=Conjugate gradient methods|author1=Alexandra Roberts|author2=Anye Shi|author3=Yue Sun|access-date=2023-12-26|publisher=[[Cornell University]]|url=https://optimization.cbe.cornell.edu/index.php?title=Conjugate_gradient_methods}}</ref>

{{Short description|Algorithm for solving matrix-vector equations}}

{{Draft topics|computing|mathematics}}

{{AfC topic|stem}}

== The Algorithm ==

In [[numerical linear algebra]], the '''conjugate gradient squared method (CGS)''' is an [[iterative method|iterative]] algorithm for solving systems of linear equations of the form <math>Ax = b</math>, particularly in cases where computing the [[transpose]] <math>A^T</math> is impractical.<ref>{{cite web|title=Conjugate Gradient Squared Method|author1=Noel Black|author2=Shirley Moore|publisher=[[MathWorld|Wolfram Mathworld]]|url=https://mathworld.wolfram.com/ConjugateGradientSquaredMethod.html}}</ref> The CGS method was developed as an improvement to the [[Biconjugate gradient method]].<ref>{{cite web|title=cgs|author=Mathworks|url=https://au.mathworks.com/help/matlab/ref/cgs.html}}</ref><ref>{{cite book|author=[[Henk van der Vorst]]|title=Iterative Krylov Methods for Large Linear Systems|chapter=Bi-Conjugate Gradients|year=2003|publisher=Cambridge University Press |isbn=0-521-81828-1}}</ref><ref>{{cite journal|title=CGS, A Fast Lanczos-Type Solver for Nonsymmetric Linear systems|author=Peter Sonneveld|journal=SIAM Journal on Scientific and Statistical Computing|volume=10|issue=1|pages=36–52|date=1989|url=https://www.proquest.com/docview/921988114|url-access=limited|doi=10.1137/0910004|id={{ProQuest|921988114}} }}</ref>

As with other methods for solving matrix-vector equations, the CGS method can be used to solve optimisation problems

== The Algorithm ==

The algorithm is as follows:<ref>{{cite book|author1=R. Barrett|author2=M. Berry|author3=T. F. Chan|author4=J. Demmel|author5=J. Donato|author6=J. Dongarra|author7=V. Eijkhout|author8=R. Pozo|author9=C. Romine|author10=H. Van der Vorst|title=Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods, 2nd Edition|publisher=SIAM|year=1994|url=https://netlib.org/linalg/html_templates/Templates.html}}</ref>

# Choose an initial guess <math>x_0{\bold x}^{(0)}</math>

# Compute the residual <math>r_0{\bold r}^{(0)} = {\bold b} - Ax_0A{\bold x}^{(0)}</math>

# Choose <math>\tilde r_0{\bold r}^{(0)} = r_0{\bold r}^{(0)}</math>

# For <math>i = 1, 2, 3, \dots</math> do:

## <math>\rho_rho^{(i-1)} = \tilde {\bold r}^T_{T(i-1)}r_{\bold r}^{(i-1)}</math>

## If <math>\rho_rho^{(i-1)} = 0</math>, the method fails.

## If <math>i=1</math>:

### <math>p_1{\bold p}^{(1)} = u_1{\bold u}^{(1)} = r_0{\bold r}^{(0)}</math>

## Else:

### <math>\beta_beta^{(i-1)} = \rho_rho^{(i-1)}/\rho_rho^{(i-2)}</math>

### <math>u_i{\bold u}^{(i)} = r_{\bold r}^{(i-1)} + \beta_{i-1}q_{\bold q}^{(i-1)}</math>

### <math>p_i{\bold p}^{(i)} = u_i{\bold u}^{(i)} + \beta_beta^{(i-1)}(q_{\bold q}^{(i-1)} + \beta_beta^{(i-1)}p_{\bold p}^{(i-1)})</math>

## Solve <math>M\hat {\bold p}=p_i{\bold p}^{(i)}</math>, where <math>M</math> is a pre-conditioner.

## <math>\hat {\bold v} = A\hat {\bold p}</math>

## <math>\alpha_ialpha^{(i)} = \rho_rho^{(i-1)} / \tilde {\bold r}^T \hat {\bold v}</math>

## <math>q_i{\bold q}^{(i)} = u_i{\bold u}^{(i)} - \alpha_ialpha^{(i)}\hat {\bold v}</math>

## Solve <math>M\hat {\bold u} = u_i{\bold u}^{(i)} + q_i{\bold q}^{(i)}</math>

## <math>x_i{\bold x}^{(i)} = x_{\bold x}^{(i-1)} + \alpha_ialpha^{(i)} \hat {\bold u}</math>

## <math>\hat {\bold q} = A\hat {\bold u}</math>

## <math>r_i{\bold r}^{(i)} = r_{\bold r}^{(i-1)} - \alpha_ialpha^{(i)}\hat {\bold q}</math>

## Check for convergence: if there is convergence, end the loop and return the result

== See Alsoalso ==

* [[Biconjugate gradient method]]

* [[Biconjugate gradient stabilized method]]

Line 45 ⟶ 40:

== References ==

<!-- Inline citations added to your article will automatically display here. See en.wikipedia.org/wiki/WP:REFB for instructions on how to add citations. -->

{{reflist}}

{{Reflist}}

[[:Category:Numerical linear algebra]]

[[:Category:Gradient methods]]

[[:Category:Numerical linear algebra]]

[[:Category:Gradient methods]]