Avoiding look-ahead in the Lanczos method and Padé approximation

E. Ayachour

Applicationes Mathematicae (1999)

  • Volume: 26, Issue: 1, page 33-62
  • ISSN: 1233-7234

Abstract

top
In the non-normal case, it is possible to use various look-ahead strategies for computing the elements of a family of regular orthogonal polynomials. These strategies consist in jumping over non-existing and singular orthogonal polynomials by solving triangular linear systems. We show how to avoid them by using a new method called ALA (Avoiding Look-Ahead), for which we give three principal implementations. The application of ALA to Padé approximation, extrapolation methods and Lanczos method for solving systems of linear equations is discussed.

How to cite

top

Ayachour, E.. "Avoiding look-ahead in the Lanczos method and Padé approximation." Applicationes Mathematicae 26.1 (1999): 33-62. <http://eudml.org/doc/219225>.

@article{Ayachour1999,
abstract = {In the non-normal case, it is possible to use various look-ahead strategies for computing the elements of a family of regular orthogonal polynomials. These strategies consist in jumping over non-existing and singular orthogonal polynomials by solving triangular linear systems. We show how to avoid them by using a new method called ALA (Avoiding Look-Ahead), for which we give three principal implementations. The application of ALA to Padé approximation, extrapolation methods and Lanczos method for solving systems of linear equations is discussed.},
author = {Ayachour, E.},
journal = {Applicationes Mathematicae},
keywords = {extrapolation methods; orthogonal and biorthogonal polynomials; Padé approximation; Lanczos method; regular orthogonal polynomials; singular orthogonal polynomials; triangular linear systems; avoiding look-ahead},
language = {eng},
number = {1},
pages = {33-62},
title = {Avoiding look-ahead in the Lanczos method and Padé approximation},
url = {http://eudml.org/doc/219225},
volume = {26},
year = {1999},
}

TY - JOUR
AU - Ayachour, E.
TI - Avoiding look-ahead in the Lanczos method and Padé approximation
JO - Applicationes Mathematicae
PY - 1999
VL - 26
IS - 1
SP - 33
EP - 62
AB - In the non-normal case, it is possible to use various look-ahead strategies for computing the elements of a family of regular orthogonal polynomials. These strategies consist in jumping over non-existing and singular orthogonal polynomials by solving triangular linear systems. We show how to avoid them by using a new method called ALA (Avoiding Look-Ahead), for which we give three principal implementations. The application of ALA to Padé approximation, extrapolation methods and Lanczos method for solving systems of linear equations is discussed.
LA - eng
KW - extrapolation methods; orthogonal and biorthogonal polynomials; Padé approximation; Lanczos method; regular orthogonal polynomials; singular orthogonal polynomials; triangular linear systems; avoiding look-ahead
UR - http://eudml.org/doc/219225
ER -

References

top
  1. [1] E. H. Ayachour, Avoiding the look-ahead in the Lanczos method, Publ. ANO-363, Univ. des Sciences et Technologies de Lille, 1996. 
  2. [2] E. H. Ayachour, Application de la biorthogonalité aux méthodes de projection, thèse, Université des Sciences et Technologies de Lille, 1998. 
  3. [3] C. Brezinski, Computation of Padé approximants and continued fractions, J. Comput. Appl. Math. 2 (1976), 113-123. Zbl0341.65007
  4. [4] C. Brezinski, Sur les polynômes associés à une famille de polynômes orthogonaux, C. R. Acad. Sci. Paris Sér. A 284 (1977), 1041-1044. Zbl0356.42016
  5. [5] C. Brezinski, Padé-Type Approximation and General Orthogonal Polynomials, Birkhäuser, Basel, 1980. 
  6. [6] C. Brezinski, Other manifestations of the Schur complement, Linear Algebra Appl. 111 (1988), 231-247. Zbl0662.65037
  7. [7] C. Brezinski, CGM: a whole class of Lanczos-type solvers for linear systems, Publ. ANO-253, Univ. des Sciences et Technologies de Lille, 1991. 
  8. [8] C. Brezinski and M. Redivo Zaglia, Breakdowns in the computation of orthogonal polynomials, in: Nonlinear Numerical Methods and Rational Approximation II, A. Cuyt (ed.), Kluwer, Dordrecht, 1994, 49-59. 
  9. [9] C. Brezinski and M. Redivo Zaglia, Extrapolation Methods--Theory and Practice, North-Holland, Amsterdam, 1994. Zbl0802.65029
  10. [10] C. Brezinski and M. Redivo Zaglia, Look-ahead in Bi-CGSTAB and other methods for linear systems, BIT 35 (1995), 169-201. 
  11. [11] C. Brezinski and M. Redivo Zaglia, A look-ahead strategy for the implementation of old and new extrapolation methods, Numer. Algorithms 11 (1996), 35-55. 
  12. [12] C. Brezinski, M. Redivo Zaglia and H. Sadok, Avoiding breakdown and near-breakdown in Lanczos type algorithms, ibid. 1 (1991), 261-284. Zbl0748.65033
  13. [13] C. Brezinski, M. Redivo Zaglia and H. Sadok, A breakdown-free Lanczos type algorithm for solving linear systems, Numer. Math. 63 (1992), 29-38. Zbl0739.65027
  14. [14] C. Brezinski and H. Sadok, Lanczos-type algorithms for solving systems of linear equations, Appl. Numer. Math. 11 (1993), 443-473. Zbl0780.65020
  15. [15] F. Cordellier, Interpolation rationnelle et autres questions : aspects algorithmiques et numériques, thèse d'état, Univ. des Sciences et Technologies de Lille, 1989. 
  16. [16] A. Draux, Polynômes Orthogonaux Formels. Applications, Lecture Notes in Math. 974, Springer, Berlin, 1983. Zbl0504.42001
  17. [17] A. Draux et P. Van Ingelandt, Polynômes Orthogonaux et Approximants de Padé. Logiciels, Technip, Paris, 1987. 
  18. [18] R. W. Freund, M. H. Gutknecht and N. M. Nachtigal, An implementation of the look-ahead Lanczos algorithm for non-Hermitian matrices, SIAM J. Sci. Statist. Comput. 14 (1993), 137-158. Zbl0770.65022
  19. [19] W. B. Gragg and A. Lindquist, On the partial realization problem, Linear Algebra Appl. 50 (1983), 277-319. Zbl0519.93024
  20. [20] M. H. Gutknecht, Variants of Bi-CGSTAB for matrices with complex spectrum, SIAM J. Sci. Comput. 193 (1993), 1020-1033. Zbl0837.65031
  21. [21] 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
  22. [22] M. H. Gutknecht and M. Hochbruck, Look-ahead Levinson- and Schur-type recurrences in the Padé table, Electr. Trans. Numer. Anal. 2 (1994), 104-129. Zbl0852.41012
  23. [23] M. H. Gutknecht and M. Hochbruck, Look-ahead Levinson and Schur algorithms for non-Hermitian Toeplitz systems, Numer. Math. 70 (1995), 181-227. Zbl0823.65023
  24. [24] K. C. Jea and D. M. Young, On the simplification of generalized conjugate-gradient methods for linear systems, Linear Algebra Appl. 52 (1983), 399-417. Zbl0535.65018
  25. [25] 5 N. M. Nachtigal, A look-ahead variant of the Lanczos algorithm and its application to the quasi-minimal residual method for non-hermitian linear systems, Ph.D. thesis, Massachusetts Institute of Technology, 1991. 
  26. [26] M. A. Piñar and V. Ramirez, Recursive inversion of Hankel matrices, Monogr. Acad. Ciencias Zaragoza 1 (1988), 119-128. Zbl0684.65020
  27. [27] P. Sonneveld, CGS: a fast Lanczos-type solver for nonsymmetric linear systems, SIAM J. Sci. Statist. Comput. 10 (1989), 36-52. Zbl0666.65029
  28. [28] H. A. Van Der Vorst, Bi-CGSTAB: a fast and smoothly converging variant of Bi-CG for the solution of nonsymmetric linear systems, ibid. 13 (1992), 631-644. Zbl0761.65023
  29. [29] H. Van Rossum, Contiguous orthogonal systems, Koninkl. Nederl. Akad. Wet- ensch. Ser. A 63 (1960), 323-332. Zbl0099.05502
  30. [30] P. Wynn, Upon systems of recursions which obtain among the quotients of Padé table, Numer. Math. 8 (1966), 264-269. Zbl0163.39502
  31. [31] D. M. Young and K. C. Jea, Generalized conjugate-gradient acceleration for nonsymmetrizable iterative methods, Linear Algebra Appl. 34 (1980), 159-194. Zbl0463.65025
  32. [32] M. Ziegler, Generalized biorthogonal bases and tridiagonalisation of matrices, Report Nr. 22 (1995), Universität Tübingen, Biomathematik. 
  33. [33] M. Ziegler, Generalized biorthogonal bases and tridiagonalisation of matrices, Numer. Math. 77 (1997), 407-421. Zbl0884.65030

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.