Sven-Erik Ekström

Let { Λ n = { λ 1 , n , … , λ d n , n } } n ${\left\{{{\Lambda}}_{n}=\left\{{\lambda }_{1,n},\dots ,{\lambda }_{{d}_{n},n}\right\}\right\}}_{n}$ be a sequence of finite multisets of real numbers such that d _n → ∞ as n → ∞, and let f : Ω ⊂ R d → R $f:{\Omega}\subset {\mathbb{R}}^{d}\to \mathbb{R}$ be a Lebesgue measurable function defined on a domain Ω with 0 < μ _d (Ω) < ∞, where μ _d is the Lebesgue measure in R d ${\mathbb{R}}^{d}$ . We say that { Λ n } n ${\left\{{{\Lambda}}_{n}\right\}}_{n}$ has an asymptotic distribution described by f , and we write { Λ n } n ∼ f ${\left\{{{\Lambda}}_{n}\right\}}_{n}\sim f$ , if (*) lim n → ∞ 1 d n ∑ i = 1 d n F ( λ i , n ) = 1 μ d ( Ω ) ∫ Ω F ( f ( x ) ) d x ${\mathrm{lim}}_{n\to \infty }\frac{1}{{d}_{n}}{\sum }_{i=1}^{{d}_{n}}F\left({\lambda }_{i,n}\right)=\frac{1}{{\mu }_{d}\left({\Omega}\right)}{\int }_{{\Omega}}F\left(f\left(\boldsymbol{x}\right)\right)\mathrm{d}\boldsymbol{x}$ for every continuous function F with bounded support. If Λ _n is the spectrum of a matrix A _n , we say that { A n } n ${\left\{{A}_{n}\right\}}_{n}$ has an asymptotic spectral distribution described by f and we write { A n } n ∼ λ f ${\left\{{A}_{n}\right\}}_{n}{ \sim }_{\lambda } f$ . In the case where d = 1, Ω is a bounded interval, Λ _n ⊆ f (Ω) for all n , and f satisfies suitable conditions, Bogoya, Böttcher, Grudsky, and Maximenko proved that the asymptotic distribution (*) implies the uniform convergence to 0 of the difference between the properly sorted vector [ λ 1 , n , … , λ d n , n ] $\left[{\lambda }_{1,n},\dots ,{\lambda }_{{d}_{n},n}\right]$ and the vector of samples [ f ( x 1 , n ) , … , f ( x d n , n ) ] $\left[f\left({x}_{1,n}\right),\dots ,f\left({x}_{{d}_{n},n}\right)\right]$ , i.e., (**) lim n → ∞ max i = 1 , … , d n | f ( x i , n ) − λ τ n ( i ) , n | = 0 , ${\mathrm{lim}}_{n\to \infty } {\mathrm{max}}_{i=1,\dots ,{d}_{n}}\vert f\left({x}_{i,n}\right)-{\lambda }_{{\tau }_{n}\left(i\right),n}\vert =0,$ where x 1 , n , … , x d n , n ${x}_{1,n},\dots ,{x}_{{d}_{n},n}$ is a uniform grid in Ω and τ _n is the sorting permutation. We extend this result to the case where d ⩾ 1 and Ω is a Peano–Jordan measurable set (i.e., a bounded set with μ _d (∂Ω) = 0). We also formulate and prove a uniform convergence result analogous to (**) in the more general case where the function f takes values in the space of k × k matrices. Our derivations are based on the concept of monotone rearrangement (quantile function) as well as on matrix analysis arguments stemming from the theory of generalized locally Toeplitz sequences and the observation that any finite multiset of numbers Λ n = { λ 1 , n , … , λ d n , n } ${{\Lambda}}_{n}=\left\{{\lambda }_{1,n},\dots ,{\lambda }_{{d}_{n},n}\right\}$ can always be interpreted as the spectrum of a matrix A n = diag ( λ 1 , n , … , λ d n , n ) ${A}_{n}=\mathrm{diag}\left({\lambda }_{1,n},\dots ,{\lambda }_{{d}_{n},n}\right)$ . The theoretical results are illustrated through numerical experiments, and a reinterpretation of them in terms of vague convergence of probability measures is hinted.

Sequences of structured matrices of increasing size, such as generalized locally Toeplitz sequences, arise in many scientific applications and especially in the numerical discretization of linear differential problems. We assume that the eigenvalues of a matrix $$X_n$$ X n , belonging to a sequence of such kind, are given by a regular expansion. Under this working hypothesis, we propose a method for computing approximations of the eigenvalues of $$X_n$$ X n for large n and we provide a theoretical analysis of its convergence. The method is called matrix-less because it does not operate on the matrix $$X_n$$ X n but on a few similar matrices of smaller size combined with an interpolation-extrapolation strategy. The working hypothesis and the performance of the proposed eigenvalue approximation method are benchmarked on several numerical examples, with a special attention to matrices arising from the discretization of variable-coefficient differential problems.

We study the spectral properties of flipped Toeplitz matrices of the form $H_n(f)=Y_nT_n(f)$, where $T_n(f)$ is the $n\times n$ Toeplitz matrix generated by the function $f$ and $Y_n$ is the $n\times n$ exchange (or flip) matrix having $1$ on the main anti-diagonal and $0$ elsewhere. In particular, under suitable assumptions on $f$, we establish an alternating sign relationship between the eigenvalues of $H_n(f)$, the eigenvalues of $T_n(f)$, and the quasi-uniform samples of $f$. Moreover, after fine-tuning a few known theorems on Toeplitz matrices, we use them to provide localization results for the eigenvalues of $H_n(f)$. Our study is motivated by the convergence analysis of the minimal residual (MINRES) method for the solution of real non-symmetric Toeplitz linear systems of the form $T_n(f)\mathbf x=\mathbf b$ after pre-multiplication of both sides by $Y_n$, as suggested by Pestana and Wathen.

Let $\{Λ_n=\{λ_{1,n},\ldots,λ_{d_n,n}\}\}_n$ be a sequence of finite multisets of real numbers such that $d_n\to\infty$ as $n\to\infty$, and let $f:Ω\subset\mathbb R^d\to\mathbb R$ be a Lebesgue measurable function defined on a domain $Ω$ with $0<μ_d(Ω)<\infty$, where $μ_d$ is the Lebesgue measure in $\mathbb R^d$. We say that $\{Λ_n\}_n$ has an asymptotic distribution described by $f$, and we write $\{Λ_n\}_n\sim f$, if \[ \lim_{n\to\infty}\frac1{d_n}\sum_{i=1}^{d_n}F(λ_{i,n})=\frac1{μ_d(Ω)}\int_ΩF(f({\boldsymbol x})){\rm d}{\boldsymbol x}\qquad\qquad(*) \] for every continuous function $F$ with bounded support. If $Λ_n$ is the spectrum of a matrix $A_n$, we say that $\{A_n\}_n$ has an asymptotic spectral distribution described by $f$ and we write $\{A_n\}_n\sim_λf$. In the case where $d=1$, $Ω$~is a bounded interval, $Λ_n\subseteq f(Ω)$ for all $n$, and $f$ satisfies suitable conditions, Bogoya, Böttcher, Grudsky, and Maximenko proved that the asymptotic distribution (*) implies the uniform convergence to $0$ of the difference between the properly sorted vector $[λ_{1,n},\ldots,λ_{d_n,n}]$ and the vector of samples $[f(x_{1,n}),\ldots,f(x_{d_n,n})]$, i.e., \[ \lim_{n\to\infty}\,\max_{i=1,\ldots,d_n}|f(x_{i,n})-λ_{τ_n(i),n}|=0, \qquad\qquad(**) \] where $x_{1,n},\ldots,x_{d_n,n}$ is a uniform grid in $Ω$ and $τ_n$ is the sorting permutation. We extend this result to the case where $d\ge1$ and $Ω$ is a Peano--Jordan measurable set (i.e., a bounded set with $μ_d(\partialΩ)=0$). See the rest of the abstract in the manuscript.

Consider the Toeplitz matrix $T_n(f)$ generated by the symbol $f(θ)=\hat{f}_r e^{\mathbf{i}rθ}+\hat{f}_0+\hat{f}_{-s} e^{-\mathbf{i}sθ}$, where $\hat{f}_r, \hat{f}_0, \hat{f}_{-s} \in \mathbb{C}$ and $0<r<n,~0<s<n$. For $r=s=1$ we have the classical tridiagonal Toeplitz matrices, for which the eigenvalues and eigenvectors are known. Similarly, the eigendecompositions are known for $1<r=s$, when the generated matrices are ``symmetrically sparse tridiagonal''. In the current paper we study the eigenvalues of $T_n(f)$ for $1\leq r<s$, which are ``non-symmetrically sparse tridiagonal''. We propose an algorithm which constructs one or two ad hoc matrices smaller than $T_n(f)$, whose eigenvalues are sufficient for determining the full spectrum of $T_n(f)$. The algorithm is explained through use of a conjecture for which examples and numerical experiments are reported for supporting it and for clarifying the presentation. Open problems are briefly discussed.

In a series of recent papers the spectral behavior of the matrix sequence $\{Y_nT_n(f)\}$ is studied in the sense of the spectral distribution, where $Y_n$ is the main antidiagonal (or flip matrix) and $T_n(f)$ is the Toeplitz matrix generated by the function $f$, with $f$ being Lebesgue integrable and with real Fourier coefficients. This kind of study is also motivated by computational purposes for the solution of the related large linear systems using the (preconditioned) MINRES algorithm. Here we complement the spectral study with more results holding both asymptotically and for a fixed dimension $n$, and with regard to eigenvalues, singular values, and eigenvectors of $T_n(f), Y_nT_n(f)$ and to several relationships among them: beside fast linear solvers, a further target is the design of ad hoc procedures for the computation of the related spectra via matrix-less algorithms, with a cost being linear in the number of computed eigenvalues. We emphasize that the challenge of the case of non-monotone generating functions is considered in the current work, for which the previous matrix-less algorithms fail. Numerical experiments are reported and commented, with the aim of showing in a visual way the theoretical analysis.