Exact formulae and matrix-less eigensolvers for block banded symmetric Toeplitz matrices

Precise asymptotic expansions for the eigenvalues of a Toeplitz matrix Tn(f) , as the matrix size n tends to infinity, have recently been obtained, under suitable assumptions on the associated generating function f. A restriction is that f has to be polynomial, monotone, and scalar-valued. In this paper we focus on the case where f is an s× s matrix-valued trigonometric polynomial with s≥ 1 , and Tn(f) is the block Toeplitz matrix generated by f, whose size is N(n, s) = sn. The case s= 1 corresponds to that already treated in the literature. We numerically derive conditions which ensure the existence of an asymptotic expansion for the eigenvalues. Such conditions generalize those known for the scalar-valued setting. Furthermore, following a proposal in the scalar-valued case by the first author, Garoni, and the third author, we devise an extrapolation algorithm for computing the eigenvalues of banded symmetric block Toeplitz matrices with a high level of accuracy and a low computational cost. The resulting algorithm is an eigensolver that does not need to store the original matrix, does not need to perform matrix-vector products, and for this reason is called matrix-less. We use the asymptotic expansion for the efficient computation of the spectrum of special block Toeplitz structures and we provide exact formulae for the eigenvalues of the matrices coming from the Qp Lagrangian Finite Element approximation of a second order elliptic differential problem. Numerical results are presented and critically discussed.