kth.sePublications KTH
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
A geometric approach to approximating the limit set of eigenvalues for banded Toeplitz matrices
KTH, School of Engineering Sciences (SCI), Mathematics (Dept.), Probability, Mathematical Physics and Statistics. Centre for Mathematical Sciences, Lund University, Box 118, 22100 Lund, Sweden.
Centre for Mathematical Sciences, Lund University, Box 118, 22100 Lund, Sweden, Box 118.
2024 (English)In: SIAM Journal on Matrix Analysis and Applications, ISSN 0895-4798, E-ISSN 1095-7162, Vol. 45, no 3, p. 1573-1598Article in journal (Refereed) Published
Abstract [en]

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.

Place, publisher, year, edition, pages
Society for Industrial & Applied Mathematics (SIAM) , 2024. Vol. 45, no 3, p. 1573-1598
Keywords [en]
banded Toeplitz matrices, limiting set of eigenvalues, polygon approximations
National Category
Mathematical Analysis Computational Mathematics
Identifiers
URN: urn:nbn:se:kth:diva-353482DOI: 10.1137/23M1587804ISI: 001343416500015Scopus ID: 2-s2.0-85202344510OAI: oai:DiVA.org:kth-353482DiVA, id: diva2:1899157
Note

QC 20240930

Available from: 2024-09-19 Created: 2024-09-19 Last updated: 2025-12-05Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full textScopus

Authority records

Bucht, Teodor

Search in DiVA

By author/editor
Bucht, Teodor
By organisation
Probability, Mathematical Physics and Statistics
In the same journal
SIAM Journal on Matrix Analysis and Applications
Mathematical AnalysisComputational Mathematics

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 71 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf