Precise asymptotic expansions for the eigenvalues of a Toeplitz matrix (Formula presented.), 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 (Formula presented.) is an (Formula presented.) matrix-valued trigonometric polynomial with (Formula presented.), and (Formula presented.) is the block Toeplitz matrix generated by (Formula presented.), whose size is (Formula presented.). The case (Formula presented.) 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 (Formula presented.) Lagrangian Finite Element approximation of a second order elliptic differential problem. Numerical results are presented and critically discussed.

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

Furci, Isabella;Serra-Capizzano, Stefano
2018-01-01

Abstract

Precise asymptotic expansions for the eigenvalues of a Toeplitz matrix (Formula presented.), 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 (Formula presented.) is an (Formula presented.) matrix-valued trigonometric polynomial with (Formula presented.), and (Formula presented.) is the block Toeplitz matrix generated by (Formula presented.), whose size is (Formula presented.). The case (Formula presented.) 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 (Formula presented.) Lagrangian Finite Element approximation of a second order elliptic differential problem. Numerical results are presented and critically discussed.
2018
BIT
http://www.kluweronline.com/issn/0006-3835
Asymptotic eigenvalue expansion; Block matrices; Eigenvalues; Extrapolation; Polynomial interpolation; Software; Computer Networks and Communications; Computational Mathematics; Applied Mathematics
Ekström, Sven-Erik; Furci, Isabella; Serra-Capizzano, Stefano
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11383/2073477
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 13
  • ???jsp.display-item.citation.isi??? 12
social impact