Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

A GEOMETRIC APPROACH TO APPROXIMATING THE LIMIT SET OF EIGENVALUES FOR BANDED TOEPLITZ MATRICES

Bucht, Teodor and Christiansen, Jacob S. LU (2024) In SIAM Journal on Matrix Analysis and Applications 45(3). p.1573-1598
Abstract

This article is about finding the limit set for banded Toeplitz matrices. Our main result is a new approach to approximate the limit set Λ(b), where b is the symbol of the banded Toeplitz matrix. The new approach is geometrical and based on the formula Λ(b) = ∩ρ∊(0, ∞) sp T (bρ), where ρ is a scaling factor, i.e., bρ(t):= b(ρt), and sp(∙) denotes the spectrum. We show that the full intersection can be approximated by the intersection for a finite number of ρ's and that the intersection of polygon approximations for sp T (bρ) yields an approximating polygon for Λ(b) that converges to Λ(b) in the Hausdorff metric. Further, we show that one can slightly expand the polygon approximations for sp T... (More)

This article is about finding the limit set for banded Toeplitz matrices. Our main result is a new approach to approximate the limit set Λ(b), where b is the symbol of the banded Toeplitz matrix. The new approach is geometrical and based on the formula Λ(b) = ∩ρ∊(0, ∞) sp T (bρ), where ρ is a scaling factor, i.e., bρ(t):= b(ρt), and sp(∙) denotes the spectrum. We show that the full intersection can be approximated by the intersection for a finite number of ρ's and that the intersection of polygon approximations for sp T (bρ) yields an approximating polygon for Λ(b) that converges to Λ(b) in the Hausdorff metric. Further, we show that one can slightly expand the polygon approximations for sp T (bρ) to ensure that they contain sp T (bρ). Then, taking the intersection yields an approximating superset of Λ(b) which converges to Λ(b) in the Hausdorff metric and is guaranteed to contain Λ(b). Combining the established algebraic (root-finding) method with our approximating superset, we are able to give an explicit bound on the Hausdorff distance to the true limit set. We implement the algorithm in Python and test it. It performs on par to and better in some cases than existing algorithms. We argue, but do not prove, that the average time complexity of the algorithm is O(n2 + mn log m), where n is the number of ρ's and m is the number of vertices for the polygons approximating sp T (bρ). Further, we argue that the distance from Λ(b) to both the approximating polygon and the approximating superset decreases as O(1/√k) for most of Λ(b), where k is the number of elementary operations required by the algorithm.

(Less)
Please use this url to cite or link to this publication:
author
and
organization
publishing date
type
Contribution to journal
publication status
published
subject
keywords
banded Toeplitz matrices, limiting set of eigenvalues, polygon approximations
in
SIAM Journal on Matrix Analysis and Applications
volume
45
issue
3
pages
26 pages
publisher
Society for Industrial and Applied Mathematics
external identifiers
  • scopus:85202344510
ISSN
0895-4798
DOI
10.1137/23M1587804
language
English
LU publication?
yes
id
a6b556f5-8f97-4f94-832a-f65f91844bad
date added to LUP
2024-10-30 14:40:14
date last changed
2025-10-09 11:28:52
@article{a6b556f5-8f97-4f94-832a-f65f91844bad,
  abstract     = {{<p>This article is about finding the limit set for banded Toeplitz matrices. Our main result is a new approach to approximate the limit set Λ(b), where b is the symbol of the banded Toeplitz matrix. The new approach is geometrical and based on the formula Λ(b) = ∩<sub>ρ∊(0, ∞)</sub> sp T (b<sub>ρ</sub>), where ρ is a scaling factor, i.e., b<sub>ρ</sub>(t):= b(ρt), and sp(∙) denotes the spectrum. We show that the full intersection can be approximated by the intersection for a finite number of ρ's and that the intersection of polygon approximations for sp T (b<sub>ρ</sub>) yields an approximating polygon for Λ(b) that converges to Λ(b) in the Hausdorff metric. Further, we show that one can slightly expand the polygon approximations for sp T (b<sub>ρ</sub>) to ensure that they contain sp T (b<sub>ρ</sub>). Then, taking the intersection yields an approximating superset of Λ(b) which converges to Λ(b) in the Hausdorff metric and is guaranteed to contain Λ(b). Combining the established algebraic (root-finding) method with our approximating superset, we are able to give an explicit bound on the Hausdorff distance to the true limit set. We implement the algorithm in Python and test it. It performs on par to and better in some cases than existing algorithms. We argue, but do not prove, that the average time complexity of the algorithm is O(n<sup>2</sup> + mn log m), where n is the number of ρ's and m is the number of vertices for the polygons approximating sp T (b<sub>ρ</sub>). Further, we argue that the distance from Λ(b) to both the approximating polygon and the approximating superset decreases as O(1/√k) for most of Λ(b), where k is the number of elementary operations required by the algorithm.</p>}},
  author       = {{Bucht, Teodor and Christiansen, Jacob S.}},
  issn         = {{0895-4798}},
  keywords     = {{banded Toeplitz matrices; limiting set of eigenvalues; polygon approximations}},
  language     = {{eng}},
  number       = {{3}},
  pages        = {{1573--1598}},
  publisher    = {{Society for Industrial and Applied Mathematics}},
  series       = {{SIAM Journal on Matrix Analysis and Applications}},
  title        = {{A GEOMETRIC APPROACH TO APPROXIMATING THE LIMIT SET OF EIGENVALUES FOR BANDED TOEPLITZ MATRICES}},
  url          = {{http://dx.doi.org/10.1137/23M1587804}},
  doi          = {{10.1137/23M1587804}},
  volume       = {{45}},
  year         = {{2024}},
}