Analysis of the finite precision bi-conjugate gradient algorithm for nonsymmetric linear systems
HTML articles powered by AMS MathViewer
- by Charles H. Tong and Qiang Ye;
- Math. Comp. 69 (2000), 1559-1575
- DOI: https://doi.org/10.1090/S0025-5718-99-01171-0
- Published electronically: August 19, 1999
- PDF | Request permission
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
- Zhaojun Bai, Error analysis of the Lanczos algorithm for the nonsymmetric eigenvalue problem, Math. Comp. 62 (1994), no. 205, 209–226. MR 1201066, DOI 10.1090/S0025-5718-1994-1201066-7
- Randolph E. Bank and Tony F. Chan, An analysis of the composite step biconjugate gradient method, Numer. Math. 66 (1993), no. 3, 295–319. MR 1246959, DOI 10.1007/BF01385699
- T. Barth and T. A. Manteuffel, Variable Metric Conjugate Gradient Methods, Proceedings of the 10th International Symposium on Matrix Analysis and Parallel Computing, Keio University, Yokohama, Japan, March 14-16, 1994.
- Jane Cullum and Anne Greenbaum, Relations between Galerkin and norm-minimizing iterative methods for solving linear systems, SIAM J. Matrix Anal. Appl. 17 (1996), no. 2, 223–247. MR 1384506, DOI 10.1137/S0895479893246765
- D. Day, Semi-duality in the two-sided Lanczos algorithm. Ph.D. Thesis, University of Californial, Berkeley, 1993.
- I. S. Duff, R. G. Grimes, and J. G. Lewis, Sparse Matrix Test Problems, ACM Trans. Math. Softw., 15:1-14 (1989).
- R. Fletcher, Conjugate gradient methods for indefinite systems, Numerical analysis (Proc. 6th Biennial Dundee Conf., Univ. Dundee, Dundee, 1975) Lecture Notes in Math., Vol. 506, Springer, Berlin-New York, 1976, pp. 73–89. MR 461857
- Roland W. Freund and Noël M. Nachtigal, QMR: a quasi-minimal residual method for non-Hermitian linear systems, Numer. Math. 60 (1991), no. 3, 315–339. MR 1137197, DOI 10.1007/BF01385726
- Gene H. Golub and Michael L. Overton, Convergence of a two-stage Richardson iterative procedure for solving systems of linear equations, Numerical analysis (Dundee, 1981) Lecture Notes in Math., vol. 912, Springer, Berlin-New York, 1982, pp. 125–139. MR 654347
- Gene H. Golub and Michael L. Overton, The convergence of inexact Chebyshev and Richardson iterative methods for solving linear systems, Numer. Math. 53 (1988), no. 5, 571–593. MR 954771, DOI 10.1007/BF01397553
- Gene H. Golub and Charles F. Van Loan, Matrix computations, Johns Hopkins Series in the Mathematical Sciences, vol. 3, Johns Hopkins University Press, Baltimore, MD, 1983. MR 733103
- A. Greenbaum, Behavior of slightly perturbed Lanczos and conjugate-gradient recurrences, Linear Algebra Appl. 113 (1989), 7–63. MR 978581, DOI 10.1016/0024-3795(89)90285-1
- A. Greenbaum, Accuracy of Computed Solutions from Conjugate-Gradient-Like Methods, PCG ’94, Matrix Analysis and Parallel Computing, Keio University, March 14-16, 1994.
- A. Greenbaum and Z. Strakoš, Predicting the behavior of finite precision Lanczos and conjugate gradient computations, SIAM J. Matrix Anal. Appl. 13 (1992), no. 1, 121–137. MR 1146656, DOI 10.1137/0613011
- A. Greenbaum, V. Druskin, and L. Knizhnerman, Private communication.
- P. Hebroni, Sur les inverses des éléments dérivables dans un anneau abstrait, C. R. Acad. Sci. Paris 209 (1939), 285–287 (French). MR 14
- R. Lehoucq, Analysis and implementation of an implicitly restarted iteration Ph.D. Thesis, Rice University, Houston, Texas, May 1995.
- Yvan Notay, On the convergence rate of the conjugate gradients in presence of rounding errors, Numer. Math. 65 (1993), no. 3, 301–317. MR 1227024, DOI 10.1007/BF01385754
- C. C. Paige, Error analysis of the Lanczos algorithm for tridiagonalizing a symmetric matrix, J. Inst. Math. Appl. 18 (1976), no. 3, 341–349. MR 501834
- C. C. Paige, Accuracy and effectiveness of the Lanczos algorithm for the symmetric eigenproblem, Linear Algebra Appl. 34 (1980), 235–258. MR 591433, DOI 10.1016/0024-3795(80)90167-6
- Y. Saad, Analysis of some Krylov subspace approximations to the matrix exponential operator, SIAM J. Numer. Anal. 29 (1992), no. 1, 209–228. MR 1149094, DOI 10.1137/0729014
- Peter Sonneveld, CGS, a fast Lanczos-type solver for nonsymmetric linear systems, SIAM J. Sci. Statist. Comput. 10 (1989), no. 1, 36–52. MR 976160, DOI 10.1137/0910004
- C. H. Tong, A Comparative Study of Preconditioned Lanczos Methods for Nonsymmetric Linear Systems, Tech. Report SAND91-9240B, Sandia National Lab., Livermore, 1992.
- L. N. Trefethen, Approximation theory and numerical linear algebra, Algorithms for approximation, II (Shrivenham, 1988) Chapman and Hall, London, 1990, pp. 336–360. MR 1071991
- H. A. van der Vorst, Bi-CGSTAB: a fast and smoothly converging variant of Bi-CG for the solution of nonsymmetric linear systems, SIAM J. Sci. Statist. Comput. 13 (1992), no. 2, 631–644. MR 1149111, DOI 10.1137/0913035
- H. A. van der Vorst, The convergence behaviour of preconditioned CG and CG-S in the presence of rounding errors, Preconditioned conjugate gradient methods (Nijmegen, 1989) Lecture Notes in Math., vol. 1457, Springer, Berlin, 1990, pp. 126–136. MR 1101632, DOI 10.1007/BFb0090905
- Qiang Ye, A convergence analysis for nonsymmetric Lanczos algorithms, Math. Comp. 56 (1991), no. 194, 677–691. MR 1068826, DOI 10.1090/S0025-5718-1991-1068826-4
Bibliographic Information
- Charles H. Tong
- Affiliation: Sandia National Laboratories, Livermore, CA 94551
- Email: chtong@california.sandia.gov
- Qiang Ye
- Affiliation: Department of Mathematics, University of Manitoba, Winnipeg, Manitoba, Canada R3T 2N2
- MR Author ID: 237891
- Email: ye@gauss.amath.umanitoba.ca
- 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. - © Copyright 2000 American Mathematical Society
- Journal: Math. Comp. 69 (2000), 1559-1575
- MSC (1991): Primary 65F10, 65N20
- DOI: https://doi.org/10.1090/S0025-5718-99-01171-0
- MathSciNet review: 1665975