Biconjugate gradient method

The biconjugate gradient method is an algorithm to solve a particular system of linear equations $Ax=b$. In contrary to the conjugate gradient method the algorithm does not require the matrix $A$ to be symmetric, but requires to additionally apply $A^{*}$.

Biconjugate gradient algorithm

The regular preconditioner $M$ may be chosen arbitrarily (so $M^{-1}=1$ is frequently used).

1. Choose $x_{0},y_{0}$ and let $r_{0}\leftarrow b-Ax_{0},s_{0}\leftarrow c-A^{*}y_{0}$;
2. $d_{0}\leftarrow M^{-1}r_{0},f_{0}\leftarrow M^{-*}s_{0}$;
3. for $k=0,1,\dots$ do
4. $\alpha _{k}\leftarrow {s_{k}^{*}M^{-1}r_{k} \over f_{k}^{*}Ad_{k}}$;
5. $x_{k+1}\leftarrow x_{k}+\alpha _{k}d_{k}$ $\left(y_{k+1}\leftarrow y_{k}+{\overline {\alpha _{k}}}f_{k}\right)$;
6. $r_{k+1}\leftarrow r_{k}-\alpha _{k}Ad_{k}$, $s_{k+1}\leftarrow s_{k}-{\overline {\alpha _{k}}}A^{*}f_{k}$;
7. $\beta _{k}\leftarrow {s_{k+1}^{*}M^{-1}r_{k+1} \over s_{k}^{*}M^{-1}r_{k}}$;
8. $d_{k+1}\leftarrow M^{-1}r_{k+1}+\beta _{k}d_{k}$, $f_{k+1}\leftarrow M^{-*}s_{k+1}+{\overline {\beta _{k}}}f_{k}$.

The algorithm is stopped if $r_{n}=0$ or $s_{n}=0$, and $x_{n}$ then is the required solution of the system $Ax=b$ ($y_{n}$ solves the dual problem $A^{*}y=c$). In finite dimensional spaces the algorithm always terminates, as $n\leq dim$ may be proven.

The sequences produced by the algorithm are biorthogonal: $f_{i}^{*}Ad_{j}=0$ and $s_{i}^{*}M^{-1}r_{j}=0$ for $i\neq j$.

If $A=A^{*}$ is symmetric and $y_{0}=x_{0}$ is chosen, then $r_{k}=s_{k}$, $d_{k}=f_{k}$, and $x_{k}=y_{k}$ is the same sequence as produced by the conjugate gradient method.