TOPICS
Search

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 i|->P_i^2(A)r^((0)), BCGSTAB computes i|->Q_i(A)P_i(A)r^((0)) where Q is an ith 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 omega_i 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 s, 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).


See also

Biconjugate Gradient Method, Chebyshev Iteration, Conjugate Gradient Method on the Normal Equations Conjugate Gradient Method, Conjugate Gradient Squared Method, Generalized Minimal Residual Method, Linear System of Equations, Minimal Residual Method, Quasi-Minimal Residual Method Stationary Iterative Method, Symmetric LQ Method

Portions of this entry contributed by Noel Black and Shirley Moore, adapted from Barrett et al. (1994) (author's link)

Explore with Wolfram|Alpha

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.

Referenced on Wolfram|Alpha

Biconjugate Gradient Stabilized Method

Cite this as:

Black, Noel; Moore, Shirley; and Weisstein, Eric W. "Biconjugate Gradient Stabilized Method." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/BiconjugateGradientStabilizedMethod.html

Subject classifications