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)
Breakdowns in the implementation of the Lánczos method for solving linear systems. (English) Zbl 0871.65025
The Lanczos procedure for solving linear systems is considered via formal orthogonal polynomials. Two types of breakdown are analyzed, i. e. “true” and “ghost” breakdowns. Ways to overcome these breakdowns are reviewed. Near-breakdowns are also discussed.

MSC:
65F10Iterative methods for linear systems
Software:
na5; na1
WorldCat.org
Full Text: DOI
References:
[1] Lánczos, C.: An iteration method for the solution of the eigenvalue problem of linear differential and integral operators. J. res. Natl. bur. Stand. 45, 255-282 (1950)
[2] Kardos, I.: Scientists face to face. (1978)
[3] Lánczos, C.: Solution of systems of linear equations by minimized iterations. J. res. Natl. bur. Stand. 49, 33-53 (1952)
[4] Hestenes, M. R.; Stiefel, E.: Methods of conjugate gradients for solving linear systems. J. res. Natl. bur. Stand. 49, 409-436 (1952) · Zbl 0048.09901
[5] Hestenes, M. R.: The conjugate-gradient method for solving linear systems. Proceedings of the sixth symposium on applied mathematics, 83-102 (1956) · Zbl 0072.14102
[6] Fletcher, R.: Conjugate gradient methods for indefinite systems. Numerical analysis 506, 73-89 (1976) · Zbl 0326.65033
[7] Golub, G. H.; O’leary, D. P.: Some history of the conjugate and Lanczos algorithms. SIAM rev. 31, 50-102 (1989)
[8] Hestenes, M. R.: Conjugate direction methods in optimization. (1980) · Zbl 0439.49001
[9] Brezinski, C.: 2nd edition Padé-type approximation and general orthogonal polynomials. Padé-type approximation and general orthogonal polynomials 50 (1980) · Zbl 0418.41012
[10] Brezinski, C.; Sadok, H.: Lanczos-type algorithms for solving systems of linear equations. Appl. numer. Math. 11, 443-473 (1993) · Zbl 0780.65020
[11] Brezinski, C.; Redivo-Zaglia, M.: Breakdowns in the computation of orthogonal polynomials. Nonlinear numerical methods and rational approximation, II, 49-59 (1994) · Zbl 0812.65008
[12] Chan, T. F.; Szeto, T.: A composite step conjugate gradients squared algorithm for solving nonsymmetric linear systems. Numerical algorithms 7, 17-32 (1994) · Zbl 0809.65026
[13] Young, D. M.; Jea, K. C.: Generalized conjugate-gradient acceleration of nonsymmetrizable iterative methods. Linear algebra appl. 34, 159-194 (1980) · Zbl 0463.65025
[14] Gutknecht, M. H.: The unsymmetric Lanczos algorithms and their relations to Padé approximation, continued fractions, and the qd algorithm. Preliminary Proceedings of the copper mountain conference on iterative methods (April 1--5, 1990)
[15] Baheux, C.: New implementations of Lanczos method. J. comput. Appl. math. 57, 3-15 (1995) · Zbl 0827.65037
[16] Brezinski, C.; Redivo-Zaglia, M.: A new presentation of orthogonal polynomials with applications to their computation. Numerical algorithms 1, 207-221 (1991) · Zbl 0752.65011
[17] Jea, K. C.: Generalized conjugate gradient acceleration of iterative methods. Ph.d. thesis (1982)
[18] Jea, K. C.; Young, D. M.: On the simplification of generalized conjugate gradient methods for nonsymmetrizable linear systems. Linear algebra appl. 52, 299-317 (1983) · Zbl 0535.65018
[19] Freund, R. W.; Golub, G. H.; Nachtigal, N. M.: Iterative solution of linear systems. Acta numerica 1, 57-100 (1991) · Zbl 0762.65019
[20] Freund, R. W.; Gutknecht, M. H.; Nachtigal, N. M.: An implementation of the look-ahead Lanczos algorithm for non-Hermitian matrices. SIAM J. Sci. comput. 14, 137-158 (1993) · Zbl 0770.65022
[21] Saad, Y.: The Lanczos biorthogonalization algorithm and other oblique projection methods for solving large unsymmetric systems. SIAM J. Numer. anal. 19, 485-506 (1982) · Zbl 0483.65022
[22] Vinsome, P. K. W.: Orthomin, an iterative method for solving sparse sets of simultaneous equations. Proceedings 4th symposium on reservoir simulation, 149-159 (1976)
[23] Draux, A.: Polynômes orthogonaux formels. Applications 974 (1983) · Zbl 0504.42001
[24] Brezinski, C.; Redivo-Zaglia, M.; Sadok, H.: A breakdown-free Lanczos type algorithm for solving linear systems. Numer. math. 63, 29-38 (1992) · Zbl 0739.65027
[25] Gutknecht, M. H.: A completed theory of the unsymmetric Lanczos process and related algorithms, part I. SIAM J. Matrix anal. Appl. 13, 594-639 (1992) · Zbl 0760.65039
[26] Gutknecht, M. H.: A completed theory of the unsymmetric Lanczos process and related algorithms, part II. SIAM J. Matrix anal. Appl. 15, 15-58 (1994) · Zbl 0809.65028
[27] Sonneveld, P.: A fast Lanczos-type solver for nonsymmetric linear systems. SIAM J. Sci. stat. Comput. 10, 35-52 (1989) · Zbl 0666.65029
[28] Brezinski, C.; Sadok, H.: Avoiding breadkown in the CGS algorithm. Numerical algorithms 1, 199-206 (1991) · Zbl 0766.65024
[29] Bank, R. E.; Chan, T. F.: A composite step bi-conjugate gradient algorithm for solving nonsymmetric systems. Numerical algorithms 7, 1-16 (1994) · Zbl 0809.65025
[30] Bank, R. E.; Chan, T. F.: An analysis of the composite step bi-conjugate gradient algorithm for solving nonsymmetric systems. Numer. math. 66, 295-319 (1993) · Zbl 0802.65038
[31] Taylor, D. R.: Analysis of the look-ahead Lanczos algorithm. Ph.d. thesis (November 1982)
[32] Parlett, B. N.; Taylor, D. R.; Liu, Z. A.: A look-ahead Lanczos algorithm for unsymmetric matrices. Math. comput. 44, 105-124 (1985) · Zbl 0564.65022
[33] Khelifi, M.: Lanczos maximal algorithm for unsymmetric eigenvalue problems. Appl. numer. Math. 7, 179-193 (1991) · Zbl 0716.65030
[34] Brezinski, C.; Redivo-Zaglia, M.; Sadok, H.: Avoiding breakdown and near-breakdown in Lanczos type algorithms. Numerical algorithms 1, 261-284 (1991) · Zbl 0748.65033
[35] Brezinski, C.; Redivo-Zaglia, M.: Treatment of near-breakdown in the CGS algorithm. Numerical algorithms 7, 33-73 (1994) · Zbl 0810.65028
[36] Brezinski, C.; Redivo-Zaglia, M.: Treatment of near-breakdown in the CGS algorithm. Publication ANO 257 (November 1991) · Zbl 0810.65028
[37] Brezinski, C.; Redivo-Zaglia, M.; Sadok, H.: Addendum to ”avoiding breakdown and near-breakdown in Lanczos type algorithms”. Numerical algorithms 2, 133-136 (1992) · Zbl 0769.65014
[38] Boley, D. L.; Elhay, S.; Golub, G. H.; Gutknecht, M. H.: Nonsymmetric Lanczos and finding orthogonal polynomials associated with indefinite weights. Numerical algorithms 1, 21-44 (1991) · Zbl 0752.65010
[39] Freund, R. W.: Solution of shifted linear systems by quasi-minimal residual iterations. Numerical linear algebra, 101-121 (1993) · Zbl 0794.65028
[40] Brezinski, C.; Redivo-Zaglia, M.: Look-ahead in bi-CGSTAB and other methods for linear systems. Bit 35, 169-201 (1995) · Zbl 0831.65032
[41] 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. Comp. 13, 631-644 (1992) · Zbl 0761.65023
[42] Parlett, B. N.: The symmetric eigenvalue problem. (1980) · Zbl 0431.65017
[43] Watkins, D. S.: Some perspectives on the eigenvalue problem. SIAM rev. 35, 430-471 (1993) · Zbl 0786.65032
[44] Brezinski, C.: Biorthogonality and its applications to numerical analysis. (1992) · Zbl 0757.41001
[45] Brezinski, C.: Biorthogonality and conjugate gradient-type algorithms. Contributions in numerical mathematics 2, 55-70 (1993) · Zbl 0834.65015
[46] Brezinski, C.; Sadok, H.: Some vector sequence transformations with applications to systems of equations. Numerical algorithms 3, 75-80 (1992) · Zbl 0794.65002
[47] Saad, Y.: Numerical methods for large eigenvalue problems. (1992) · Zbl 0991.65039
[48] Saad, Y.: Iterative methods for sparse linear systems. (1996) · Zbl 1031.65047
[49] Joubert, W.: Generalized conjugate gradient and Lanczos methods for the solution of nonsymmetric systems of linear equations. Ph.d. thesis (1990)
[50] Nachtigal, N. M.: A look-ahead variant of the Lanczos algorithm and its application to the quasi-minimal residual method for non-Hermitian linear systems. Ph.d. thesis (1991)
[51] Saad, Y.; Schultz, M. H.: Conjugate gradient-like algorithms for solving non-symmetric linear systems. Math. comput. 44, 417-424 (1985) · Zbl 0566.65019
[52] Mai, T. -Z.: Modified Lanczos method for solving large sparse linear systems. Commun. numer. Meth. engn. 9, 67-79 (1993) · Zbl 0782.65047
[53] Cabay, S.; Meleshko, R.: A weakly stable algorithm for Padé approximants and the inversion of Hankel matrices. SIAM J. Matrix anal. Appl. 14, 735-765 (1993) · Zbl 0779.65009
[54] Cabay, S.; Choi, D. -K.: Algebraic computations of scaled Padé fractions. SIAM J. Comput. 15, 243-270 (1986) · Zbl 0633.30008
[55] Meleshko, R.; Cabay, S.: On computing Padé approximants quickly and accurately. Congr. numerantium 80, 245-255 (1991) · Zbl 0736.65005
[56] Schönauer, W.: Scientific computing on vector computers. (1987)
[57] Weiss, R.: Convergence behavior of generalized conjugate gradient methods. Thesis (1990)
[58] Zhou, L.; Walker, H. F.: Residual smoothing techniques for iterative methods. SIAM J. Sci. comput. 15, 297-312 (1994) · Zbl 0802.65041
[59] Brezinski, C.; Redivo-Zaglia, M.: Hybrid procedures for solving linear systems. Numer. math. 67, 1-19 (1994) · Zbl 0797.65023
[60] Wynn, P.: On some recent developments in the theory and application of continued fractions. SIAM J. Numer. anal. 1, 177-197 (1964) · Zbl 0143.17804