Analysis of the finite precision biconjugate gradient algorithm for nonsymmetric linear systems
Authors:
Charles H. Tong and Qiang Ye
Journal:
Math. Comp. 69 (2000), 15591575
MSC (1991):
Primary 65F10, 65N20
Published electronically:
August 19, 1999
MathSciNet review:
1665975
Fulltext PDF Free Access
Abstract 
References 
Similar Articles 
Additional Information
Abstract: In this paper we analyze the biconjugate 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 biconjugate 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 nearbreakdowns 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.
 [1]
Zhaojun
Bai, Error analysis of the Lanczos
algorithm for the nonsymmetric eigenvalue problem, Math. Comp. 62 (1994), no. 205, 209–226. MR 1201066
(94c:65045), http://dx.doi.org/10.1090/S00255718199412010667
 [2]
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
(94i:65043), http://dx.doi.org/10.1007/BF01385699
 [3]
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 1416, 1994.
 [4]
Jane
Cullum and Anne
Greenbaum, Relations between Galerkin and normminimizing iterative
methods for solving linear systems, SIAM J. Matrix Anal. Appl.
17 (1996), no. 2, 223–247. MR 1384506
(97b:65035), http://dx.doi.org/10.1137/S0895479893246765
 [5]
D. Day, Semiduality in the twosided Lanczos algorithm. Ph.D. Thesis, University of Californial, Berkeley, 1993.
 [6]
I. S. Duff, R. G. Grimes, and J. G. Lewis, Sparse Matrix Test Problems, ACM Trans. Math. Softw., 15:114 (1989).
 [7]
R.
Fletcher, Conjugate gradient methods for indefinite systems,
Numerical analysis (Proc 6th Biennial Dundee Conf., Univ. Dundee, Dundee,
1975) Springer, Berlin, 1976, pp. 73–89. Lecture Notes in
Math., Vol. 506. MR 0461857
(57 #1841)
 [8]
Roland
W. Freund and Noël
M. Nachtigal, QMR: a quasiminimal residual method for
nonHermitian linear systems, Numer. Math. 60 (1991),
no. 3, 315–339. MR 1137197
(92g:65034), http://dx.doi.org/10.1007/BF01385726
 [9]
Gene
H. Golub and Michael
L. Overton, Convergence of a twostage Richardson iterative
procedure for solving systems of linear equations, Numerical analysis
(Dundee, 1981) Lecture Notes in Math., vol. 912, Springer,
BerlinNew York, 1982, pp. 125–139. MR 654347
(83f:65045)
 [10]
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
(90b:65054), http://dx.doi.org/10.1007/BF01397553
 [11]
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
(85h:65063)
 [12]
A.
Greenbaum, Behavior of slightly perturbed Lanczos and
conjugategradient recurrences, Linear Algebra Appl.
113 (1989), 7–63. MR 978581
(90e:65044), http://dx.doi.org/10.1016/00243795(89)902851
 [13]
A. Greenbaum, Accuracy of Computed Solutions from ConjugateGradientLike Methods, PCG '94, Matrix Analysis and Parallel Computing, Keio University, March 1416, 1994.
 [14]
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
(92j:65043), http://dx.doi.org/10.1137/0613011
 [15]
A. Greenbaum, V. Druskin, and L. Knizhnerman, Private communication.
 [16]
Cornelius
Lanczos, Solution of systems of linear equations by
minimizediterations, J. Research Nat. Bur. Standards
49 (1952), 33–53. MR 0051583
(14,501g)
 [17]
R. Lehoucq, Analysis and implementation of an implicitly restarted iteration Ph.D. Thesis, Rice University, Houston, Texas, May 1995.
 [18]
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
(94j:65050), http://dx.doi.org/10.1007/BF01385754
 [19]
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 0501834
(58 #19082)
 [20]
C.
C. Paige, Accuracy and effectiveness of the Lanczos algorithm for
the symmetric eigenproblem, Linear Algebra Appl. 34
(1980), 235–258. MR 591433
(82b:65025), http://dx.doi.org/10.1016/00243795(80)901676
 [21]
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
(92m:65050), http://dx.doi.org/10.1137/0729014
 [22]
Peter
Sonneveld, CGS, a fast Lanczostype solver for nonsymmetric linear
systems, SIAM J. Sci. Statist. Comput. 10 (1989),
no. 1, 36–52. MR 976160
(89k:65052), http://dx.doi.org/10.1137/0910004
 [23]
C. H. Tong, A Comparative Study of Preconditioned Lanczos Methods for Nonsymmetric Linear Systems, Tech. Report SAND919240B, Sandia National Lab., Livermore, 1992.
 [24]
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
(91j:65063)
 [25]
H.
A. van der Vorst, BiCGSTAB: a fast and smoothly converging variant
of BiCG for the solution of nonsymmetric linear systems, SIAM J. Sci.
Statist. Comput. 13 (1992), no. 2, 631–644. MR 1149111
(92j:65048), http://dx.doi.org/10.1137/0913035
 [26]
H.
A. van der Vorst, The convergence behaviour of preconditioned CG
and CGS 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
(92a:65141), http://dx.doi.org/10.1007/BFb0090905
 [27]
Qiang
Ye, A convergence analysis for
nonsymmetric Lanczos algorithms, Math.
Comp. 56 (1991), no. 194, 677–691. MR 1068826
(91m:65115), http://dx.doi.org/10.1090/S00255718199110688264
 [1]
 Z. Bai, Error Analysis of the Lanczos Algorithm for the Nonsymmetric Eigenvalue Problem, Math. Comp., 62:209226 (1994). MR 94c:65045
 [2]
 R. E. Bank and T. F. Chan, An Analysis of the Composite Step Biconjugate Gradient Algorithm for Solving nonsymmetric Systems, Numer. Math., 66:295319 (1993). MR 94i:65043
 [3]
 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 1416, 1994.
 [4]
 J. Cullum and A. Greenbaum, Relation between Galerkian and normminimizing iterative methods for solving linear systems SIAM J. Matrix Anal. Appl. 17:223247 (1996). MR 97b:65035
 [5]
 D. Day, Semiduality in the twosided Lanczos algorithm. Ph.D. Thesis, University of Californial, Berkeley, 1993.
 [6]
 I. S. Duff, R. G. Grimes, and J. G. Lewis, Sparse Matrix Test Problems, ACM Trans. Math. Softw., 15:114 (1989).
 [7]
 R. Fletcher, Conjugate Gradient Methods for Indefinite Systems, in Proc. Dundee Conference on Numerical Analysis, 1975, Lecture Notes in Mathematics 506, G. A. Watson, ed., SpringerVerlag, Berlin, pp. 7389 (1976). MR 57:1841
 [8]
 R. W. Freund and N. M. Nachtigal, QMR : a Quasiminimal Residual Method for nonHermitian Linear Systems, Numer. Math., 60:315339 (1991). MR 92g:65034
 [9]
 G. H. Golub and M. L. Overton, Convergence of a twostage Richardson iterative procedure for solving systems of linear equations. in Numerical Analysis, Lect. Notes Math 912, (ed. G.A. Watson), Springer, New York Heidelberg Berlin pp.128139. MR 83f:65045
 [10]
 G. H. Golub and M. L. Overton, The convergence of inexact Chebyshev and Richardson iterative methods for solving linear systems. Numer. Math. 53:571593 (1988). MR 90b:65054
 [11]
 G. H. Golub, C. F. Van Loan, Matrix Computations, The Johns Hopkins University Press, Baltimore, 1983. MR 85h:65063
 [12]
 A. Greenbaum, Behavior of Slightly Perturbed Lanczos and ConjugateGradient Recurrences, Lin. Alg. and its Appl., 113:763 (1989). MR 90e:65044
 [13]
 A. Greenbaum, Accuracy of Computed Solutions from ConjugateGradientLike Methods, PCG '94, Matrix Analysis and Parallel Computing, Keio University, March 1416, 1994.
 [14]
 A. Greenbaum and Z. Strakos, Predicting the behavior of finite precision Lanczos and Conjugate Gradient computations, SIAM J. Matrix Anal. Appl. 13:121137 (1992). MR 92j:65043
 [15]
 A. Greenbaum, V. Druskin, and L. Knizhnerman, Private communication.
 [16]
 C. Lanczos, Solution of Systems of Linear Equations by Minimized Iterations, J. Res. Natl. Bur. Stand. 49:3353 (1952). MR 14:501g
 [17]
 R. Lehoucq, Analysis and implementation of an implicitly restarted iteration Ph.D. Thesis, Rice University, Houston, Texas, May 1995.
 [18]
 Y. Notay, On the convergence rate of the conjugate gradients in presence of rounding errors, Numer. Math. 65:301317 (1993). MR 94j:65050
 [19]
 C. Paige, Error Analysis of the Lanczos Algorithm for Tridiagonalizing a Symmetric Matrix, J. Inst. Math. Appl., 18:341349 (1976). MR 58:19082
 [20]
 C. Paige, Accuracy and Effectiveness of the Lanczos Algorithm for the Symmetric Eigenproblem, Linear Alg. Appl. 34(1980):235258. MR 82b:65025
 [21]
 Y. Saad, Analysis of some Krylov subspace approximations to the matrix exponential operators, SIAM J. Numer. Anal. 29:209228 (1992). MR 92m:65050
 [22]
 P. Sonneveld, CGS, a Fast Lanczostype Solver for Nonsymmetric Linear Systems, SIAM J. Sci. Stat. Comput., 10:3652 (1989). MR 89k:65052
 [23]
 C. H. Tong, A Comparative Study of Preconditioned Lanczos Methods for Nonsymmetric Linear Systems, Tech. Report SAND919240B, Sandia National Lab., Livermore, 1992.
 [24]
 L. N. Trefethen, Approximation theory and numerical linear algebra, in Algorithms for Approximation II, J.C. Mason and M.G. Cox eds., Chapman and Hall, London, 1990, pp. 336360. MR 91j:65063
 [25]
 H. A. Van der Vorst, BiCGSTAB : A Fast and Smoothly Converging Variant of BiCG for the Solution of Nonsymmetric Linear Systems, SIAM J. Sci. Stat. Comput., 13:631644 (1992). MR 92j:65048
 [26]
 H. A. Van der Vorst, The convergence behaviour of preconditioned CG and CGS in Lect. Notes in Math. 1457, ed. O. Axelsson and L. Kolotilina, pp. 121136, Springer, Berlin Heidelberg New York (1990), pp. 199. MR 92a:65141
 [27]
 Q. Ye, A convergence analysis of nonsymmetric Lanczos algorithms, Math. Comp. 56:677691 (1991). MR 91m:65115
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
Email:
chtong@california.sandia.gov
Qiang Ye
Affiliation:
Department of Mathematics, University of Manitoba, Winnipeg, Manitoba, Canada R3T 2N2
Email:
ye@gauss.amath.umanitoba.ca
DOI:
http://dx.doi.org/10.1090/S0025571899011710
PII:
S 00255718(99)011710
Keywords:
Biconjugate 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
