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

• Autorzy: E. H. Ayachour
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

extrapolation methods; orthogonal and biorthogonal polynomials; Padé approximation; Lanczos method

• Wydawca: Institute of Mathematics Polish Academy of Sciences
• Czasopismo: Applicationes Mathematicae
• Rocznik: 1999
• Tom: 26
• Numer: 1
• Strony: 33-62

Daty

wydano

1999

otrzymano

1998-07-06

Twórcy

autor

E. H. Ayachour

• Laboratoire d'Analyse Numérique et d'Optimisation, UFR IEEA-M3

Bibliografia

• [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.