Search

The eigenvalues of Toeplitz matrices T n (f) with a real-valued generating function f , satisfying some conditions and tracing out a simple loop over the interval [ − π , π ] , are known to admit an asymptotic expansion with the form λ j (T n (f)) = f (σ j , n) + c 1 (σ j , n) h + c 2 (σ j , n) h 2 + O (h 3) , where h = 1 / (n + 1) , σ j , n = π j h , and c k are some bounded coefficients depending only on f. The numerical results presented in the literature suggest that the effective conditions for the expansion to hold are weaker and reduce to a fixed smoothness and to having only two intervals of monotonicity over [ − π , π ]. In this article we investigate the superposition caused over this expansion, when considering the following linear combination λ j (T n (f 0) + β n , 1 T n (f 1) + β n , 2 T n (f 2)) , where β n , 1 , β n , 2 are certain constants depending on n and the generating functions f 0 , f 1 , f 2 are either simple loop or satisfy the weaker conditions mentioned before. We formally obtain an asymptotic expansion in this setting under simple-loop related assumptions, and we show numerically that there is much more to investigate, opening the door to linear in time algorithms for the computation of eigenvalues of large matrices of this type including a multilevel setting. The problem is of concrete interest, considering spectral features of matrices stemming from the numerical approximation of standard differential operators and distributed order fractional differential equations, via local methods such as Finite Differences, Finite Elements, and Isogeometric Analysis. [ABSTRACT FROM AUTHOR]

We study the individual behavior of the eigenvalues of the laplacian matrices of the cyclic graph of order n , where one edge has weight α ∈ C , with Re (α) < 0 , and all the others have weights 1. This paper is a sequel of a previous one where we considered Re (α) ∈ [ 0 , 1 ] (Grudsky et al., 2022 [12]). We prove that for Re (α) < 0 and n > Re (α − 1) / Re (α) , one eigenvalue is negative while the others belong to [ 0 , 4 ] and are distributed as the function x ↦ 4 sin 2 ⁡ (x / 2). Additionally, we prove that as n tends to ∞, the outlier eigenvalue converges exponentially to 4 Re (α) 2 / (2 Re (α) − 1). We give exact formulas for half of the inner eigenvalues, while for the others we justify the convergence of Newton's method and fixed-point iteration method. We find asymptotic expansions, as n tends to ∞, both for the eigenvalues belonging to [ 0 , 4 ] and the outlier. We also compute the eigenvectors and their norms. [ABSTRACT FROM AUTHOR]

It is known that the generating function of a sequence of Toeplitz matrices may not describe the asymptotic distribution of the eigenvalues of the considered matrix sequence in the non‐Hermitian setting. In a recent work, under the assumption that the eigenvalues are real, admitting an asymptotic expansion whose first term is the distribution function, fast algorithms computing all the spectra were proposed in different settings. In the current work, we extend this idea to non‐Hermitian Toeplitz matrices with complex eigenvalues, in the case where the range of the generating function does not disconnect the complex field or the limiting set of the spectra, as the matrix‐size tends to infinity, has one nonclosed analytic arc. For a generating function having a power singularity, we prove the existence of an asymptotic expansion, that can be used as a theoretical base for the respective numerical algorithm. Different generating functions are explored, highlighting different numerical and theoretical aspects; for example, non‐Hermitian and complex symmetric matrix sequences, the reconstruction of the generating function, a consistent eigenvalue ordering, the requirements of high‐precision data types. Several numerical experiments are reported and critically discussed, and avenues of possible future research are presented. [ABSTRACT FROM AUTHOR]

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(n²+mnlogm), 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. [ABSTRACT FROM AUTHOR]

In this article, we give an explicit expression for calculating the arbitrary positive integer powers of the Kronecker sum of two tridiagonal Toeplitz matrices. [ABSTRACT FROM AUTHOR]

Understanding the eigenvalue distribution of sequence Toeplitz matrices has advanced significantly in recent years. Notable contributors include Bogoya, Grudsky, Böttcher, and Maximenko, who have derived precise asymptotic expansions for these eigenvalues under certain conditions related to the generating function as the matrix size increases. Building on this foundation, the Stefano Serra-Capizzano conjectured that, under certain assumptions about Ω and Φ, a similar expansion may hold for the eigenvalues of a sequence of preconditioned Toeplitz matrices T-1n (Φ)Tn(Ω), given a monotonic ratio r=Ω/Φ. In contrast to current eigenvalue solvers, this work presents a novel method for efficiently calculating the eigenvalues of a sequence of large preconditioned banded symmetric Toeplitz matrices (PBST). Our algorithm uses a higher-order spline fitting extrapolation technique to gather spectral data from a smaller sequence of PBST matrices in order to forecast the spectrum of bigger matrices. [ABSTRACT FROM AUTHOR]

In this paper, a Toeplitz construction method based on eigenvalues and eigenvectors is proposed to combine with traditional denoising algorithms, including fractional low-order moment (FLOM), phased fractional low-order moment (PFLOM), and correntropy-based correlation (CRCO) methods. It can improve the direction of arrival (DOA) estimation of signals in impulsive noise. Firstly, the algorithm performs eigenvalue decomposition on the received covariance matrix to obtain eigenvectors and eigenvalues, and then the Toeplitz matrix is created according to the eigenvectors corresponding to its eigenvalues. Secondly, the spatial averaging method is used to obtain an unbiased estimate of the Toeplitz matrix, which is then weighted and added based on the corresponding eigenvalues. Next, the noise subspace of the Toeplitz matrix is reconstructed to obtain the one that has less angle information. Finally, the DOA of the coherent signal is estimated using the Multiple Signal Classification (MUSIC) algorithm. The improved method based on the Toeplitz matrix can not only suppress the effect of impulsive noise but can also solve the problem of aperture loss due to its decoherence. A series of simulations have shown that they have better performances than other algorithms. [ABSTRACT FROM AUTHOR]

This paper focuses on the reversibility of multidimensional linear cellular automata with an intermediate boundary condition. We begin by addressing the matrix representation of these automata, and the question of reversibility boils down to the invertibility of this matrix representation. We introduce a decomposition method that factorizes the matrix representation into a Kronecker sum of significantly smaller matrices. The invertibility of the matrix hinges on determining whether zero can be expressed as the sum of eigenvalues of these smaller matrices, which happen to be tridiagonal Toeplitz matrices. Notably, each of these smaller matrices represents a one-dimensional cellular automaton. Leveraging the rich body of research on the eigenvalue problem of Toeplitz matrices, our result provides an efficient algorithm for addressing the reversibility problem. As an application, we show that there is no reversible nontrivial linear cellular automaton over Z 2 . This paper focuses on the reversibility of multidimensional linear cellular automata with an intermediate boundary condition. We begin by addressing the matrix representation of these automata, and the question of reversibility boils down to the invertibility of this matrix representation. We introduce a decomposition method that factorizes the matrix representation into a Kronecker sum of significantly smaller matrices. The invertibility of the matrix hinges on determining whether zero can be expressed as the sum of eigenvalues of these smaller matrices, which happen to be tridiagonal Toeplitz matrices. Notably, each of these smaller matrices represents a one-dimensional cellular automaton. Leveraging the rich body of research on the eigenvalue problem of Toeplitz matrices, our result provides an efficient algorithm for addressing the reversibility problem. As an application, we show that there is no reversible nontrivial linear cellular automaton over . [ABSTRACT FROM AUTHOR]

The present work is devoted to the eigenvalue asymptotic expansion of the Toeplitz matrix Tn(a), whose generating function a is complex-valued and has a power singularity at one point. As a consequence, Tn(a) is non-Hermitian and we know that in this setting, the eigenvalue computation is a nontrivial task for large sizes. First we follow the work of Bogoya, Böttcher, Grudsky, and Maximenko and deduce a complete asymptotic expansion for the eigenvalues. In a second step, we apply matrixless algorithms, in the spirit of the work by Ekström, Furci, Garoni, Serra-Capizzano et al., for computing those eigenvalues. Since the inner and extreme eigenvalues have different asymptotic behaviors, we worked on them independently and combined the results to produce a high precision global numerical and matrixless algorithm. The numerical results are very precise, and the computational cost of the proposed algorithms is independent of the size of the considered matrices for each eigenvalue, which implies a linear cost when the entire spectrum is computed. From the viewpoint of real-world applications, we emphasize that the class under consideration includes the matrices stemming from the numerical approximation of fractional diffusion equations. In the final section a concise discussion on the matter and a few open problems are presented. [ABSTRACT FROM AUTHOR]

We introduce a new block preconditioner for the solution of weighted Toeplitz regularized least-squares problems written in augmented system form. The proposed preconditioner is obtained based on the new splitting of coefficient matrix which results in an unconditionally convergent stationary iterative method. Spectral analysis of the preconditioned matrix is investigated. In particular, we show that the preconditioned matrix has a very nice eigenvalue distribution which can lead to fast convergence of the preconditioned Krylov subspace methods such as GMRES. Numerical experiments are reported to demonstrate the performance of preconditioner used with GMRES method in the solution of augmented system form of weighted Toeplitz regularized least-squares problems. [ABSTRACT FROM AUTHOR]

The present work is devoted to the construction of an asymptotic expansion for the eigenvalues of a Toeplitz matrix Tn(a)$$ {T}_n(a) $$ as n$$ n $$ goes to infinity, with a continuous and real‐valued symbol a$$ a $$ having a power singularity of degree γ$$ \gamma $$ with 1<γ<2$$ 1<\gamma <2 $$, at one point. The resulting matrix is dense and its entries decrease slowly to zero when moving away from the main diagonal, we apply the so called simple‐loop (SL) method for constructing and justifying a uniform asymptotic expansion for all the eigenvalues. Note however, that the considered symbol does not fully satisfy the conditions imposed in previous works, but only in a small neighborhood of the singularity point. In the present work: (i) We construct and justify the asymptotic formulas of the SL method for the eigenvalues λj(Tn(a))$$ {\lambda}_j\left({T}_n(a)\right) $$ with j⩾εn$$ j\geqslant \varepsilon n $$, where the eigenvalues are arranged in nondecreasing order and ε$$ \varepsilon $$ is a sufficiently small fixed number. (ii) We show, with the help of numerical calculations, that the obtained formulas give good approximations in the case j<εn$$ j<\varepsilon n $$. (iii) We numerically show that the main term of the asymptotics for eigenvalues with j<εn$$ j<\varepsilon n $$, formally obtained from the formulas of the SL method, coincides with the main term of the asymptotics constructed and justified in the classical works of Widom and Parter. [ABSTRACT FROM AUTHOR]

Total fractional-order variation (TFOV) in image deblurring problems can reduce/remove the staircase problems observed with the image deblurring technique by using the standard total variation (TV) model. However, the discretization of the Euler–Lagrange equations associated with the TFOV model generates a saddle point system of equations where the coefficient matrix of this system is dense and ill conditioned (it has a huge condition number). The ill-conditioned property leads to slowing of the convergence of any iterative method, such as Krylov subspace methods. One treatment for the slowness property is to apply the preconditioning technique. In this paper, we propose a block triangular preconditioner because we know that using the exact triangular preconditioner leads to a preconditioned matrix with exactly two distinct eigenvalues. This means that we need at most two iterations to converge to the exact solution. However, we cannot use the exact preconditioner because the Shur complement of our system is of the form S = K * K + λ L α which is a huge and dense matrix. The first matrix, K * K , comes from the blurred operator, while the second one is from the TFOV regularization model. To overcome this difficulty, we propose two preconditioners based on the circulant and standard TV matrices. In our algorithm, we use the flexible preconditioned GMRES method for the outer iterations, the preconditioned conjugate gradient (PCG) method for the inner iterations, and the fixed point iteration (FPI) method to handle the nonlinearity. Fast convergence was found in the numerical results by using the proposed preconditioners. [ABSTRACT FROM AUTHOR]

Let Ip,q = Ip ⊕−Iq. Pseudounitary eigenvalues of a positive definite matrix A are the moduli of conventional eigenvalues of the matrix Ip,qA. They are invariants of pseudounitary *-congruences performed with A. For a fixed n = p+q, the sum of the squares σp,q of these numbers is a function of the parameter p. In general, its values for different p can differ very significantly. However, if A is the tridiagonal Toeplitz matrix with an entry a ≥ 2 on the principal diagonal and the entry −1 on the two neighboring diagonals, then σp,q has the same value for all p. This nontrivial fact is explained in the paper. [ABSTRACT FROM AUTHOR]

The present paper is a survey of some of the authors' results on the asymptotic behavior of individual eigenvalues and eigenvectors of sequences of Toeplitz matrices when their size tends to infinity. The symbols of the matrices are supposed to have power singularities and are special cases of so-called Fisher–Hartwig symbols. [ABSTRACT FROM AUTHOR]

We propose recursive algorithms to update an orthogonal numerical basis matrix of the null space of the block row, (banded) block Toeplitz, and block Macaulay matrix, which is the multivariate generalization of the (banded) block Toeplitz matrix. These structured matrices are often constructed in an iterative way, and, for some applications, a basis matrix of the null space is required in every iteration. Consequently, recursively updating a numerical basis matrix of the null space, while exploiting the inherent structure of the matrices involved, induces large savings in the computation time. Moreover, we also develop a sparse adaptation of one of the recursive algorithms that avoids the explicit construction of the block Macaulay matrix and results in a considerable reduction of the required memory. We provide several numerical experiments to illustrate the proposed algorithms: for example, we solve four multiparameter eigenvalue problems via the null space of the block Macaulay matrix and notice that the recursive and sparse approach are, on average, 450 and 1300 times faster than the standard approach, respectively. [ABSTRACT FROM AUTHOR]

We introduce a new family of linearizations of rational matrices, which we call block full rank linearizations. The theory of block full rank linearizations is useful as it establishes very simple criteria to determine if a pencil is a linearization of a rational matrix in a target set or in the whole underlying field, by using rank conditions. Block full rank linearizations allow us to recover locally information about zeros and poles. To recover the pole-zero information at infinity, we will define the grade of the new block full rank linearizations as linearizations at infinity and the notion of degree of a rational matrix will be used. Moreover, the eigenvectors of a rational matrix associated with its eigenvalues in a target set can be obtained from the eigenvectors of its block full rank linearizations in that set. This new family of linearizations generalizes and includes the structures appearing in most of the linearizations for rational matrices constructed in the literature. As example, we study the structure and properties of the linearizations in [P. Lietaert et al., Automatic rational approximation and linearization of nonlinear eigenvalue problems, 2021]. [ABSTRACT FROM AUTHOR]

We consider the eigenvalues of a fixed, non-normal matrix subject to a small additive perturbation. In particular, we consider the case when the fixed matrix is a banded Toeplitz matrix, where the bandwidth is allowed to grow slowly with the dimension, and the perturbation matrix is drawn from one of several different random matrix ensembles. We establish a number of non-asymptotic results for the eigenvalues of this model, including a local law and a rate of convergence in Wasserstein distance of the empirical spectral measure to its limiting distribution. In addition, we define the classical locations of the eigenvalues and prove a rigidity result showing that, on average, the eigenvalues concentrate closely around their classical locations. While proving these results we also establish a number of auxiliary results that may be of independent interest, including a quantitative version of the Tao–Vu replacement principle, a general least singular value bound that applies to adversarial models, and a description of the limiting empirical spectral measure for random multiplicative perturbations. [ABSTRACT FROM AUTHOR]

A quasi-Toeplitz (QT) matrix is a semi-infinite matrix of the form A = T (a) + E where T(a) is the Toeplitz matrix with entries (T (a)) i , j = a j - i , for a j - i ∈ C , i , j ≥ 1 , while E is a matrix representing a compact operator in ℓ 2 . The matrix A is finitely representable if a k = 0 for k < - m and for k > n , given m , n > 0 , and if E has a finite number of nonzero entries. The problem of numerically computing eigenpairs of a finitely representable QT matrix is investigated, i.e., pairs (λ , v) such that A v = λ v , with λ ∈ C , v = (v j) j ∈ Z + , v ≠ 0 , and ∑ j = 1 ∞ | v j | 2 < ∞ . It is shown that the problem is reduced to a finite nonlinear eigenvalue problem of the kind W U (λ) β = 0 , where W is a constant matrix and U depends on λ and can be given in terms of either a Vandermonde matrix or a companion matrix. Algorithms relying on Newton's method applied to the equation det W U (λ) = 0 are analyzed. Numerical experiments show the effectiveness of this approach. The algorithms have been included in the CQT-Toolbox [Numer. Algorithms 81 (2019), no. 2, 741–769]. [ABSTRACT FROM AUTHOR]

Under appropriate technical assumptions, the simple-loop theory allows to derive various types of asymptotic expansions for the eigenvalues of Toeplitz matrices generated by a function f. Independently and under the milder hypothesis that f is even and monotone over [0,π], matrix-less algorithms have been developed for the fast eigenvalue computation of large Toeplitz matrices, within a linear complexity in the matrix order: behind the high efficiency of such algorithms there are the expansions predicted by the simple-loop theory, combined with the extrapolation idea. Here we focus our attention on a change of variable, followed by the asymptotic expansion of the new variable, and we adapt the matrix-less algorithm to the considered new setting. Numerical experiments show a higher precision (till machine precision) and the same linear computation cost, when compared with the matrix-less procedures already presented in the relevant literature. Among the advantages, we concisely mention the following: (a) when the coefficients of the simple-loop function are analytically known, the algorithm computes them perfectly; (b) while the proposed algorithm is better or at worst comparable to the previous ones for computing the inner eigenvalues, it is vastly better for the computation of the extreme eigenvalues; a mild deterioration in the quality of the numerical experiments is observed when dense Toeplitz matrices are considered, having generating function of low smoothness and not satisfying the simple-loop assumptions. [ABSTRACT FROM AUTHOR]

In this paper we study the eigenvalues of the laplacian matrices of the cyclic graphs with one edge of weight α and the others of weight 1. We denote by n the order of the graph and suppose that n tends to infinity. We notice that the characteristic polynomial and the eigenvalues depend only on Re (α). After that, through the rest of the paper we suppose that 0 < α < 1. It is easy to see that the eigenvalues belong to [ 0 , 4 ] and are asymptotically distributed as the function g (x) = 4 sin 2 ⁡ (x / 2) on [ 0 , π ]. We obtain a series of results about the individual behavior of the eigenvalues. First, we describe more precisely their localization in subintervals of [ 0 , 4 ]. Second, we transform the characteristic equation to a form convenient to solve by numerical methods. In particular, we prove that Newton's method converges for every n ≥ 3. Third, we derive asymptotic formulas for all eigenvalues, where the errors are uniformly bounded with respect to the number of the eigenvalue. [ABSTRACT FROM AUTHOR]

A powerful tool for analyzing and approximating the singular values and eigenvalues of structured matrices is the theory of Generalized Locally Toeplitz (GLT) sequences. By the GLT theory one can derive a function, called the symbol, which describes the singular value or the eigenvalue distribution of the sequence, the latter under precise assumptions. However, for small values of the matrix-size of the considered sequence, the approximations may not be as good as it is desirable, since in the construction of the GLT symbol one disregards small norm and low-rank perturbations. On the other hand, Local Fourier Analysis (LFA) can be used to construct polynomial symbols in a similar manner for discretizations, where the geometric information is present, but the small norm perturbations are retained. The main focus of this paper is the introduction of the concept of sequence of "Toeplitz momentary symbols", associated with a given sequence of truncated Toeplitz-like matrices. We construct the symbol in the same way as in the GLT theory, but we keep the information of the small norm contributions. The low-rank contributions are still disregarded, and we give an idea on the reason why this is negligible in certain cases and why it is not in other cases, being aware that in presence of high nonnormality the same low-rank perturbation can produce a dramatic change in the eigenvalue distribution. Moreover, a difference with respect to the LFA symbols is that GLT symbols and Toeplitz momentary symbols are more general - just Lebesgue measurable - and are applicable to a larger class of matrices, while in the LFA setting only trigonometric polynomials are considered and more specifically those related to the approximation stencils. We show the applicability of the approach which leads to higher accuracy in some cases, when approximating the singular values and eigenvalues of Toeplitz-like matrices using Toeplitz momentary symbols, compared with the GLT symbol. Finally, since for many applications and their analysis it is often necessary to consider non-square Toeplitz matrices, we formalize and provide some useful definitions, applicable for non-square Toeplitz momentary symbols. [ABSTRACT FROM AUTHOR]

This paper considers an inverse eigenvalue problem for bisymmetric nonnegative matrices. We first discuss the specified structure of the bisymmetric matrices. Then for a given set of real numbers of order maximum five with special conditions, we construct a non-negative bisymmetric matrix such that the given set is its spectrum. Finally, we solve the problem for arbitrary order n in the special case of the spectrum. [ABSTRACT FROM AUTHOR]

The lower triangular Toeplitz matrix of Markov parameters is the finite time, time domain equivalent of the z-transfer function of digital systems. Its properties are therefore of interest, and this paper discovers previously unknown properties. The singular value decomposition (SVD) of the Toeplitz matrix contains the matrix of the singular values, and two orthonormal matrices of input and output singular vectors. An understanding of these three matrices in terms of system frequency response has been available for the limiting case when the Toeplitz matrix tends to infinity. Here we obtain an understanding of what happens to the SVD as the dimension is reduced. A system identification algorithm uses the entries in the input/output singular vectors as samples of a continuous time linear system under free response, with the result that such identified dynamics represent the data. Numerical examples for several different system orders are used to show the characteristics of identified eigenvalues embedded in the singular vectors. Each singular vector contains at least a pure frequency that is close to but not the same as the frequency when the dimension tends to infinity. Other eigenvalues help the output singular vectors to end at zero, and the input singular vectors to start at zero, a property of the finite time matrix. Singular vector dynamics in various Iterative Learning Control (ILC) laws are discussed here and numerically investigated, and the dynamics are relevant to basis function ILC, to finite time low pass filtering design, and to new versions of stable inverse theory, among other applications within the theory of control. [ABSTRACT FROM AUTHOR]

Kubo's fluctuation theory of line shape forms the backbone of our understanding of optical and vibrational line shapes, through such concepts as static heterogeneity and motional narrowing. However, the theory does not properly address the effects of quantum coherences on optical line shape, especially in extended systems where a large number of eigenstates are present. In this work, we study the line shape of an exciton in a one-dimensional lattice consisting of regularly placed and equally separated optical two level systems. We consider both linear array and cyclic ring systems of different sizes. Detailed analytical calculations of line shape have been carried out by using Kubo's stochastic Liouville equation (SLE). We make use of the observation that in the site representation, the Hamiltonian of our system with constant off-diagonal coupling J is a tridiagonal Toeplitz matrix (TDTM) whose eigenvalues and eigenfunctions are known analytically. This identification is particularly useful for long chains where the eigenvalues of TDTM help understanding crossover between static and fast modulation limits. We summarize the new results as follows. (i) In the slow modulation limit when the bath correlation time is large, the effects of spatial correlation are not negligible. Here the line shape is broadened and the number of peaks increases beyond the ones obtained from TDTM (constant off-diagonal coupling element J and no fluctuation). (ii) However, in the fast modulation limit when the bath correlation time is small, the spatial correlation is less important. In this limit, the line shape shows motional narrowing with peaks at the values predicted by TDTM (constant J and no fluctuation). (iii) Importantly, we find that the line shape can capture that quantum coherence affects in the two limits differently. (iv) In addition to linear chains of two level systems, we also consider a cyclic tetramer. The cyclic polymers can be designed for experimental verification. (v)We also build a connection between line shape and population transfer dynamics. In the fast modulation limit, both the line shape and the population relaxation, for both correlated and uncorrelated bath, show similar behavior. However, in slow modulation limit, they show profoundly different behavior. (vi) This study explains the unique role of the rate of fluctuation (inverse of the bath correlation time) in the sustenance and propagation of coherence. We also examine the effects of off-diagonal fluctuation in spectral line shape. Finally, we use Tanimura-Kubo formalism to derive a set of coupled equations to include temperature effects (partly neglected in the SLE employed here) and effects of vibrational mode in energy transfer dynamics. [ABSTRACT FROM AUTHOR]

We study kill-and-restart and preemptive strategies for the fundamental scheduling problem of minimizing the sum of weighted completion times on a single machine in the non-clairvoyant setting. First, we show a lower bound of 3 for any deterministic non-clairvoyant kill-and-restart strategy. Then, we give for any b>1\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$b > 1$$\end{document} a tight analysis for the natural b-scaling kill-and-restart strategy as well as for a randomized variant of it. In particular, we show a competitive ratio of (1+33)≈6.197\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$(1+3\sqrt{3})\approx 6.197$$\end{document} for the deterministic and of ≈3.032\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$\approx 3.032$$\end{document} for the randomized strategy, by making use of the largest eigenvalue of a Toeplitz matrix. In addition, we show that the preemptive Weighted Shortest Elapsed Time First (WSETF) rule is 2-competitive when jobs are released online, matching the lower bound for the unit weight case with trivial release dates for any non-clairvoyant algorithm. Using this result as well as the competitiveness of round-robin for multiple machines, we prove performance guarantees smaller than 10 for adaptions of the b-scaling strategy to online release dates and unweighted jobs on identical parallel machines. [ABSTRACT FROM AUTHOR]

In this paper, a novel algorithm is proposed for reducing a banded symmetric generalized eigenvalue problem to a banded symmetric standard eigenvalue problem, based on the sequentially semiseparable (SSS) matrix techniques. It is the first time that the SSS matrix techniques are used in such eigenvalue problems. The newly proposed algorithm only requires linear storage cost and O (n 2) computation cost for matrices with dimension n, and is also potentially good for parallelism. Some experiments have been performed by using Matlab, and the accuracy and stability of algorithm are verified. [ABSTRACT FROM AUTHOR]

In Barrera M, Grudsky SM. Asymptotics of eigenvalues for pentadiagonal symmetric Toeplitz matrices. In: Large truncated Toeplitz matrices, toeplitz operators, and related topics. Operator theory: advances and applications Vol. 259, Birkhäuser, Cham.; 2017; p. 51–77. we have considered the problem about asymptotic formulas for all eigenvalues of T n (a) , as n goes to infinity, assuming that a is a specific model symbol with a unique zero of order 4. In this paper, we continue our investigation and we explore the case where a is a more general real-valued rational symbol with a unique zero of order 4. It should be noted that we apply a different method than the one used in Barrera M, Grudsky SM. Asymptotics of eigenvalues for pentadiagonal symmetric Toeplitz matrices. In: Large truncated Toeplitz matrices, Toeplitz operators, and related topics. Operator theory: advances and applications Vol. 259, Birkhäuser, Cham.; 2017; p. 51–77. This method coming from works Bogoya JM, Böttcher A, Grudsky SM, et al. Eigenvalues of Hermitian Toeplitz matrices with smooth simple-loop symbols. J Math Anal Appl. 2015;422(2):1308–1334 and Bogoya JM, Böttcher A, Grudsky SM, et al. Eigenvalues of Hermitian Toeplitz matrices generated by simple-loop symbols with relaxed smoothness. In: Large truncated Toeplitz matrices, Toeplitz operators, and related topics. Operator theory: advances and applications Vol. 259, Birkhäuser, Cham.; 2017. p. 179–212, where it is considered the class of all symbols having zeros of second order and one can reduce the problem to asymptotic analysis of a nonlinear equation. As well, we construct uniform asymptotic expansions for all eigenvalues, which allow us to precise the classical results of Widom and Parter for first and very last eigenvalues. [ABSTRACT FROM AUTHOR]

We present a circulant and skew-circulant splitting (CSCS) iterative method for solving large sparse continuous Sylvester equations A X + X B = C , where the coefficient matrices A and B are Toeplitz matrices. A theoretical study shows that if the circulant and skew-circulant splitting factors of A and B are positive semi-definite (not necessarily Hermitian), and at least one factor is positive definite, then the CSCS method converges to the unique solution of the Sylvester equation. In addition, our analysis gives an upper bound for the convergence factor of the CSCS iteration which depends only on the eigenvalues of the circulant and skew-circulant splitting matrices. A computational comparison with alternative methods reveals the efficiency and reliability of the proposed method. [ABSTRACT FROM AUTHOR]

We generalize the nested off-diagonal Bethe ansatz method to study the quantum chain associated with the twisted D 3 2 algebra (or the D 3 2 model) with either periodic or integrable open boundary conditions. We obtain the intrinsic operator product identities among the fused transfer matrices and find a way to close the recursive fusion relations, which makes it possible to determinate eigenvalues of transfer matrices with an arbitrary anisotropic parameter η. Based on them, and the asymptotic behaviors and values at certain points, we construct eigenvalues of transfer matrices in terms of homogeneous T − Q relations for the periodic case and inhomogeneous ones for the open case with some off-diagonal boundary reflections. The associated Bethe ansatz equations are also given. The method and results in this paper can be generalized to the D n + 1 2 model and other high rank integrable models. [ABSTRACT FROM AUTHOR]

It is known that the generating function f of a sequence of Toeplitz matrices {Tn(f)}n may not describe the asymptotic distribution of the eigenvalues of Tn(f) if f is not real. In this paper, we assume as a working hypothesis that, if the eigenvalues of Tn(f) are real for all n, then they admit an asymptotic expansion of the same type as considered in previous works, where the first function, called the eigenvalue symbol f , appearing in this expansion is real and describes the asymptotic distribution of the eigenvalues of Tn(f). This eigenvalue symbol f is in general not known in closed form. After validating this working hypothesis through a number of numerical experiments, we propose a matrix-less algorithm in order to approximate the eigenvalue distribution function f . The proposed algorithm, which opposed to previous versions, does not need any information about neither f nor f is tested on a wide range of numerical examples; in some cases, we are even able to find the analytical expression of f . Future research directions are outlined at the end of the paper. [ABSTRACT FROM AUTHOR]

We investigate distribution of eigenvalues of growing size Toeplitz matrices [ a n + k − j ] 1 ≤ j , k ≤ n as n → ∞ , when the entries { a j } are "smooth" in the sense, for example, that for some α > 0 , a j − 1 a j + 1 a j 2 = 1 − 1 α j (1 + o (1)) , j → ∞. Typically they are Maclaurin series coefficients of an entire function. We establish that when suitably scaled, the eigenvalue counting measures have limiting support on [ 0 , 1 ] , and under mild additional smoothness conditions, the universal scaled and weighted limit distribution is | π log ⁡ t | − 1 / 2 d t on [ 0 , 1 ]. [ABSTRACT FROM AUTHOR]

We consider boundary conditions of self-adjoint banded Toeplitz matrices. We ask if boundary conditions exist for banded self-adjoint Toeplitz matrices which satisfy operator inequalities of Dirichlet-Neumann bracketing type. For a special class of banded Toeplitz matrices including integer powers of the discrete Laplacian we find such boundary conditions. Moreover, for this class we give a lower bound on the spectral gap above the lowest eigenvalue. [ABSTRACT FROM AUTHOR]

Two of the most famous definitions of fractional derivatives are the Riemann-Liouville and the Caputo ones. In principle, these formulations are not equivalent and ask for different levels of regularity of the considered function. By focusing on a B-spline collocation discretization of both kind of derivatives, we show that when the fractional order α ranges in (1, 2) their difference in terms of matrices corresponds to a rank-1 correction whose spectral norm increases with the mesh-size n and is o( n $\begin{array}{} \displaystyle \sqrt{n} \end{array}$). On one hand, this implies that the spectral distribution for the B-spline collocation matrices corresponding to the Riemann-Liouville and Caputo derivatives coincide; on the other hand, the presence of the rank-1 correction makes the Caputo matrices worse conditioned for α tending to 1 due to a larger maximum singular value. Some linear algebra consequences of all this knowledge are discussed, and a selection of numerical experiments that validate our findings is provided. [ABSTRACT FROM AUTHOR]

A previous paper studied the so-called borderline curves of the Kac–Murdock–Szegő matrix K n (ρ) = [ ρ | j − k | ] j , k = 1 n , where ρ ∈ C. These are the level curves (contour lines) in the complex- ρ plane on which K n (ρ) has a type-1 or type-2 eigenvalue of modulus n , where n is the matrix dimension. Those curves have cusps at all critical points ρ = ρ c at which multiple (double) eigenvalues occur. The present paper determines corresponding curves pertaining to eigenvalues of modulus ν ≠ n. We find that these curves no longer present cusps; and that, when ν < n , the cusps have in a sense transformed into loops. We discuss the meaning of the winding numbers of our curves. Finally, we point out possible extensions to more general matrices. [ABSTRACT FROM AUTHOR]

Based on the spectral divide‐and‐conquer algorithm by Nakatsukasa and Higham [SIAM J. Sci. Comput., 35(3):A1325–A1349, 2013], we propose a new algorithm for computing all the eigenvalues and eigenvectors of a symmetric banded matrix with small bandwidth, with the eigenvectors given implicitly as a product of orthonormal matrices stored in the so‐called hierarchically off‐diagonal low‐rank (HODLR) format. For this purpose, we combine our previous work on the fast computation of spectral projectors in the HODLR format, with a novel technique for extracting a basis for the range of such a HODLR matrix. Preliminary numerical experiments demonstrate that our algorithm exhibits quasi‐linear complexity for matrices that can be efficiently represented in the HODLR format throughout the divide‐and‐conquer algorithm, and allows for conveniently dealing with such large‐scale matrices. [ABSTRACT FROM AUTHOR]

In this work, we perform a spectral analysis of flipped multilevel Toeplitz sequences, i.e., we study the asymptotic spectral behavior of {YnTn (f)} n, where Tn (f) is a real, square multilevel Toeplitz matrix generated by a function f ∈ L¹([-π, π]d) and Yn is the exchange matrix, which has 1's on the main antidiagonal. In line with what we have shown for unilevel flipped Toeplitz matrix sequences, the asymptotic spectrum is determined by a 2 x 2 matrix-valued function whose eigenvalues are ±|f|. Furthermore, we characterize the eigenvalue distribution of certain preconditioned flipped multilevel Toeplitz sequences with an analysis that covers both multilevel Toeplitz and circulant preconditioners. Finally, all our findings are illustrated by several numerical experiments. [ABSTRACT FROM AUTHOR]

The discretizations of the left and the right fractional derivatives based on the shifted finite-difference formulas of the Grünwald-Letnikov type can result in Toeplitz matrices T and T ⁎. Combining with the generating function of Toeplitz matrix T , we analyse the dominant property of the Hermitian part of T relative to its skew-Hermitian part. Then we construct a dominant Hermitian splitting iteration method for solving the discrete linear system of the considered space-fractional diffusion equations, and design a more practical dominant Hermitian-circulant splitting preconditioner to accelerate the convergence rates of the Krylov subspace iteration methods. Theoretical analyses demonstrate that all eigenvalues of the corresponding preconditioned matrix are clustered in a complex disk centered at 1 with the radius much less than 1, especially when the order β of the fractional derivative is close to 2. In addition, the numerical results show that the constructed preconditioner can effectively solve the discrete linear systems of one-dimensional and two-dimensional space-fractional diffusion equations. [ABSTRACT FROM AUTHOR]

Under appropriate technical assumptions, the simple-loop theory allows to derive various types of asymptotic expansions for the eigenvalues of Toeplitz matrices T n (f) generated by a function f. Unfortunately, such a theory is not available in the preconditioning setting, that is for matrices of the form T n − 1 (g) T n (ℓ) with g , ℓ real-valued, g nonnnegative and not identically zero almost everywhere. Independently and under the milder hypothesis that f = ℓ / g is even and monotonic over [ 0 , π ] , matrix-less algorithms have been developed for the fast eigenvalue computation of large preconditioned matrices of the type above, within a linear complexity in the matrix order: behind the high efficiency of such algorithms there are the expansions as in the case g ≡ 1 , combined with the extrapolation idea, and hence we conjecture that the simple-loop theory has to be extended in such a new setting, as the numerics strongly suggest. Here we focus our attention on a change of variable, followed by the asymptotic expansion of the new variable, and we consider new matrix-less algorithms ad hoc for the current case. Numerical experiments show a much higher accuracy till machine precision and the same linear computational cost, when compared with the matrix-less procedures already proposed in the literature. [ABSTRACT FROM AUTHOR]

We study the symmetry resolved entanglement entropies in one-dimensional systems with boundaries. We provide some general results for conformal invariant theories and then move to a semi-infinite chain of free fermions. We consider both an interval starting from the boundary and away from it. We derive exact formulas for the charged and symmetry resolved entropies based on theorems and conjectures about the spectra of Toeplitz+Hankel matrices. En route to characterise the interval away from the boundary, we prove a general relation between the eigenvalues of Toeplitz+Hankel matrices and block Toeplitz ones. An important aspect is that the saddle-point approximation from charged to symmetry resolved entropies introduces algebraic corrections to the scaling that are much more severe than in systems without boundaries. [ABSTRACT FROM AUTHOR]

The singular value distribution of the matrix‐sequence {YnTn[f]}n, with Tn[f] generated by f∈L1([−π,π]), was shown in [J. Pestana and A.J. Wathen, SIAM J Matrix Anal Appl. 2015;36(1):273‐288]. The results on the spectral distribution of {YnTn[f]}n were obtained independently in [M. Mazza and J. Pestana, BIT, 59(2):463‐482, 2019] and [P. Ferrari, I. Furci, S. Hon, M.A. Mursaleen, and S. Serra‐Capizzano, SIAM J. Matrix Anal. Appl., 40(3):1066‐1086, 2019]. In the latter reference, the authors prove that {YnTn[f]}n is distributed in the eigenvalue sense as ϕ|f|(θ)=|f(θ)|,θ∈[0,2π],−|f(−θ)|,θ∈[−2π,0),under the assumptions that f belongs to L1([−π,π]) and has real Fourier coefficients. The purpose of this paper is to extend the latter result to matrix‐sequences of the form {h(Tn[f])}n, where h is an analytic function. In particular, we provide the singular value distribution of the sequence {h(Tn[f])}n, the eigenvalue distribution of the sequence {Ynh(Tn[f])}n, and the conditions on f and h for these distributions to hold. Finally, the implications of our findings are discussed, in terms of preconditioning and of fast solution methods for the related linear systems. [ABSTRACT FROM AUTHOR]

We study the spectra of general N × N Toeplitz matrices given by symbols in the Wiener Algebra perturbed by small complex Gaussian random matrices, in the regime N ≫ 1 . We prove an asymptotic formula for the number of eigenvalues of the perturbed matrix in smooth domains. We show that these eigenvalues follow a Weyl law with probability sub-exponentially close to 1, as N ≫ 1 , in particular that most eigenvalues of the perturbed Toeplitz matrix are close to the curve in the complex plane given by the symbol of the unperturbed Toeplitz matrix. [ABSTRACT FROM AUTHOR]

For complex ρ , the spectral properties of the Toeplitz matrix K n (ρ) = [ ρ | j − k | ] j , k = 1 n , often called the Kac–Murdock–Szegő matrix, have been examined in detail in two recent papers. The second paper, in particular, introduced the concept of borderline curves. These are two closed curves in the complex- ρ plane that consist of all the ρ for which K n (ρ) possesses some eigenvalue whose magnitude equals the matrix dimension n. The purpose of the present paper is to examine eigenvalue bifurcations in both a qualitative and a quantitative manner, and to discuss connections between bifurcations and the borderline curves. [ABSTRACT FROM AUTHOR]

The asymptotic spectral properties of matrices of grid operators on polygonal domains in the plane are studied in the case of refining triangular grids. Methods available for analyzing spectral distributions are largely based on tool of the theory of generalized locally Toeplitz sequences (GLT theory). In this paper, we show that the matrices of grid operators on nonrectangular domains do not form GLT sequences. A method for calculating spectral distributions in such cases is proposed. Generalizations of GLT sequences are introduced, and preconditioner based on them are proposed. [ABSTRACT FROM AUTHOR]

The problem of finding the distance from a given n×n matrix polynomial of degree k to the set of matrix polynomials having the elementary divisor (λ-λ0)j,j⩾r, for a fixed scalar λ0 and 2⩽r⩽kn is considered. It is established that polynomials that are not regular are arbitrarily close to a regular matrix polynomial with the desired elementary divisor. For regular matrix polynomials the problem is shown to be equivalent to finding minimal structure preserving perturbations such that a certain block Toeplitz matrix becomes suitably rank deficient. This is then used to characterize the distance via two different optimizations. The first one shows that if λ0 is not already an eigenvalue of the matrix polynomial, then the problem is equivalent to computing a generalized notion of a structured singular value. The distance is computed via algorithms like BFGS and Matlab's globalsearch algorithm from the second optimization. Upper and lower bounds of the distance are also derived and numerical experiments are performed to compare them with the computed values of the distance. [ABSTRACT FROM AUTHOR]

In this paper, for a class of perturbed Toeplitz periodic tridiagonal (PTPT) matrices, some properties, including the determinant, the inverse matrix, the eigenvalues and the eigenvectors, are studied in detail. Specifically, the determinant of the PTPT matrix can be explicitly expressed using the well-known Fibonacci numbers; the inverse of the PTPT matrix can also be explicitly expressed using the Lucas number and only four elements in the PTPT matrix. Eigenvalues and eigenvectors can be obtained under certain conditions. In addition, some algorithms are presented based on these theoretical results. Comparison of our new algorithms and some recent works is given. Numerical results confirm our new theoretical results and show that the new algorithms not only can obtain accurate results but also have much better computing efficiency than some existing algorithms studied recently. [ABSTRACT FROM AUTHOR]

In this paper, a 2n-by-2n circulant preconditioner is introduced for a system of linear equations arising from discretization of the spatial fractional diffusion equations (FDEs). We show that the eigenvalues of our preconditioned system are clustered around 1, even if the diffusion coefficients of FDEs are not constants. Numerical experiments are presented to demonstrate that the preconditioning technique is very efficient. [ABSTRACT FROM AUTHOR]

In this paper, we derive an orthogonal block diagonalization and a number of formulas for pentadiagonal block band symmetric Toeplitz matrices and anti-pentadiagonal block band persymmetric Hankel matrices, both with perturbed corners. Namely, our formulas include block diagonalization, inverse, eigenvalues of these matrices. Our approach uses a suitable modification technique for pentadiagonal block band symmetric Toeplitz matrices and anti-pentadiagonal block band persymmetric Hankel matrices. Some numerical experiments are also presented to demonstrate the performance and effectiveness of the proposed theorems. [ABSTRACT FROM AUTHOR]

In this paper we consider sparse symmetrically banded matrices in which the nonzero off-diagonals are positioned a multiple of k steps from the main diagonal. We show that such a matrix T is permutationally similar to direct sum of banded matrices. In particular, when T has exactly one nonzero off-diagonal above and below the main diagonal, the direct summands are tridiagonal. If T has a w -Toeplitz structure, the blocks are w ′ -Toeplitz, with w ′ = lcm (w , k) / k. This reduction allows the study of spectral properties of T from those of the direct summands. Finally, we give a reduction of sparse symmetrically banded matrices relatively to the main antidiagonal. [ABSTRACT FROM AUTHOR]