×

An analysis of the composite step biconjugate gradient method. (English) Zbl 0802.65038

The paper shows that \(2\times 2\) composite steps can cure breakdowns in the biconjugate gradient matrix caused by (near) singularity of principal submatrices of the tridiagonal matrix generated by the underlying Lanczos process. In section 2, the factorization of general nonsingular tridiagonal matrices is considered. In section 3 and 4, the composite step biconjugate gradient method is derived, an analysis of its convergence is presented and a “best approximation” result is proved. In section 5, three of many possible implementations of the method are presented. Some illustrations showing the effect of roundoff error are given in the last section.

MSC:

65F10 Iterative numerical methods for linear systems

Software:

PLTMG; symrcm; CGS
PDFBibTeX XMLCite
Full Text: DOI EuDML

References:

[1] Aziz, A.K., Babu?ka, I. (1972): Part I, survey lectures on the mathematical foundations of the finite element method. In: Aziz, A.K., ed., The Mathematical Foundations of the Finite Element Method with Applications to Partial Differential Equations, pp. 1-362. Academic Press, New York
[2] Bank, R.E. (1990): PLTMG: a software package for solving elliptic partial differential equations, Users’ Guide 6.0. Front. Appl. Math. SIAM, vol. 7 · Zbl 0717.68001
[3] Bank, R.E., Bürgler, J.F., Fichtner, W., Smith, R.K. (1990): Some upwinding techniques for finite element approximations of convection-diffusion equations. Numer. Math.58, 185-202 · Zbl 0713.65066 · doi:10.1007/BF01385618
[4] Bank, R.E., Chan, T.F. (1992): A composite step bi-conjugate gradient algorithm for nonsymmetric linear systems. University of California, California · Zbl 0809.65025
[5] Bunch, J.R. (1974): Partial pivoting strategies for symmetric matrices. SIAM J. Numer. Anal.11, 521-528 · Zbl 0286.65023 · doi:10.1137/0711043
[6] Brezinski, C., Sadok, H. (1993): Lanczos-type algorithms for solving systems of linear equations. Appl. Num. Math.11, 443-473 · Zbl 0780.65020 · doi:10.1016/0168-9274(93)90087-8
[7] Brezinski, C., Zaglia, M.R., Sadok, H. (1992): A breakdown-free Lanczos type algorithm for solving linear systems. Numer. Math.63, 29-38 · Zbl 0782.65045 · doi:10.1007/BF01385846
[8] Concus, P., Golub, G.H., O’Leary, D.P. (1976): A generalized conjugate gradient method for the numerical o solution of elliptic partial differential equations. In: J.R. Bunch, D.J. Rose, eds., Sparse matrix computations, p. 309-332. Academic Press, New York
[9] Fletcher, R. (1976): Conjugate gradient methods for indefinite systems. In: G.A. Watson, ed., Numerical Analysis. Lecture Notes in Mathematics506, 73-89. Springer, Berlin Heidelberg New York · Zbl 0326.65033
[10] Freund, R.W. (1991): A transpose-free quasi-minimum residual algorithm for non-Hermitian linear systems. Tech. Rep. 91.18, RIACS. Nasa Ames Research Center, Moffett Field
[11] Freund, R.W., Golub, G.H., Nachtigal, N.M. (1991): Iterative solution of linear systems. Tech. Rep. NA-91-05. Computer Science Department, Stanford University · Zbl 0762.65019
[12] Freund, R.W., Gutknecht, M.H., Nachtigal, N.M. (1991): An implementation of the look-ahead Lanczos algorithm for non-hermitian matrices. Tech. Rep. 91.09, RIACS. Nasa Ames Research Ceneter, Moffett Field · Zbl 0770.65022
[13] Freund, R.W., Nachtigal, N.M.: QMR: a quasi residual residual method for non-Hermetian linear systems. Numer. Math. (to appear) · Zbl 0754.65034
[14] George, A., Liu, J. (1981): Computer Solution of Large Sparse Positive Definite Systems. Prentice-Hall, Englewood Cliffs, NJ · Zbl 0516.65010
[15] Gutknecht, M.H. (1990): A completed theory of the unsymmetric Lanczos process and related algorithms. Part II, Tech. Rep. 90-16, IPS Research Report, ETH Zürich · Zbl 0809.65028
[16] Gutknecht, M.H. (1990): The unsymmetric Lanczoz algorithms and their relations to Páde approximation, continued fractions and the QD algorithm. In: Preliminary Proceedings of the Copper Mountain Conference on Iterative Methods
[17] Gutknecht, M.H. (1992): A completed theory of the unsymmetric Lanczos process and related algorithms, part I. SIAM J. Mat. Anal. Appl.13, 594-639 · Zbl 0760.65039 · doi:10.1137/0613037
[18] Joubert, W. (1992): Lanczos methods for the solution of nonsymmetric systems of linear equations. SIAM J. Matrix Anal. Appl.13, 926-943 · Zbl 0758.65026 · doi:10.1137/0613056
[19] Manteuffel, T.A. (1977): An Iterative Method for Solving Nonsymmetric Linear Systems with Dynamic Estimation of Parameters, PhD Thesis. University if Illinois, Urbana
[20] Manteuffel, T.A. (1977): The Tchebychev iteration for nonsymmetric linear systems. Numer. Math.28, 307-327 · Zbl 0361.65024 · doi:10.1007/BF01389971
[21] Nachtigal, N.M.: (1991): A Look-Ahead Variant of the Lanczos Algorithm and its Application to the Quasi-Minimum Residual Methods for Non-Hermitian Linear Systems. PhD Thesis, MIT, Cambridge
[22] Paige, C.C., Saunders, M.A. (1975): Solution of sparse indefinite systems of linear equations. SIAM J. Numer. Anal.12, 617-629 · Zbl 0319.65025 · doi:10.1137/0712047
[23] Parlett, B.N. (1992): Reduction to tridiagonal form and minimal realizations. SIAM J. Matrix Anal. Appl.13, 567-593 · Zbl 0754.65040 · doi:10.1137/0613036
[24] Parlett, Taylor, D.R., Liu, Z.A. (1985): A look-ahead Lanczos, algorithm for unsymmetric matrices. Mat. Apl. Comput.44, 105-124 · Zbl 0564.65022
[25] Saad, Y. (1982): The Lanczos biorthogonalization algorithm and other oblique projection methods for solving large unsymmetric systems. SIAM J. Numer. Anal.19, 485-506 · Zbl 0483.65022 · doi:10.1137/0719031
[26] Sonneveld, P. (1989): CGS, a fast Lanczos-type solver for nonsymmetric linear systems. SIAM J. Sci. Stat. Comput.10, 36-52 · Zbl 0666.65029 · doi:10.1137/0910004
[27] Tong, C.H. (1992): A comparative study of preconditioned Lanczos methods for nonsymmetric linear systems. Tech. Rep. SAND91-8402 UC-404. Sandia National Laboratories, Albuquerque
[28] Van Der Vorst, H.A.: BI-CGSTAB: a fast and smoothly converging variant of BI-CG for the solution of nonsymmetric linear systems. SIAM J. Sci. Stat. Comput. (to appear) · Zbl 0761.65023
[29] Wilkinson, J.H. (1965): The Algebraic Eigenvalue Problem. Oxford University Press, Oxford · Zbl 0258.65037
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.