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

A. El Guennouni

Applicationes Mathematicae (1999)

  • Volume: 26, Issue: 4, page 477-488
  • ISSN: 1233-7234

Abstract

top
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.

How to cite

top

El Guennouni, A.. "A unified approach to some strategies for the treatment of breakdown in Lanczos-type algorithms." Applicationes Mathematicae 26.4 (1999): 477-488. <http://eudml.org/doc/219253>.

@article{ElGuennouni1999,
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.},
author = {El Guennouni, A.},
journal = {Applicationes Mathematicae},
keywords = {deficient polynomials; orthogonal polynomials; Lanczos method; biconjugate algorithm},
language = {eng},
number = {4},
pages = {477-488},
title = {A unified approach to some strategies for the treatment of breakdown in Lanczos-type algorithms},
url = {http://eudml.org/doc/219253},
volume = {26},
year = {1999},
}

TY - JOUR
AU - El Guennouni, A.
TI - A unified approach to some strategies for the treatment of breakdown in Lanczos-type algorithms
JO - Applicationes Mathematicae
PY - 1999
VL - 26
IS - 4
SP - 477
EP - 488
AB - 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.
LA - eng
KW - deficient polynomials; orthogonal polynomials; Lanczos method; biconjugate algorithm
UR - http://eudml.org/doc/219253
ER -

References

top
  1. [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. Zbl0812.65008
  2. [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. [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. [4] C. Brezinski and H. Sadok, Lanczos-type algorithm for solving systems of linear equations, Appl. Numer. Math. 11 (1993), 443-473. Zbl0780.65020
  5. [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. Zbl0809.65025
  6. [6] T. F. Chan and R. E. Bank, An analysis of the composite step bi-conjugate gradient method, Numer. Math. 66 (1993), 295-319. Zbl0802.65038
  7. [7] A. Draux, Polynômes orthogonaux formels, Lecture Notes in Math. 974, Springer, Berlin, 1983. Zbl0504.42001
  8. [8] A. Draux, Formal orthogonal polynomials revisited. Applications, Numer. Algorithms 11 (1996), 143-158. 
  9. [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. [10] M. H. Gutknecht, A completed theory of the unsymmetric Lanczos process and related algorithms. I, SIAM J. Matrix Anal. 13 (1992), 594-639. Zbl0760.65039
  11. [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. [12] C. Lanczos, Solution of systems of linear equations by minimized iterations, ibid. 49 (1952), 33-53. 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.