zbMATH — the first resource for mathematics

Examples
Geometry Search for the term Geometry in any field. Queries are case-independent.
Funct* Wildcard queries are specified by * (e.g. functions, functorial, etc.). Otherwise the search is exact.
"Topological group" Phrases (multi-words) should be set in "straight quotation marks".
au: Bourbaki & ti: Algebra Search for author and title. The and-operator & is default and can be omitted.
Chebyshev | Tschebyscheff The or-operator | allows to search for Chebyshev or Tschebyscheff.
"Quasi* map*" py: 1989 The resulting documents have publication year 1989.
so: Eur* J* Mat* Soc* cc: 14 Search for publications in a particular source with a Mathematics Subject Classification code (cc) in 14.
"Partial diff* eq*" ! elliptic The not-operator ! eliminates all results containing the word elliptic.
dt: b & au: Hilbert The document type is set to books; alternatively: j for journal articles, a for book articles.
py: 2000-2015 cc: (94A | 11T) Number ranges are accepted. Terms can be grouped within (parentheses).
la: chinese Find documents in a given language. ISO 639-1 language codes can also be used.

Operators
a & b logic and
a | b logic or
!ab logic not
abc* right wildcard
"ab c" phrase
(ab c) parentheses
Fields
any anywhere an internal document identifier
au author, editor ai internal author identifier
ti title la language
so source ab review, abstract
py publication year rv reviewer
cc MSC code ut uncontrolled term
dt document type (j: journal article; b: book; a: book article)
An analysis of the composite step biconjugate gradient method. (English) Zbl 0802.65038
The paper shows that 2×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:
65F10Iterative methods for linear systems
Software:
PLTMG
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
[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
[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
[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
[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
[13]Freund, R.W., Nachtigal, N.M.: QMR: a quasi residual residual method for non-Hermetian linear systems. Numer. Math. (to appear)
[14]George, A., Liu, J. (1981): Computer Solution of Large Sparse Positive Definite Systems. Prentice-Hall, Englewood Cliffs, NJ
[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
[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
[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)
[29]Wilkinson, J.H. (1965): The Algebraic Eigenvalue Problem. Oxford University Press, Oxford