Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
1999 | 26 | 1 | 33-62
Tytuł artykułu

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

Treść / Zawartość
Warianty tytułu
Języki publikacji
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.
Opis fizyczny
  • Laboratoire d'Analyse Numérique et d'Optimisation, UFR IEEA-M3
  • [1] E. H. Ayachour, Avoiding the look-ahead in the Lanczos method, Publ. ANO-363, Univ. des Sciences et Technologies de Lille, 1996.
  • [2] E. H. Ayachour, Application de la biorthogonalité aux méthodes de projection, thèse, Université des Sciences et Technologies de Lille, 1998.
  • [3] C. Brezinski, Computation of Padé approximants and continued fractions, J. Comput. Appl. Math. 2 (1976), 113-123.
  • [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.
  • [5] C. Brezinski, Padé-Type Approximation and General Orthogonal Polynomials, Birkhäuser, Basel, 1980.
  • [6] C. Brezinski, Other manifestations of the Schur complement, Linear Algebra Appl. 111 (1988), 231-247.
  • [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] 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] C. Brezinski and M. Redivo Zaglia, Extrapolation Methods--Theory and Practice, North-Holland, Amsterdam, 1994.
  • [10] C. Brezinski and M. Redivo Zaglia, Look-ahead in Bi-CGSTAB and other methods for linear systems, BIT 35 (1995), 169-201.
  • [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] C. Brezinski, M. Redivo Zaglia and H. Sadok, Avoiding breakdown and near-breakdown in Lanczos type algorithms, ibid. 1 (1991), 261-284.
  • [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.
  • [14] C. Brezinski and H. Sadok, Lanczos-type algorithms for solving systems of linear equations, Appl. Numer. Math. 11 (1993), 443-473.
  • [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] A. Draux, Polynômes Orthogonaux Formels. Applications, Lecture Notes in Math. 974, Springer, Berlin, 1983.
  • [17] A. Draux et P. Van Ingelandt, Polynômes Orthogonaux et Approximants de Padé. Logiciels, Technip, Paris, 1987.
  • [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.
  • [19] W. B. Gragg and A. Lindquist, On the partial realization problem, Linear Algebra Appl. 50 (1983), 277-319.
  • [20] M. H. Gutknecht, Variants of Bi-CGSTAB for matrices with complex spectrum, SIAM J. Sci. Comput. 193 (1993), 1020-1033.
  • [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.
  • [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.
  • [23] M. H. Gutknecht and M. Hochbruck, Look-ahead Levinson and Schur algorithms for non-Hermitian Toeplitz systems, Numer. Math. 70 (1995), 181-227.
  • [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.
  • [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] M. A. Piñar and V. Ramirez, Recursive inversion of Hankel matrices, Monogr. Acad. Ciencias Zaragoza 1 (1988), 119-128.
  • [27] P. Sonneveld, CGS: a fast Lanczos-type solver for nonsymmetric linear systems, SIAM J. Sci. Statist. Comput. 10 (1989), 36-52.
  • [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.
  • [29] H. Van Rossum, Contiguous orthogonal systems, Koninkl. Nederl. Akad. Wet- ensch. Ser. A 63 (1960), 323-332.
  • [30] P. Wynn, Upon systems of recursions which obtain among the quotients of Padé table, Numer. Math. 8 (1966), 264-269.
  • [31] D. M. Young and K. C. Jea, Generalized conjugate-gradient acceleration for nonsymmetrizable iterative methods, Linear Algebra Appl. 34 (1980), 159-194.
  • [32] M. Ziegler, Generalized biorthogonal bases and tridiagonalisation of matrices, Report Nr. 22 (1995), Universität Tübingen, Biomathematik.
  • [33] M. Ziegler, Generalized biorthogonal bases and tridiagonalisation of matrices, Numer. Math. 77 (1997), 407-421.
Typ dokumentu
Identyfikator YADDA
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.