×

Avoiding breakdown and near-breakdown in Lanczos type algorithms. (English) Zbl 0748.65033

The paper deals with methods which the authors have developed to avoid breakdown and near-breakdown due to division by a scalar product whose value is zero or is different from zero but small in Lanczos type algorithms for solving linear systems.
In particular, the bulk of the paper concentrates on a method called by the authors the method of recursive zoom (MRZ) and its variants: SMRZ, BMRZ, GMRZ and BSMRZ, where S, B, G stand for symmetric, balancing and general, respectively. It is shown that a breakdown can be avoided by considering only the existing orthogonal polynomials in the Lanczos type algorithms. The methods described in the paper are able to detect if such a polynomial does not exist in order to jump over it.
Pseudo-codes for MRZ and BSMRZ are given and some numerical results are presented.

MSC:

65F15 Numerical computation of eigenvalues and eigenvectors of matrices
65F10 Iterative numerical methods for linear systems
65F25 Orthogonalization in numerical linear algebra

Software:

CGS; na1
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] D.L. Boley, S. Elhay, G.H. Golub and M.H. Gutknecht, Nonsymmetric Lanczos and finding orthogonal polynomials associated with indefinite weights, Numer. Algorithms 1 (1991) 21–44. · Zbl 0752.65010 · doi:10.1007/BF02145581
[2] C. Brezinski,Padé-type Approximation and General Orthogonal Polynomials. ISNM Vol. 50, (Birkhäuser, Basel, 1980). · Zbl 0418.41012
[3] C. Brezinski, M. Redivo Zaglia and H. Sadok, A breakdown-free Lanczos type algorithm for solving linear systems, Numer. Math., to appear.
[4] C. Brezinski and H. Sadok, Lanczos type methods for systems of linear equations, submitted. · Zbl 0780.65020
[5] C. Brezinski and H. Sadok, Avoiding breakdown in the CGS algorithm, Numer. Algorithms 1 (1991) 199–206. · Zbl 0766.65024 · doi:10.1007/BF02142321
[6] A. Draux,Polynômes Orthogonaux Formels. Applications., LNM 974 (Springer-Verlag, Berlin, 1983). · Zbl 0504.42001
[7] R. Fletcher, Conjugate gradient methods for indefinite systems, in:Numerical Analysis, ed. G.A. Watson, LNM 506 (Springer-Verlag, Berlin, 1976) pp. 73–89.
[8] M.H. Gutknecht, A completed theory of the unsymmetric Lanczos process and related algorithms, Parts I, II, SIAM J. Matrix Anal. Appl., to appear. · Zbl 0809.65028
[9] P. Sonneveld, CGS, a fast Lanczos-type solver for nonsymmetric linear systems, SIAM J. Sci. Stat. Comp. 10 (1989) 36–52. · Zbl 0666.65029 · doi:10.1137/0910004
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.