Biconjugate gradient stabilized method: Difference between revisions

Revision as of 06:21, 31 August 2023

Latest revision as of 17:57, 29 July 2025

(8 intermediate revisions by 6 users not shown)

Line 1:

{{Short description|Concept in mathematics}}

{{Technical|date=May 2015}}

Line 5 ⟶ 6:

==Algorithmic steps==

===Unpreconditioned BiCGSTAB===

In the following sections, {{math|1=('''<var>x</var>''','''<var>y</var>''') = '''<var>x</var>'''^T '''<var>y</var>'''}} denotes the [[dot product]] of vectors. To solve a linear system {{math|'''<var>Ax</var>''' {{=}} '''<var>b</var>'''}}, BiCGSTAB starts with an initial guess {{math|'''<var>x</var>'''₀}} and proceeds as follows:

# {{math|'''<var>r</var>'''₀ {{=}} '''<var>b</var>''' − '''<var>Ax</var>'''₀}}

# Choose an arbitrary vector {{math|'''<var>r̂</var>'''₀}} such that {{math|('''<var>r̂</var>'''₀, '''<var>r</var>'''₀) ≠ 0}}, e.g., {{math|'''<var>r̂</var>'''₀ {{=}} '''<var>r</var>'''₀}} . {{math|('''<var>x</var>''','''<var>y</var>''') }} denotes the [[dot product]] of vectors {{math|1=('''<var>x</var>''','''<var>y</var>''') = '''<var>x</var>'''^T '''<var>y</var>'''}}

# {{math|<var>ρ</var>₀ {{=}} ('''<var>r̂</var>'''₀, '''<var>r</var>'''₀) }}

# {{math|'''<var>p</var>'''₀ {{=}} '''<var>r</var>'''₀}}

Line 25 ⟶ 26:

## {{math|<var>β</var> {{=}} (<var>ρ_i</var>/<var>ρ</var>_{<var>i</var>−1})(<var>α</var>/<var>ω</var>)}}

## {{math|<var>'''p'''_i</var> {{=}} '''<var>r</var>'''_<var>i</var> + <var>β</var>('''<var>p</var>'''_{<var>i</var>−1} − <var>ω</var>'''<var>v</var>''')}}

In some cases, choosing the vector {{math|'''<var>r̂</var>'''₀}} randomly improves numerical stability.<ref>{{Cite journal |last=Schoutrop |first=Chris |last2=Boonkkamp |first2=Jan ten Thije |last3=Dijk |first3=Jan van |date=July 2022 |title=Reliability Investigation of BiCGStab and IDR Solvers for the Advection-Diffusion-Reaction Equation |url=https://doi.org/10.4208/cicp.OA-2021-0182 |journal=Communications in Computational Physics |language=en |volume=32 |issue=1 |pages=156–188 |doi=10.4208/cicp.oa-2021-0182 |issn=1815-2406}}</ref>

===Preconditioned BiCGSTAB===

Line 31 ⟶ 33:

# {{math|'''<var>r</var>'''₀ {{=}} '''<var>b</var>''' − '''<var>Ax</var>'''₀}}

# Choose an arbitrary vector {{math|'''<var>r̂</var>'''₀}} such that {{math|('''<var>r̂</var>'''₀, '''<var>r</var>'''₀) ≠ 0}}, e.g., {{math|'''<var>r̂</var>'''₀ {{=}} '''<var>r</var>'''₀}}

# {{math|<var>ρ</var>₀ {{=}} ('''<var>αr̂</var>'''₀, {{=}} '''<var>ωr</var>'''₀) {{=}} 1}}

# {{math|'''<var>vp</var>'''₀ {{=}} '''<var>pr</var>'''₀ {{=}} '''0'''}}

# For {{math|<var>i</var> {{=}} 1, 2, 3, …}}

## {{math|'''<var>ρ_iy</var>''' {{=}} ({{SubSup|'''<var>r̂K</var>'''|2|−1}}{{SubSup|'''<subvar>0K</subvar>, '''|1|−1}}'''<var>rp</var>'''_{<var>i</var>−1})}}

## {{math|<var>β'''v'''</var> {{=}} ('''<var>ρ_iAy</var>/<var>ρ</var>_{<var>i</var>−1})(<var>α</var>/<var>ω</var>_{<var>i</var>−1})'''}}

## {{math|<var>'''p'''_iα</var> {{=}} '''<var>rρ</var>'''_{<var>i</var>−1} + <var>β</var>('''<var>pr̂</var>'''_{<var>i</var>−10} −, <var>ω</var>_{<var>i</var>−1}'''<var>v</var>'''_{<var>i</var>−1})}}

## {{math|'''<var>y</var>''' {{=}} {{SubSup|'''<var>K</var>'''|2|−1}}{{SubSup|'''<var>K</var>'''|1|−1}}'''<var>p</var>'''_<var>i</var>}}

## {{math|<var>'''v'''_i</var> {{=}} '''<var>Ay</var>'''}}

## {{math|<var>α</var> {{=}} <var>ρ_i</var>/('''<var>r̂</var>'''₀, <var>'''v'''_i</var>)}}

## {{math|<var>'''h'''</var> {{=}} '''<var>x</var>'''_{<var>i</var>−1} + <var>α'''y'''</var> }}

## {{math|'''<var>ys</var>''' {{=}} {{SubSup|'''<var>Kr</var>'''|2|−1}}{{SubSup|'''<sub><var>Ki</var>'''|1|−1}}'''<var/sub>p − </var>α'''v'''_<var>i</var>}}

## If {{math|<var>'''h'''</var>}} is accurate enough then {{math|<var>'''x'''_i</var> {{=}} <var>'''h'''</var>}} and quit

## {{math|'''<var>s</var>''' {{=}} '''<var>r</var>'''_{<var>i</var>−1} − <var>α'''v'''_i</var>}}

## {{math|'''<var>z</var>''' {{=}} {{SubSup|'''<var>K</var>'''|2|−1}}{{SubSup|'''<var>K</var>'''|1|−1}}'''<var>s</var>'''}}

## {{math|'''<var>t</var>''' {{=}} '''<var>Az</var>'''}}

## {{math|<var>ω_i</var> {{=}} ({{SubSup|'''<var>K</var>'''|1|−1}}'''<var>t</var>''', {{SubSup|'''<var>K</var>'''|1|−1}}'''<var>s</var>''')/({{SubSup|'''<var>K</var>'''|1|−1}}'''<var>t</var>''', {{SubSup|'''<var>K</var>'''|1|−1}}'''<var>t</var>''')}}

## {{math|<var>'''x'''_i</var> {{=}} <var>'''h'''</var> + <var>ω_i'''z'''</var>}}

## {{math|<var>'''vr'''_i</var> {{=}} '''<var>Ays</var>''' − <var>ω'''t'''</var>}}

## If {{math|<var>'''x'''_i</var>}} is accurate enough then quit

## {{math|<var>'''r'''ρ_i</var> {{=}} ('''<var>sr̂</var>''' − <var>ω_i0, '''t<var>r</var>'''_<var>i</var>)}}

## {{math|<var>αβ</var> {{=}} (<var>ρ_i</var>/('''<var>r̂ρ</var>'''_{0</subvar>, i</var>'''v'''−1}i)(<var>α</subvar>/<var>ω</var>)}}

## {{math|<var>'''p'''<varsub>i</sub>s</var>''' {{=}} '''<var>r</var>'''_{<var>i</var>−1} −+ <var>αβ</var>('''v<var>p</var>'''_{<var>i</var>−1} − <var>ω</var>'''<var>v</var>''')}}

This formulation is equivalent to applying unpreconditioned BiCGSTAB to the explicitly preconditioned system

Line 98 ⟶ 100:

which entails the necessity of a recurrence relation for {{math|<var>Q_i</var>('''<var>A</var>''')<var>T_i</var>('''<var>A</var>''')'''<var>r</var>'''₀}}. This can also be derived from the BiCG relations:

:{{math|<var>Q_i</var>('''<var>A</var>''')<var>T_i</var>('''<var>A</var>''')'''<var>r</var>'''₀ {{=}} <var>Q_i</var>('''<var>A</var>''')<var>P_i</var>('''<var>A</var>''')'''<var>r</var>'''₀ + <var>β</var>_{<var>i</var>+1}('''<var>I</var>''' − <var>ω_i'''A'''</var>)<var>Q</var>_{<var>i</var>−1}('''<var>A</var>''')<var>PT</var>_{<var>i</var>−1}('''<var>A</var>''')'''<var>r</var>'''₀}}.

Similarly to defining {{math|<var>'''r̃'''_i</var>}}, BiCGSTAB defines

Line 167 ⟶ 169:

==References==

{{reflist}}

* {{Cite journal | doi = 10.1137/0913035 | title = Bi-CGSTAB: A Fast and Smoothly Converging Variant of Bi-CG for the Solution of Nonsymmetric Linear Systems | year = 1992 | last1 = Van der Vorst | first1 = H. A. | journal = [[SIAM Journal on Scientific Computing|SIAM J. Sci. Stat. Comput.]] | volume = 13 | issue = 2 | pages = 631–644 | hdl = 10338.dmlcz/104566 | hdl-access = free }}

* {{cite book