Biconjugate Gradient Stabilized Method

The biconjugate gradient stabilized (BCGSTAB) method was developed to solve nonsymmetric linear systems while avoiding the often irregular convergence patterns of the conjugate gradient squared method (van der Vorst 1992). Instead of computing the conjugate gradient squared method sequence , BCGSTAB computes  where  is an th degree polynomial describing a steepest descent update.

BCGSTAB often converges about as fast as the conjugate gradient squared method (CGS), sometimes faster and sometimes not. CGS can be viewed as a method in which the biconjugate gradient method (BCG) "contraction" operator is applied twice. BCGSTAB can be interpreted as the product of BCG and repeated application of the generalized minimal residual method. At least locally, a residual vector is minimized, which leads to a considerably smoother convergence behavior. On the other hand, if the local generalized minimal residual method step stagnates, then the Krylov subspace is not expanded, and BCGSTAB will break down. This is a breakdown situation that can occur in addition to the other breakdown possibilities in the underlying BCG algorithm. This type of breakdown may be avoided by combining BCG with other methods, i.e., by selecting other values for  in the algorithm. One such alternative is BCGSTAB2 (Gutknecht 1993). More general approaches have been suggested by Sleijpen and Fokkema (1993).

Note that BCGSTAB has two stopping tests: if the method has already converged at the first test on the norm of , the subsequent update would be numerically questionable. Additionally, stopping on the first test saves a few unnecessary operations, but this is of minor importance.

BCGSTAB requires two matrix-vector products and four inner products, i.e., two inner products more than the biconjugate gradient method or the conjugate gradient squared method (van der Vorst 2003).

REFERENCES:

Barrett, R.; Berry, M.; Chan, T. F.; Demmel, J.; Donato, J.; Dongarra, J.; Eijkhout, V.; Pozo, R.; Romine, C.; and van der Vorst, H. Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods, 2nd ed. Philadelphia, PA: SIAM, 1994. http://www.netlib.org/linalg/html_templates/Templates.html.

Gutknecht, M. H. "Variants of Bi-CGSTAB for Matrices with Complex Spectrum." SIAM J. Sci. Comput. 14, 1020-1033, 1993.

Sleijpen, G. L. G. and Fokkema, D. R. "Bi-CGSTAB(l) for Linear Equations Involving Unsymmetric Matrices with Complex Spectrum." Elec. Trans. Numer. Anal. 1, 11-32, 1993.

van der Vorst, H. "Bi-CGSTAB: A Fast and Smoothly Converging Variant of Bi-CG for the Solution of Nonsymmetric Linear Systems." SIAM J. Sci. Statist. Comput. 13, 631-644, 1992.

van der Vorst, H. Iterative Krylov Methods for Large Linear Systems. Cambridge, England: Cambridge University Press, 2003.