A Geometric Approach to Approximating the Limit Set of Eigenvalues for Banded Toeplitz Matrices
Teodor Bucht, Jacob S. Christiansen · SIAM Journal on Matrix Analysis and Applications · 2024
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 [Formula: see text], where [Formula: see text] is the symbol of the banded Toeplitz matrix. The new approach is geometrical and based on the formula [Formula: see text], where [Formula: see text] is a scaling factor, i.e., [Formula: see text], and [Formula: see text] denotes the spectrum. We show that the full intersection can be approximated by the intersection for a finite number of [Formula: see text]’s and that the intersection of polygon approximations for [Formula: see text] yields an approximating polygon for [Formula: see text] that converges to [Formula: see text] in the Hausdorff metric. Further, we show that one can slightly expand the polygon approximations for [Formula: see text] to ensure that they contain [Formula: see text]. Then, taking the intersection yields an approximating superset of [Formula: see text] which converges to [Formula: see text] in the Hausdorff metric and is guaranteed to contain [Formula: see text]. 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 [Formula: see text], where [Formula: see text] is the number of [Formula: see text]’s and [Formula: see text] is the number of vertices for the polygons approximating [Formula: see text]. Further, we argue that the distance from [Formula: see text] to both the approximating polygon and the approximating superset decreases as [Formula: see text] for most of [Formula: see text], where [Formula: see text] is the number of elementary operations required by the algorithm.