A matrix-less and parallel interpolation-extrapolation algorithm for computing the eigenvalues of preconditioned banded symmetric Toeplitz matrices

摘要

In the past few years, Bogoya, Bottcher, 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)T--1(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)T--1(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.