Biconjugate gradient method

From Wikipedia, the free encyclopedia

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 *$ .

[edit] 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 \right)\,$ ;
$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);
$\beta_k \leftarrow {s_{k+1}^* M^{-1} r_{k+1} \over s^*_k M^{-1} r_k}\,$ ;
$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\,$ .

[edit] 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 \right)$ and $y_k:=y_j+A^{-*}P_k^*\left(c-A^* y_j \right)$ ( $j < k$ ) using the related projection

$P_k:= \mathbf{u_k} \left(\mathbf{v_k}^* A \mathbf{u_k} \right)^{-1} \mathbf{v_k}^* A$ ,

where $\mathbf{u_k}=\left(u_0, u_1, \dots u_{k-1} \right)$ and $\mathbf{v_k}=\left(v_0, v_1, \dots v_{k-1} \right)$ . These related projections may be iterated themselves, as

$P_{k+1}= P_k+ \left( 1-P_k\right) u_k \otimes {v_k^* A\left(1-P_k \right) \over v_k^* A\left(1-P_k \right) u_k}$ .

The new directions $d_k:= \left(1-P_k \right) u_k$ and $f_k:= \left( A \left(1- P_k \right) A^{-1} \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 \left( 1- P_k \right) A^{-1} r_j$ and $s_k= \left( 1- P_k \right) ^* s_j$ ( $i, j < k$ ).

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.

[edit] 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 \ne j$ .

if $p j'$ is a polynomial with $deg\left( p_{j'} \right) +j <k$ , then $s_k^* p_{j'}\left(M^{-1} A \right) u_j=0$ . The algorithm thus produces projections onto the Krylov subspace;