Biconjugate gradient method

In mathematics, more specifically in numerical analysis, the biconjugate gradient method is an algorithm to solve systems of linear equations

:$A\; x=\; b.,$

Unlike the conjugate gradient method, this algorithm does not require the matrix $A$ to be self-adjoint, but instead one needs to perform multiplications by the conjugate transpose $A^*$.

The algorithm

# Choose $x\_0$, $y\_0$, a regular preconditioner $M$ (frequently $M^\{-1\}=1$ is used) and $c$;
# $r\_0\; leftarrow\; b-A\; x\_0,\; s\_0\; leftarrow\; c-A^*\; y\_0,$;
# $d\_0\; leftarrow\; M^\{-1\}\; r\_0,\; f\_0\; leftarrow\; M^\{-*\}\; s\_0,$;
# for $k=0,\; 1,\; dots,$ do
# $alpha\_k\; leftarrow\; \{s^*\_k\; M^\{-1\}\; r\_k\; over\; f\_k^*\; A\; d\_k\},$;
# $x\_\{k+1\}\; leftarrow\; x\_k+\; alpha\_k\; d\_k,$ $left(\; y\_\{k+1\}\; leftarrow\; y\_k\; +\; overline\{alpha\_k\}\; f\_k\; ight),$;
# $r\_\{k+1\}\; leftarrow\; r\_k-\; alpha\_k\; A\; d\_k\; ,$, $s\_\{k+1\}\; leftarrow\; s\_k-\; overline\{alpha\_k\}\; A^*\; f\_k\; ,$ ($r\_k=b-A\; x\_k$ and $s\_k=\; c-\; A^*\; y\_k$ are the residuums);
# ;
# , .

Discussion

The BiCG method is numerically unstable, but very important from theoretical point of view: Define the iteration steps by $x\_k:=x\_j+\; P\_k\; A^\{-1\}left(b\; -\; A\; x\_j\; ight)$ and $y\_k:=y\_j+A^\{-*\}P\_k^*left(c-A^*\; y\_j\; ight)$ (

The new directions $d\_k:=\; left(1-P\_k\; ight)\; u\_k$ and $f\_k:=\; left(\; A\; left(1-\; P\_k\; ight)\; A^\{-1\}\; ight)^*\; v\_k$ then are orthogonal to the residuums: $v\_i^*\; r\_k=\; f\_i^*\; r\_k=0$ and $s\_k^*\; u\_j\; =\; s\_k^*\; d\_j=\; 0$, which themselves satisfy $r\_k=\; A\; left(\; 1-\; P\_k\; ight)\; A^\{-1\}\; r\_j$ and $s\_k=\; left(\; 1-\; P\_k\; ight)\; ^*\; s\_j$(

The biconjugate gradient method now makes a special choice and uses the setting :$u\_k:=\; M^\{-1\}\; r\_k$ and $v\_k:=M^\{-*\}\; s\_k$.This special choice allows to avoid direct evaluations of $P\_k$ and $A^\{-1\}$, and subsequently leads to the algorithm as stated above.

Properties

* If $A=\; A^*$ is self-adjoint, $y\_0=\; x\_0$ and $c=b$, then $r\_k=\; s\_k$, $d\_k=\; f\_k$, and the conjugate gradient method produces the same sequence $x\_k=\; y\_k$.

* In finite dimensions $x\_n=A^\{-1\}b$, at the latest when $P\_n=1$: The biconjugate gradient method returns the exact solution after iterating the full space and thus is a direct method.

* The sequences produced by the algorithm are biorthogonal: $f\_i^*\; A\; d\_j\; =\; 0$ and $s\_i^*\; M^\{-1\}\; r\_j=0$ for $i\; e\; j$.

* if $p\_\{j\text{'}\}$ is a polynomial with

* if $p\_\{i\text{'}\}$ is a polynomial with