Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



Analysis of the finite precision
bi-conjugate gradient algorithm
for nonsymmetric linear systems

Authors: Charles H. Tong and Qiang Ye
Journal: Math. Comp. 69 (2000), 1559-1575
MSC (1991): Primary 65F10, 65N20
Published electronically: August 19, 1999
MathSciNet review: 1665975
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: In this paper we analyze the bi-conjugate gradient algorithm in finite precision arithmetic, and suggest reasons for its often observed robustness. By using a tridiagonal structure, which is preserved by the finite precision bi-conjugate gradient iteration, we are able to bound its residual norm by a minimum polynomial of a perturbed matrix (i.e. the residual norm of the exact GMRES applied to a perturbed matrix) multiplied by an amplification factor. This shows that occurrence of near-breakdowns or loss of biorthogonality does not necessarily deter convergence of the residuals provided that the amplification factor remains bounded. Numerical examples are given to gain insights into these bounds.

References [Enhancements On Off] (What's this?)

Similar Articles

Retrieve articles in Mathematics of Computation of the American Mathematical Society with MSC (1991): 65F10, 65N20

Retrieve articles in all journals with MSC (1991): 65F10, 65N20

Additional Information

Charles H. Tong
Affiliation: Sandia National Laboratories, Livermore, CA 94551

Qiang Ye
Affiliation: Department of Mathematics, University of Manitoba, Winnipeg, Manitoba, Canada R3T 2N2

Keywords: Bi-conjugate gradient algorithm, error analysis, convergence analysis, nonsymmetric linear systems
Received by editor(s): October 6, 1998
Published electronically: August 19, 1999
Additional Notes: The first author’s research was supported by Research Grant Council of Hong Kong.
The second author’s research was supported by Natural Sciences and Engineering Research Council of Canada. Part of this work was completed while this author visited Stanford University during the summer of 1995. He would like to thank Professor Gene Golub for providing this opportunity and for his great hospitality.
Article copyright: © Copyright 2000 American Mathematical Society