A unified approach to some strategies for the treatment of breakdown in Lanczos-type algorithms
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.
-  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.
-  C. Brezinski, M. Redivo Zaglia and H. Sadok, Avoiding breakdown and near-breakdown in Lanczos type algorithms, Numer. Algorithms 1 (1991), 261-284.
-  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.
-  C. Brezinski and H. Sadok, Lanczos-type algorithm for solving systems of linear equations, Appl. Numer. Math. 11 (1993), 443-473.
-  T. F. Chan and R. E. Bank, A composite step bi-conjugate gradient algorithm for solving nonsymmetric systems, Numer. Algorithms 7 (1994), 1-16.
-  T. F. Chan and R. E. Bank, An analysis of the composite step bi-conjugate gradient method, Numer. Math. 66 (1993), 295-319.
-  A. Draux, Polynômes orthogonaux formels, Lecture Notes in Math. 974, Springer, Berlin, 1983.
-  A. Draux, Formal orthogonal polynomials revisited. Applications, Numer. Algorithms 11 (1996), 143-158.
-  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.
-  M. H. Gutknecht, A completed theory of the unsymmetric Lanczos process and related algorithms. I, SIAM J. Matrix Anal. 13 (1992), 594-639.
-  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.
-  C. Lanczos, Solution of systems of linear equations by minimized iterations, ibid. 49 (1952), 33-53.