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

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

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

---

1. Choose $x\_0$, $y\_0$, a regular preconditioner $M$ (frequently $M^\{-1\}=1$ is used) and $c$;
2. $r\_0\; \backslash leftarrow\; b-A\; x\_0,\; s\_0\; \backslash leftarrow\; c-A^*\; y\_0\backslash ,$;
3. $d\_0\; \backslash leftarrow\; M^\{-1\}\; r\_0,\; f\_0\; \backslash leftarrow\; M^\{-*\}\; s\_0\backslash ,$;
4. for $k=0,\; 1,\; \backslash dots\backslash ,$ do
5. $\backslash alpha\_k\; \backslash leftarrow\; \{s^*\_k\; M^\{-1\}\; r\_k\; \backslash over\; f\_k^*\; A\; d\_k\}\backslash ,$;
6. $x\_\{k+1\}\; \backslash leftarrow\; x\_k+\; \backslash alpha\_k\; d\_k\backslash ,$ $\backslash left(\; y\_\{k+1\}\; \backslash leftarrow\; y\_k\; +\; \backslash overline\{\backslash alpha\_k\}\; f\_k\; \backslash right)\backslash ,$;
7. $r\_\{k+1\}\; \backslash leftarrow\; r\_k-\; \backslash alpha\_k\; A\; d\_k\; \backslash ,$, $s\_\{k+1\}\; \backslash leftarrow\; s\_k-\; \backslash overline\{\backslash alpha\_k\}\; A^*\; f\_k\; \backslash ,$ ($r\_k=b-A\; x\_k$ and $s\_k=\; c-\; A^*\; y\_k$ are the residuums);
8. $\backslash beta\_k\; \backslash leftarrow\; \{s\_\{k+1\}^*\; M^\{-1\}\; r\_\{k+1\}\; \backslash over\; s^*\_k\; M^\{-1\}\; r\_k\}\backslash ,$;
9. $d\_\{k+1\}\; \backslash leftarrow\; M^\{-1\}\; r\_\{k+1\}\; +\; \backslash beta\_k\; d\_k\backslash ,$, $f\_\{k+1\}\; \backslash leftarrow\; M^\{-*\}\; s\_\{k+1\}\; +\; \backslash overline\{\backslash beta\_k\}\; f\_k\backslash ,$.

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\}\backslash left(b\; -\; A\; x\_j\; \backslash right)$ and $y\_k:=y\_j+A^\{-*\}P\_k^*\backslash left(c-A^*\; y\_j\; \backslash right)$ (

$P\_k:=\; \backslash mathbf\{u\_k\}\; \backslash left(\backslash mathbf\{v\_k\}^*\; A\; \backslash mathbf\{u\_k\}\; \backslash right)^\{-1\}\; \backslash mathbf\{v\_k\}^*\; A$,

where $\backslash mathbf\{u\_k\}=\backslash left(u\_0,\; u\_1,\; \backslash dots\; u\_\{k-1\}\; \backslash right)$ and $\backslash mathbf\{v\_k\}=\backslash left(v\_0,\; v\_1,\; \backslash dots\; v\_\{k-1\}\; \backslash right)$. These related projections may be iterated themselves, as

$P\_\{k+1\}=\; P\_k+\; \backslash left(\; 1-P\_k\backslash right)\; u\_k\; \backslash otimes\; \{v\_k^*\; A\backslash left(1-P\_k\; \backslash right)\; \backslash over\; v\_k^*\; A\backslash left(1-P\_k\; \backslash right)\; u\_k\}$.

The new directions $d\_k:=\; \backslash left(1-P\_k\; \backslash right)\; u\_k$ and $f\_k:=\; \backslash left(\; A\; \backslash left(1-\; P\_k\; \backslash right)\; A^\{-1\}\; \backslash right)^*\; 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\; \backslash left(\; 1-\; P\_k\; \backslash right)\; A^\{-1\}\; r\_j$ and $s\_k=\; \backslash left(\; 1-\; P\_k\; \backslash right)\; ^*\; 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\; \backslash ne\; j$.

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

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

Numerical linear algebra | BiCG-Verfahren