The Lanczos method for solving systems of linear equations is implemented by using some recurrence relationships between polynomials of a family of formal orthogonal polynomials or between those of two adjacent families of formal orthogonal polynomials. A division by zero can occur in these relations, thus producing a breakdown in the algorithm which has to be stopped. In this paper, three strategies to avoid this drawback are discussed: the MRZ and its variants, the normalized and unnormalized BIORES algorithm and the composite step biconjugate algorithm. We prove that all these algorithms can be derived from a unified framework; in fact, we give a formalism for finding all the recurrence relationships used in these algorithms, which shows that the three strategies use the same techniques.
@article{bwmeta1.element.bwnjournal-article-zmv26i4p477bwm,
author = {A. El Guennouni},
title = {A unified approach to some strategies for the treatment of breakdown in Lanczos-type algorithms},
journal = {Applicationes Mathematicae},
volume = {26},
year = {1999},
pages = {477-488},
zbl = {0998.65042},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-zmv26i4p477bwm}
}
El Guennouni, A. A unified approach to some strategies for the treatment of breakdown in Lanczos-type algorithms. Applicationes Mathematicae, Tome 26 (1999) pp. 477-488. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-zmv26i4p477bwm/
[000] [1] C. Brezinski and M. Redivo Zaglia, Breakdown in the computation of orthogonal polynomial, in: Nonlinear Numerical Methods and Rational Approximation, II, A. Cuyt (ed.), Kluwer, Dordrecht, 1994, 49-59. | Zbl 0812.65008
[001] [2] C. Brezinski, M. Redivo Zaglia and H. Sadok, Avoiding breakdown and near-breakdown in Lanczos type algorithms, Numer. Algorithms 1 (1991), 261-284.
[002] [3] C. Brezinski, M. Redivo Zaglia and H. Sadok, Breakdown in the implementation of the Lanczos method for solving linear systems, Comput. Math. Appl. 33 (1997), 31-44.
[003] [4] C. Brezinski and H. Sadok, Lanczos-type algorithm for solving systems of linear equations, Appl. Numer. Math. 11 (1993), 443-473. | Zbl 0780.65020
[004] [5] T. F. Chan and R. E. Bank, A composite step bi-conjugate gradient algorithm for solving nonsymmetric systems, Numer. Algorithms 7 (1994), 1-16. | Zbl 0809.65025
[005] [6] T. F. Chan and R. E. Bank, An analysis of the composite step bi-conjugate gradient method, Numer. Math. 66 (1993), 295-319. | Zbl 0802.65038
[006] [7] A. Draux, Polynômes orthogonaux formels, Lecture Notes in Math. 974, Springer, Berlin, 1983. | Zbl 0504.42001
[007] [8] A. Draux, Formal orthogonal polynomials revisited. Applications, Numer. Algorithms 11 (1996), 143-158.
[008] [9] R. Fletcher, Conjugate gradient methods for indefinite systems, in: Numerical Analysis (Dundee, 1975), G. A. Watson (ed.), Lecture Notes in Math. 506, Springer, Berlin, 1976, 73-89.
[009] [10] M. H. Gutknecht, A completed theory of the unsymmetric Lanczos process and related algorithms. I, SIAM J. Matrix Anal. 13 (1992), 594-639. | Zbl 0760.65039
[010] [11] C. Lanczos, An iteration method for the solution of the eigenvalue problem of linear differential and integral operators, J. Res. Nat. Bur. Standards 45 (1950), 255-282.
[011] [12] C. Lanczos, Solution of systems of linear equations by minimized iterations, ibid. 49 (1952), 33-53.