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

Ayachour, E.

Applicationes Mathematicae, Tome 26 (1999), p. 33-62 / Harvested from The Polish Digital Mathematics Library

Résumé

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.

Détail

Publié le : 1999-01-01

Zbl 1012.65038

EUDML-ID : urn:eudml:doc:219225

Bibliographie

[000] [1] E. H. Ayachour, Avoiding the look-ahead in the Lanczos method, Publ. ANO-363, Univ. des Sciences et Technologies de Lille, 1996.

[001] [2] E. H. Ayachour, Application de la biorthogonalité aux méthodes de projection, thèse, Université des Sciences et Technologies de Lille, 1998.

[002] [3] C. Brezinski, Computation of Padé approximants and continued fractions, J. Comput. Appl. Math. 2 (1976), 113-123. | Zbl 0341.65007

[003] [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. | Zbl 0356.42016

[004] [5] C. Brezinski, Padé-Type Approximation and General Orthogonal Polynomials, Birkhäuser, Basel, 1980.

[005] [6] C. Brezinski, Other manifestations of the Schur complement, Linear Algebra Appl. 111 (1988), 231-247. | Zbl 0662.65037

[006] [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.

[007] [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.

[008] [9] C. Brezinski and M. Redivo Zaglia, Extrapolation Methods--Theory and Practice, North-Holland, Amsterdam, 1994. | Zbl 0802.65029

[009] [10] C. Brezinski and M. Redivo Zaglia, Look-ahead in Bi-CGSTAB and other methods for linear systems, BIT 35 (1995), 169-201.

[010] [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.

[011] [12] C. Brezinski, M. Redivo Zaglia and H. Sadok, Avoiding breakdown and near-breakdown in Lanczos type algorithms, ibid. 1 (1991), 261-284. | Zbl 0748.65033

[012] [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. | Zbl 0739.65027

[013] [14] C. Brezinski and H. Sadok, Lanczos-type algorithms for solving systems of linear equations, Appl. Numer. Math. 11 (1993), 443-473. | Zbl 0780.65020

[014] [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.

[015] [16] A. Draux, Polynômes Orthogonaux Formels. Applications, Lecture Notes in Math. 974, Springer, Berlin, 1983. | Zbl 0504.42001

[016] [17] A. Draux et P. Van Ingelandt, Polynômes Orthogonaux et Approximants de Padé. Logiciels, Technip, Paris, 1987.

[017] [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. | Zbl 0770.65022

[018] [19] W. B. Gragg and A. Lindquist, On the partial realization problem, Linear Algebra Appl. 50 (1983), 277-319. | Zbl 0519.93024

[019] [20] M. H. Gutknecht, Variants of Bi-CGSTAB for matrices with complex spectrum, SIAM J. Sci. Comput. 193 (1993), 1020-1033. | Zbl 0837.65031

[020] [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. | Zbl 0760.65039

[021] [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. | Zbl 0852.41012

[022] [23] M. H. Gutknecht and M. Hochbruck, Look-ahead Levinson and Schur algorithms for non-Hermitian Toeplitz systems, Numer. Math. 70 (1995), 181-227. | Zbl 0823.65023

[023] [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. | Zbl 0535.65018

[024] [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.

[025] [26] M. A. Piñar and V. Ramirez, Recursive inversion of Hankel matrices, Monogr. Acad. Ciencias Zaragoza 1 (1988), 119-128. | Zbl 0684.65020

[026] [27] P. Sonneveld, CGS: a fast Lanczos-type solver for nonsymmetric linear systems, SIAM J. Sci. Statist. Comput. 10 (1989), 36-52. | Zbl 0666.65029

[027] [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. | Zbl 0761.65023

[028] [29] H. Van Rossum, Contiguous orthogonal systems, Koninkl. Nederl. Akad. Wet- ensch. Ser. A 63 (1960), 323-332. | Zbl 0099.05502

[029] [30] P. Wynn, Upon systems of recursions which obtain among the quotients of Padé table, Numer. Math. 8 (1966), 264-269. | Zbl 0163.39502

[030] [31] D. M. Young and K. C. Jea, Generalized conjugate-gradient acceleration for nonsymmetrizable iterative methods, Linear Algebra Appl. 34 (1980), 159-194. | Zbl 0463.65025

[031] [32] M. Ziegler, Generalized biorthogonal bases and tridiagonalisation of matrices, Report Nr. 22 (1995), Universität Tübingen, Biomathematik.

[032] [33] M. Ziegler, Generalized biorthogonal bases and tridiagonalisation of matrices, Numer. Math. 77 (1997), 407-421. | Zbl 0884.65030