Uppsala University
Department of Information Technology

### Technical Report 2018-005

# Exact Formulae and Matrix-Less Eigensolvers for Block Banded Symmetric Toeplitz Matrices

### Sven-Erik Ekström, Isabella Furci, and Stefano Serra-Capizzano

March 2018

**Abstract:**Precise asymptotic expansions for the eigenvalues of a Toeplitz matrix *T*_{n}(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 *sge 1*, and *T*_{n}(**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 **Q**_{p} Lagrangian Finite Element approximation of a second order elliptic differential problem. Numerical results are presented and critically discussed.

Available as
PDF (1.37 MB, no cover)

Download BibTeX entry.