Orthogonal polynomials and the Lanczos method

C. Brezinski; H. Sadok; M. Redivo Zaglia

Banach Center Publications (1994)

  • Volume: 29, Issue: 1, page 19-33
  • ISSN: 0137-6934

Abstract

top
Lanczos method for solving a system of linear equations is well known. It is derived from a generalization of the method of moments and one of its main interests is that it provides the exact answer in at most n steps where n is the dimension of the system. Lanczos method can be implemented via several recursive algorithms known as Orthodir, Orthomin, Orthores, Biconjugate gradient,... In this paper, we show that all these procedures can be explained within the framework of formal orthogonal polynomials. This theory also provides a natural basis for curing breakdown and near-breakdown in these algorithms. The case of the conjugate gradient squared method can be treated similarly.

How to cite

top

Brezinski, C., Sadok, H., and Redivo Zaglia, M.. "Orthogonal polynomials and the Lanczos method." Banach Center Publications 29.1 (1994): 19-33. <http://eudml.org/doc/262795>.

@article{Brezinski1994,
abstract = {Lanczos method for solving a system of linear equations is well known. It is derived from a generalization of the method of moments and one of its main interests is that it provides the exact answer in at most n steps where n is the dimension of the system. Lanczos method can be implemented via several recursive algorithms known as Orthodir, Orthomin, Orthores, Biconjugate gradient,... In this paper, we show that all these procedures can be explained within the framework of formal orthogonal polynomials. This theory also provides a natural basis for curing breakdown and near-breakdown in these algorithms. The case of the conjugate gradient squared method can be treated similarly.},
author = {Brezinski, C., Sadok, H., Redivo Zaglia, M.},
journal = {Banach Center Publications},
keywords = {projection; biconjugate gradient; orthogonal polynomials; Lanczos method; Laczos method; biconjugate gradient method},
language = {eng},
number = {1},
pages = {19-33},
title = {Orthogonal polynomials and the Lanczos method},
url = {http://eudml.org/doc/262795},
volume = {29},
year = {1994},
}

TY - JOUR
AU - Brezinski, C.
AU - Sadok, H.
AU - Redivo Zaglia, M.
TI - Orthogonal polynomials and the Lanczos method
JO - Banach Center Publications
PY - 1994
VL - 29
IS - 1
SP - 19
EP - 33
AB - Lanczos method for solving a system of linear equations is well known. It is derived from a generalization of the method of moments and one of its main interests is that it provides the exact answer in at most n steps where n is the dimension of the system. Lanczos method can be implemented via several recursive algorithms known as Orthodir, Orthomin, Orthores, Biconjugate gradient,... In this paper, we show that all these procedures can be explained within the framework of formal orthogonal polynomials. This theory also provides a natural basis for curing breakdown and near-breakdown in these algorithms. The case of the conjugate gradient squared method can be treated similarly.
LA - eng
KW - projection; biconjugate gradient; orthogonal polynomials; Lanczos method; Laczos method; biconjugate gradient method
UR - http://eudml.org/doc/262795
ER -

References

top
  1. [1] C. Brezinski, Padé-type Approximation and General Orthogonal Polynomials, Internat. Ser. Number. Math. 50, Birkhäuser, Basel 1980. Zbl0418.41012
  2. [2] C. Brezinski, The methods of Vorobyev and Lanczos, to appear. Zbl0923.65023
  3. [3] C. Brezinski, Biorthogonality and its Applications to Numerical Analysis, Marcel Dekker, New York 1992. Zbl0757.41001
  4. [4] C. Brezinski and M. Redivo Zaglia, A new presentation of orthogonal polynomials with application to their computation, Numer. Algorithms 1 (1991), 207-221. 
  5. [5] C. Brezinski and M. Redivo Zaglia, Treatment of near-breakdown in the CGS algorithm, to appear. 
  6. [6] C. Brezinski, M. Redivo Zaglia and H. Sadok, A breakdown-free Lanczos type algorithm for solving linear systems, Numer. Math. 63 (1992), 29-38. 
  7. [7] C. Brezinski, M. Redivo Zaglia and H. Sadok, Avoiding breakdown and near-breakdown in Lanczos type algorithms, Numer. Algorithms 1 (1991), 261-284. 
  8. [8] C. Brezinski and H. Sadok, Lanczos type methods for solving systems of linear equations, Appl. Numer. Math., to appear. 
  9. [9] C. Brezinski and H. Sadok, Avoiding breakdown in the CGS algorithm, Numer. Algorithms 1 (1991), 199-206. Zbl0766.65024
  10. [10] A. Draux, Polynômes Orthogonaux Formels - Applications, Lecture Notes in Math. 974, Springer, Berlin 1983. Zbl0504.42001
  11. [11] R. Fletcher, Conjugate gradient methods for indefinite systems, in: Numerical Analysis, G. A. Watson (ed.), Lecture Notes in Math. 506, Springer, Berlin 1976, 73-89. 
  12. [12] M. H. Gutknecht, A completed theory of the unsymmetric Lanczos process and related algorithms. Part I, SIAM J. Matrix Anal. Appl. 13 (1992), 594-639. Zbl0760.65039
  13. [13] M. R. Hestenes and E. Stiefel, Methods of conjugate gradients for solving linear systems, J. Res. Nat. Bur. Standards 49 (1952), 409-439. Zbl0048.09901
  14. [14] C. Lanczos, Solution of systems of linear equations by minimized iterations, ibid., 33-53. 
  15. [15] P. Sonneveld, CGS, a fast Lanczos-type solver for nonsymmetric linear systems, SIAM J. Sci. Statist. Comput. 10 (1989), 36-52. Zbl0666.65029
  16. [16] Yu. V. Vorobyev, Method of Moments in Applied Mathematics, Gordon and Breach, New York 1965. 
  17. [17] D. M. Young and K. C. Jea, Generalized conjugate-gradient acceleration of nonsymmetrizable iterative methods, Linear Algebra Appl. 34 (1980), 159-194. Zbl0463.65025

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.