Ekström, Sven-Erik; Garoni, Carlo A matrix-less and parallel interpolation-extrapolation algorithm for computing the eigenvalues of preconditioned banded symmetric Toeplitz matrices. (English) Zbl 1455.65051 Numer. Algorithms 80, No. 3, 819-848 (2019). Summary: In the past few years, Bogoya, Böttcher, Grudsky, and Maximenko obtained the precise asymptotic expansion for the eigenvalues of a Toeplitz matrix \(T_n(f)\), under suitable assumptions on the generating function \(f\), as the matrix size \(n\) goes to infinity. On the basis of several numerical experiments, it was conjectured by Serra-Capizzano that a completely analogous expansion also holds for the eigenvalues of the preconditioned Toeplitz matrix \(T_n(u)^{-1}T_n(v)\), provided \(f=v/u\) is monotone and further conditions on \(u\) and \(v\) are satisfied. Based on this expansion, we here propose and analyze an interpolation-extrapolation algorithm for computing the eigenvalues of \(T_n(u)^{-1}T_n(v)\). The algorithm is suited for parallel implementation and it may be called “matrix-less” as it does not need to store the entries of the matrix. We illustrate the performance of the algorithm through numerical experiments and we also present its generalization to the case where \(f=v/u\) is non-monotone. Cited in 16 Documents MSC: 65F15 Numerical computation of eigenvalues and eigenvectors of matrices 15B05 Toeplitz, Cauchy, and related matrices 65D05 Numerical interpolation 65B05 Extrapolation to the limit, deferred corrections Keywords:preconditioned Toeplitz matrices; asymptotic eigenvalue expansion; polynomial interpolation × Cite Format Result Cite Review PDF Full Text: DOI References: [1] Ahmad, F., Al-Aidarous, E.S., Alrehaili, D.A., Ekström, S.-E., Furci, I., Serra-Capizzano, S.: Are the eigenvalues of preconditioned banded symmetric Toeplitz matrices known in almost closed form? Numer. Alg. (in press). https://doi.org/10.1007/s11075-017-0404-z · Zbl 1398.65055 [2] Arbenz, P.: Computing the eigenvalues of banded symmetric Toeplitz matrices. SIAM J. Sci. Stat. Comput. 12, 743-754 (1991) · Zbl 0727.65028 · doi:10.1137/0912039 [3] Badía, J.M., Vidal, A.M.: Parallel algorithms to compute the eigenvalues and eigenvectors of symmetric Toeplitz matrices. Parallel Algorithms Appl. 13, 75-93 (2000) · Zbl 0916.68071 · doi:10.1080/01495739808947361 [4] Bini, D., Di Benedetto, F: Solving the generalized eigenvalue problem for rational Toeplitz matrices. SIAM J. Matrix Anal. Appl. 11, 537-552 (1990) · Zbl 0724.65037 · doi:10.1137/0611038 [5] Bini, D., Pan, V: Efficient algorithms for the evaluation of the eigenvalues of (block) banded Toeplitz matrices. Math. Comput. 50, 431-448 (1988) · Zbl 0646.65035 · doi:10.1090/S0025-5718-1988-0929545-5 [6] Bogoya, J.M., Böttcher, A., Grudsky, S.M., Maximenko, E.A.: Eigenvalues of Hermitian Toeplitz matrices with smooth simple-loop symbols. J. Math. Anal. Appl. 422, 1308-1334 (2015) · Zbl 1302.65086 · doi:10.1016/j.jmaa.2014.09.057 [7] Bogoya, J.M., Böttcher, A., Grudsky, S.M., Maximenko, E.A.: Maximum norm versions of the Szegő and Avram-Parter theorems for Toeplitz matrices. J. Approx. Theory 196, 79-100 (2015) · Zbl 1320.15028 · doi:10.1016/j.jat.2015.03.003 [8] Bogoya, J.M., Grudsky, S.M., Maximenko, E.A.: Eigenvalues of Hermitian Toeplitz matrices generated by simple-loop symbols with relaxed smoothness. Oper. Theory Adv. Appl. 259, 179-212 (2017) · Zbl 1468.15007 · doi:10.1007/978-3-319-49182-0_11 [9] Böttcher, A., Silbermann, B.: Introduction to Large Truncated Toeplitz Matrices. Springer, New York (1999) · Zbl 0916.15012 · doi:10.1007/978-1-4612-1426-7 [10] Böttcher, A., Grudsky, S.M., Maximenko, E.A.: Inside the eigenvalues of certain Hermitian Toeplitz band matrices. J. Comput. Appl. Math. 233, 2245-2264 (2010) · Zbl 1195.15009 · doi:10.1016/j.cam.2009.10.010 [11] Brezinski, C., Redivo Zaglia, M.: Extrapolation Methods: Theory and Practice. North-Holland, Elsevier Science Publishers B.V., Amsterdam (1991) · Zbl 0744.65004 [12] Davis, P.J.: Interpolation and Approximation. Dover, New York (1975) · Zbl 0329.41010 [13] Ekström, S.-E., Garoni, C., Serra-Capizzano, S: Are the eigenvalues of banded symmetric Toeplitz matrices known in almost closed form? Exper. Math. (in press). https://doi.org/10.1080/10586458.2017.1320241 [14] Garoni, C., Serra-Capizzano, S.: Generalized Locally Toeplitz Sequences: Theory and Applications, vol. I. Springer, Cham (2017) · Zbl 1376.15002 · doi:10.1007/978-3-319-53679-8 [15] Stoer, J., Bulirsch, R.: Introduction to Numerical Analysis, 3rd edn. Springer, New York (2010) · Zbl 0423.65002 [16] Trench, W.F.: On the eigenvalue problem for Toeplitz band matrices. Linear Algebra Appl. 64, 199-214 (1985) · Zbl 0568.15005 · doi:10.1016/0024-3795(85)90277-0 [17] Trench, W.F.: Characteristic polynomials of symmetric rationally generated Toeplitz matrices. Linear Multilinear Algebra 21, 289-296 (1987) · Zbl 0651.15009 · doi:10.1080/03081088708817803 [18] Trench, W.F.: Numerical solution of the eigenvalue problem for symmetric rationally generated Toeplitz matrices. SIAM J. Matrix Anal. Appl. 9, 291-303 (1988) · Zbl 0647.65023 · doi:10.1137/0609023 [19] Trench, W.F.: Numerical solution of the eigenvalue problem for Hermitian Toeplitz matrices. SIAM J. Matrix Anal. Appl. 10, 135-146 (1989) · Zbl 0676.65027 · doi:10.1137/0610010 [20] Trench, W.F.: Numerical solution of the eigenvalue problem for efficiently structured Hermitian matrices. Linear Algebra Appl. 154-156, 415-432 (1991) · Zbl 0733.65020 · doi:10.1016/0024-3795(91)90387-C This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.