Download PDF - A unified approach to some strategies for the treatment of breakdown in Lanczos-type algorithmsAll rights reserved. Copyright exceptions and limitations apply

ArticleOriginal scientific text

Title

A unified approach to some strategies for the treatment of breakdown in Lanczos-type algorithms

Authors 1

Affiliations

  1. Laboratoire d'Analyse Numérique et d'Optimisation, UFR IEEA-M3, Université des Sciences et Technologies, de Lille, F-59655 Villeneuve d'Ascq Cedex, France

Abstract

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.

Keywords

ENG
deficient polynomials, orthogonal polynomials, Lanczos method

Bibliography

  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.
  2. C. Brezinski, M. Redivo Zaglia and H. Sadok, Avoiding breakdown and near-breakdown in Lanczos type algorithms, Numer. Algorithms 1 (1991), 261-284.
  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.
  4. C. Brezinski and H. Sadok, Lanczos-type algorithm for solving systems of linear equations, Appl. Numer. Math. 11 (1993), 443-473.
  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.
  6. T. F. Chan and R. E. Bank, An analysis of the composite step bi-conjugate gradient method, Numer. Math. 66 (1993), 295-319.
  7. A. Draux, Polynômes orthogonaux formels, Lecture Notes in Math. 974, Springer, Berlin, 1983.
  8. A. Draux, Formal orthogonal polynomials revisited. Applications, Numer. Algorithms 11 (1996), 143-158.
  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.
  10. M. H. Gutknecht, A completed theory of the unsymmetric Lanczos process and related algorithms. I, SIAM J. Matrix Anal. 13 (1992), 594-639.
  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.
  12. C. Lanczos, Solution of systems of linear equations by minimized iterations, ibid. 49 (1952), 33-53.
Applicationes Mathematicae
1999/26/4
Export to PBN, Opens in new tab
Pages:
477-488
Main language of publication
English
Received
1999-05-11
Accepted
1999-08-03
Published
1999
Exact and natural sciences