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)
A breakdown-free Lanczos type algorithm for solving linear systems. (English) Zbl 0739.65027

Lanczos type algorithms for solving systems of linear equations have their foundations in the theory of formal orthogonal polynomials and the method of moments which leads to a determinantal formula for their iterates. The various Lanczos type algorithms mainly differ by the way of computing the coefficients entering into the recurrence formulae. If the denominator in the formula for one of these coefficients is zero, then a breakdown occurs in the algorithm, and it must be stopped. Such a breakdown is in fact due to the non-existence of some orthogonal polynomial.

In this paper we show how to jump over such a singularity by computing the next existing orthogonal polynomial by the block bordering method. The resulting algorithm, called MRZ, is equivalent to the nongeneric BIODIR algorithm (which is a look-ahead Lanczos type algorithm), but our derivation is much simpler.

MSC:
65F10Iterative methods for linear systems
65F25Orthogonalization (numerical linear algebra)
References:
[1]Brezinski, C. (1984): Some determinantal identities in a vector space, with applications, In: H. Werner and H.J. Bünger eds., Padé Approximations and its Applications. Bad-Honnef 1983, LNM 1071. Springer, Berlin Heidelberg New York, pp. 1-11
[2]Brezinski, C. (1980): Padé-type approximation and general orthogonal polynomials. ISMM, Vol. 50. Birkhäuser, Basel
[3]Brezinski, C. (1988): Other manifestations of the Schur complement. Linear Alg. Appl,111, 231-247 · Zbl 0662.65037 · doi:10.1016/0024-3795(88)90062-6
[4]Brezinski, C. (1991): Biorthogonality and its Applications to Numerical Analysis. Dekker, New York
[5]Brezinski, C. (1992): CGM A whole class of Lanczos-type solvers for linear systems. Submitted
[6]Brezinski, C., Sadok, H. (1992): Lanczos type algorithms for solving systems of linear equations. Submitted
[7]Brezinski, C., Sadok, H. (1991): Avoiding breakdown in the CGS algorithm, Numerical Algorithms1, 199-206 · Zbl 0766.65024 · doi:10.1007/BF02142321
[8]Brezinski, C., Redivo Zaglia, M. (1991): A new presentation of orthogonal polynomials with application to their computation. Numerical Algorithms1, 207-222 · Zbl 0752.65011 · doi:10.1007/BF02142322
[9]Brezinski, C., Redivo Zaglia, M. (1992): Treatment of near-breakdown in the CGS algorithm. Submitted
[10]Brezinski, C., Redivo Zaglia, M., Sadok, H. (1991): Avoiding breakdown and near-breakdown in Lanczos type algorithms. Numerical Algorithms1, 261-284 · Zbl 0748.65033 · doi:10.1007/BF02142326
[11]Brezinski, C., Redivo Zaglia, M., Sadok, H. (1992): Addendum to ?Avoiding breakdown and near-breakdown in Lanczos type algorithms?. Numerical Algorithms2, 133-136 · Zbl 0769.65014 · doi:10.1007/BF02145381
[12]Draux, A. (1983): Polynômes Orthogonaux Formels. Applications, LNM 974. Springer, Berlin Heidelberg New York.
[13]Faddeeva, V.N. (1959): Computational methods of linear algebra. Dover, New York
[14]Fletcher, R. (1976): Conjugate gradient methods for indefinite systems. In: G.A. Watson ed., Numerical Analysis, LNM 506. Springer, Berlin Heidelberg New York, pp. 73-89
[15]Gutknecht, M.H. (1992): A completed theory of the unsymmetric Lanczos process and related algorithms. Part I. SIAM J. Matrix Anal. Appl.13, 594-639 · Zbl 0760.65039 · doi:10.1137/0613037
[16]Gutknecht, M.H. (1992): The unsymmetric Lanczos algorithms and their relations to Pade approximation, continued fractions, and the qd algorithm. To appear
[17]Hendriksen, E., Van Rossum, H. (1982): Moment methods in Padé approximation. J. Approx. Theory35, 250-263 · Zbl 0489.41017 · doi:10.1016/0021-9045(82)90007-7
[18]Keller, H.B. (1983): The bordering algorithm and path following near singular points of higher nullity. SIAM J. Sci. Stat. Comput.4, 573-582 · Zbl 0536.65017 · doi:10.1137/0904039
[19]Joubert, W.D., Manteufel, T.A. (1990): Iterative methods for nonsymmetric linear systems. In: D.R. Kincaid, L.J. Hayes eds., Iterative methods for large linear systems Academic Press, New York, pp. 149-171
[20]Lanczos, C. (1950): An iteration method for the solution of the eigenvalue problem of linear differential and integral operators. J. Res. Natl. Bur. Stand.45, 225-282
[21]Lanczos, C. (1952): Solution of systems of linear equations by minimized iterations. J. Res. Natl. Bur. Stand.49, 33-53
[22]Parlett, B.N., Taylor, D.R., Liu, Z.A. (1985): A look-ahead Lanczos algorithm for unsymmetric matrices. Math. Comput.44, 105-124
[23]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
[24]Struble, G.W. (1963): Orthogonal polynomials: variable-signed weight functions. Numer. Math.5, 88-94 · Zbl 0107.05502 · doi:10.1007/BF01385881
[25]Van der Vorst, H.A. (1992): Bi-CGSTAB: a fast and smoothly converging variant of Bi-CG for the solution of nonsymmetric linear systems. SIAM J. Sci. Stat. Comput.13, 631-644 · Zbl 0761.65023 · doi:10.1137/0913035
[26]Vorobyev, Yu.V. (1965): Method of moments in applied mathematics. Gordon and Breach, New York
[27]Young, D.M., Jea, K.C. (1984): Generalized conjugate-gradient acceleration of nonsymmetrizable iterative methods. Linear Algebra Appl.34, 159-194 · Zbl 0463.65025 · doi:10.1016/0024-3795(80)90165-2