KNOWPIA
WELCOME TO KNOWPIA

In numerical linear algebra, the **biconjugate gradient stabilized method**, often abbreviated as **BiCGSTAB**, is an iterative method developed by H. A. van der Vorst for the numerical solution of nonsymmetric linear systems. It is a variant of the biconjugate gradient method (BiCG) and has faster and smoother convergence than the original BiCG as well as other variants such as the conjugate gradient squared method (CGS). It is a Krylov subspace method. Unlike the original BiCG method, it doesn't require multiplication by the transpose of the system matrix.

In the following sections, (** x**,

`r`_{0}=−`b``Ax`_{0}- Choose an arbitrary vector
`r̂`_{0}such that (`r̂`_{0},`r`_{0}) ≠ 0, e.g.,`r̂`_{0}=`r`_{0} `ρ`_{0}= (`r̂`_{0},`r`_{0})`p`_{0}=`r`_{0}- For
`i`= 1, 2, 3, …=`v``Ap`_{i−1}`α`=`ρ`_{i−1}/(`r̂`_{0},)**v**=**h**`x`_{i−1}+`α`**p**_{i−1}=**s****r**_{i−1}−`α`**v**- If
is accurate enough, i.e., if**h**is small enough, then set**s**=**x**_{i}and quit**h** =`t``As``ω`= (,**t**)/(**s**,**t**)**t**=**x**_{i}+**h**`ω`**s**=**r**_{i}−**s**`ω`**t**- If
is accurate enough, i.e., if**x**_{i}is small enough, then quit**r**_{i} `ρ`= (_{i}`r̂`_{0},`r`_{i})`β`= (`ρ`/_{i}`ρ`_{i−1})(`α`/`ω`)=**p**_{i}`r`_{i}+`β`(`p`_{i−1}−`ω`)`v`

In some cases, choosing the vector `r̂`_{0} randomly improves numerical stability.^{[1]}

Preconditioners are usually used to accelerate convergence of iterative methods. To solve a linear system ** Ax** =

`r`_{0}=−`b``Ax`_{0}- Choose an arbitrary vector
`r̂`_{0}such that (`r̂`_{0},`r`_{0}) ≠ 0, e.g.,`r̂`_{0}=`r`_{0} `ρ`_{0}= (`r̂`_{0},`r`_{0})`p`_{0}=`r`_{0}- For
`i`= 1, 2, 3, …=`y`−1`K`

2−1`K`

1`p`_{i−1}=**v**`Ay``α`=`ρ`_{i−1}/(`r̂`_{0},)**v**=**h**`x`_{i−1}+`α`**y**=`s``r`_{i−1}−`α`**v**- If
is accurate enough then**h**=**x**_{i}and quit**h** =`z`−1`K`

2−1`K`

1`s`=`t``Az``ω`= (−1`K`

1,`t`−1`K`

1)/(`s`−1`K`

1,`t`−1`K`

1)`t`=**x**_{i}+**h**`ω`**z**=**r**_{i}−`s``ω`**t**- If
is accurate enough then quit**x**_{i} `ρ`= (_{i}`r̂`_{0},`r`_{i})`β`= (`ρ`/_{i}`ρ`_{i−1})(`α`/`ω`)=**p**_{i}`r`_{i}+`β`(`p`_{i−1}−`ω`)`v`

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

=`Ãx̃``b̃`

with ** Ã** =

1

2 ,

1

In BiCG, the search directions ` p_{i}` and

=**p**_{i}`r`_{i−1}+`β`_{i}`p`_{i−1},`p̂`_{i}=`r̂`_{i−1}+`β`_{i}`p̂`_{i−1},=**r**_{i}`r`_{i−1}−`α`_{i}`Ap`_{i},`r̂`_{i}=`r̂`_{i−1}−`α`_{i}`A`^{T}`p̂`_{i}.

The constants `α _{i}` and

`α`=_{i}`ρ`/(_{i}`p̂`_{i},),**Ap**_{i}`β`=_{i}`ρ`/_{i}`ρ`_{i−1}

where `ρ _{i}` = (

- (
`r̂`_{i},) = 0,**r**_{j} - (
`p̂`_{i},) = 0.**Ap**_{j}

It is straightforward to show that

=**r**_{i}`P`(_{i})`A``r`_{0},`r̂`_{i}=`P`(_{i}`A`^{T})`r̂`_{0},`p`_{i+1}=`T`(_{i})`A``r`_{0},`p̂`_{i+1}=`T`(_{i}`A`^{T})`r̂`_{0}

where `P _{i}`(

`P`(_{i}) =`A``P`_{i−1}() −`A``α`_{i}**A**T_{i−1}(),`A``T`(_{i}) =`A``P`(_{i}) +`A``β`_{i+1}`T`_{i−1}().`A`

It is unnecessary to explicitly keep track of the residuals and search directions of BiCG. In other words, the BiCG iterations can be performed implicitly. In BiCGSTAB, one wishes to have recurrence relations for

`r̃`_{i}=`Q`(_{i})`A``P`(_{i})`A``r`_{0}

where `Q _{i}`(

It follows from the recurrence relations for `P _{i}`(

`Q`(_{i})`A``P`(_{i})`A``r`_{0}= (−`I``ω`)(_{i}**A**`Q`_{i−1}()`A``P`_{i−1}()`A``r`_{0}−`α`_{i}**A**Q_{i−1}()`A``T`_{i−1}()`A``r`_{0}),

which entails the necessity of a recurrence relation for `Q _{i}`(

`Q`(_{i})`A``T`(_{i})`A``r`_{0}=`Q`(_{i})`A``P`(_{i})`A``r`_{0}+`β`_{i+1}(−`I``ω`)_{i}**A**`Q`_{i−1}()`A``P`_{i−1}()`A``r`_{0}.

Similarly to defining ` r̃_{i}`, BiCGSTAB defines

`p̃`_{i+1}=`Q`(_{i})`A``T`(_{i})`A``r`_{0}.

Written in vector form, the recurrence relations for `p̃`_{i} and `r̃`_{i} are

`p̃`_{i}=`r̃`_{i−1}+`β`(_{i}−`I``ω`_{i−1})`A``p̃`_{i−1},`r̃`_{i}= (−`I``ω`)(_{i}**A**`r̃`_{i−1}−`α`_{i}**A**`p̃`_{i}).

To derive a recurrence relation for ` x_{i}`, define

=**s**_{i}`r̃`_{i−1}−`α`_{i}**A**`p̃`_{i}.

The recurrence relation for `r̃`_{i} can then be written as

`r̃`_{i}=`r̃`_{i−1}−`α`_{i}**A**`p̃`_{i}−`ω`,_{i}**As**_{i}

which corresponds to

`x`_{i}=`x`_{i−1}+`α`_{i}`p̃`_{i}+`ω`._{i}**s**_{i}

Now it remains to determine the BiCG constants `α _{i}` and

In BiCG, `β _{i}` =

`ρ`= (_{i}`r̂`_{i−1},`r`_{i−1}) = (`P`_{i−1}(`A`^{T})`r̂`_{0},`P`_{i−1}()`A``r`_{0}).

Since BiCGSTAB does not explicitly keep track of `r̂`_{i} or `r`_{i}, `ρ _{i}` is not immediately computable from this formula. However, it can be related to the scalar

`ρ̃`_{i}= (`Q`_{i−1}(`A`^{T})`r̂`_{0},`P`_{i−1}()`A``r`_{0}) = (`r̂`_{0},`Q`_{i−1}()`A``P`_{i−1}()`A``r`_{0}) = (`r̂`_{0},`r`_{i−1}).

Due to biorthogonality, `r`_{i−1} = `P`_{i−1}(** A**)

`ρ`= (_{i}`α`_{1}/`ω`_{1})(`α`_{2}/`ω`_{2})⋯(`α`_{i−1}/`ω`_{i−1})`ρ̃`_{i},

and thus

`β`=_{i}`ρ`/_{i}`ρ`_{i−1}= (`ρ̃`_{i}/`ρ̃`_{i−1})(`α`_{i−1}/`ω`_{i−1}).

A simple formula for `α _{i}` can be similarly derived. In BiCG,

`α`=_{i}`ρ`/(_{i}`p̂`_{i},) = (**Ap**_{i}`P`_{i−1}(`A`^{T})`r̂`_{0},`P`_{i−1}()`A``r`_{0})/(`T`_{i−1}(`A`^{T})`r̂`_{0},**A**T_{i−1}()`A``r`_{0}).

Similarly to the case above, only the highest-order terms of `P`_{i−1}(`A`^{T}) and `T`_{i−1}(`A`^{T}) matter in the dot products thanks to biorthogonality and biconjugacy. It happens that `P`_{i−1}(`A`^{T}) and `T`_{i−1}(`A`^{T}) have the same leading coefficient. Thus, they can be replaced simultaneously with `Q`_{i−1}(`A`^{T}) in the formula, which leads to

`α`= (_{i}`Q`_{i−1}(`A`^{T})`r̂`_{0},`P`_{i−1}()`A``r`_{0})/(`Q`_{i−1}(`A`^{T})`r̂`_{0},**A**T_{i−1}()`A``r`_{0}) =`ρ̃`_{i}/(`r̂`_{0},`A``Q`_{i−1}()`A``T`_{i−1}()`A``r`_{0}) =`ρ̃`_{i}/(`r̂`_{0},`Ap̃`_{i}).

Finally, BiCGSTAB selects `ω _{i}` to minimize

- ((
**I**−`ω`)_{i}**A**,**s**_{i}) = 0,**As**_{i}

giving the optimal value

`ω`= (_{i},**As**_{i})/(**s**_{i},**As**_{i}).**As**_{i}

BiCGSTAB can be viewed as a combination of BiCG and GMRES where each BiCG step is followed by a GMRES(1) (i.e., GMRES restarted at each step) step to repair the irregular convergence behavior of CGS, as an improvement of which BiCGSTAB was developed. However, due to the use of degree-one minimum residual polynomials, such repair may not be effective if the matrix ** A** has large complex eigenpairs. In such cases, BiCGSTAB is likely to stagnate, as confirmed by numerical experiments.

One may expect that higher-degree minimum residual polynomials may better handle this situation. This gives rise to algorithms including BiCGSTAB2^{[1]} and the more general BiCGSTAB(`l`)^{[2]}. In BiCGSTAB(`l`), a GMRES(`l`) step follows every `l` BiCG steps. BiCGSTAB2 is equivalent to BiCGSTAB(`l`) with `l` = 2.

- Van der Vorst, H. A. (1992). "Bi-CGSTAB: A Fast and Smoothly Converging Variant of Bi-CG for the Solution of Nonsymmetric Linear Systems".
*SIAM J. Sci. Stat. Comput.***13**(2): 631–644. doi:10.1137/0913035. hdl:10338.dmlcz/104566. - Saad, Y. (2003). "§7.4.2 BICGSTAB".
*Iterative Methods for Sparse Linear Systems*(2nd ed.). SIAM. pp. 231–234. ISBN 978-0-89871-534-7. **^**Gutknecht, M. H. (1993). "Variants of BICGSTAB for Matrices with Complex Spectrum".*SIAM J. Sci. Comput.***14**(5): 1020–1033. doi:10.1137/0914062.**^**Sleijpen, G. L. G.; Fokkema, D. R. (November 1993). "BiCGstab(*l*) for linear equations involving unsymmetric matrices with complex spectrum" (PDF).*Electronic Transactions on Numerical Analysis*.**1**. Kent, OH: Kent State University: 11–32. ISSN 1068-9613.