Numerical analysis Iterative methods for linear systems Proposition

Biconjugate gradient stabilized method

Builds on Invertible matrix Biconjugate gradient method Krylov subspace Generalized minimal residual method Preconditioner Iterative method

Statement

Let $A$ be a real invertible $n \times n$ matrix, let $b \in \R^n$ , and let $x_0 \in \R^n$ with $r_0 = b - A x_0$ . Choose $\hat{r}_0 \in \R^n$ with $\hat{r}_0^T r_0 \ne 0$ , and set $p_0 = r_0$ . The biconjugate gradient stabilized method (BiCGSTAB) computes, for $k = 0, 1, \dots$ , $v_k = A p_k, \quad \alpha_k = \frac{\hat{r}_0^T r_k}{\hat{r}_0^T v_k}, \quad s_k = r_k - \alpha_k v_k, \quad t_k = A s_k, \quad \omega_k = \frac{t_k^T s_k}{t_k^T t_k},$ $x_{k+1} = x_k + \alpha_k p_k + \omega_k s_k, \quad r_{k+1} = s_k - \omega_k t_k,$ $\beta_k = \frac{\hat{r}_0^T r_{k+1}}{\hat{r}_0^T r_k} \cdot \frac{\alpha_k}{\omega_k}, \quad p_{k+1} = r_{k+1} + \beta_k (p_k - \omega_k v_k).$ Suppose that all denominators are nonzero up to step $m$ . Then in exact arithmetic, for $k \le m$ :

$r_k = b - A x_k$ , and $r_k = Q_k(A) P_k(A) r_0$ , where $P_k$ is the residual polynomial of the biconjugate gradient method with shadow residual $\hat{r}_0$ , and $Q_k(t) = \prod_{j=0}^{k-1} (1 - \omega_j t)$ ;
each $\omega_k$ minimizes $\norm{s_k - \omega t_k}_2$ over $\omega \in \R$ ;
each step uses two products with $A$ and none with $A^T$ .

Remarks

The residual polynomial $P_k$ of BiCG has degree $k$ and value $1$ at $0$ , so $r_k$ comes from a polynomial of degree $2k$ in the Krylov subspace $\mathcal{K}_{2k+1}(A, r_0)$ . The recurrences come from writing the BiCG coefficients in terms of the inner products $\hat{r}_0^T Q_k(A) P_k(A) r_0$ , which needs no $A^T$ because $\hat{r}_0^T Q_k(A) = (Q_k(A^T) \hat{r}_0)^T$ . The factor $Q_k$ is a product of local one-step minimal residual steps, which smooths the erratic convergence of BiCG and of the method CGS. Example: if $r_0$ is an eigenvector of $A$ for $\lambda$ , then $v_0 = \lambda r_0$ , $\alpha_0 = 1/\lambda$ and $s_0 = 0$ , so $x_0 + \alpha_0 p_0$ already solves the system. In that case $t_0 = 0$ and $\omega_0$ is undefined, and an implementation stops when $s_k$ is small. The method can still break down, when $\hat{r}_0^T r_k = 0$ or $\omega_k = 0$ . It can stagnate when the $\omega_k$ are close to $0$ , which tends to happen when $A$ has eigenvalues with large imaginary parts.

Going deeper

For a student

BiCGSTAB, due to van der Vorst, is with restarted GMRES one of the default Krylov iterative methods for nonsymmetric sparse systems. Its memory and work per step are fixed, in contrast with full GMRES, but it has no global minimization property. It is used with a preconditioner, typically an incomplete LU factorization. Variants such as BiCGSTAB( $\ell$ ) use minimal residual polynomials of higher degree to handle complex eigenvalues better.

Reading path

To understand this page from the ground up, read these 49 pages in order. The foundations come first.

Chebyshev polynomials object
Condition number concept
Eigenvalue concept
Hermitian matrix concept
Hessenberg matrix concept
Incomplete Cholesky factorization concept
Invertible matrix concept
Iterative method concept
Krylov subspace concept
Matrix definition
Orthonormal basis concept
Positive definite matrix concept
Preconditioner concept
Spectral radius concept
Symmetric matrix concept
System of linear equations concept
Transpose concept
Tridiagonal matrix concept
Vector space definition
Modified Richardson iteration statement
Transpose definition
Lanczos algorithm statement
Inner product definition
Linear combination definition
Linear map definition
Linear subspace definition
Norm definition
Inner product space definition
Orthogonal vectors definition
Linear independence definition
Endomorphism definition
Linear span definition
Chebyshev iteration statement
Sum of subspaces definition
Orthonormal family definition
Norm induced by an inner product definition
Orthogonal complement definition
Direct sum of subspaces definition
Conjugate gradient method statement
Gram–Schmidt process concept
A space is the direct sum of a subspace and its orthogonal complement statement
Projection definition
Biconjugate gradient method statement
Orthogonal projection definition
Arnoldi iteration statement
Orthogonal projection is the closest point statement
Least squares concept
Generalized minimal residual method statement
Biconjugate gradient stabilized method statement

Tag	`MA64H1RTP1`
URI	`m2://MA64H1RTP1`
Kind	statement, proposition
Writing	W0 stub
MSC	65F10
Status	This copy of the site has no build data. Run `m2 status MA64H1RTP1`.
About	Iterative method, Biconjugate gradient method
Uses	Invertible matrix, Biconjugate gradient method, Krylov subspace, Generalized minimal residual method, Preconditioner, Iterative method
Same as	Wikidata Q4903720 Wikipedia Biconjugate gradient stabilized method