论文标题
快速toeplitz特征值计算，连接插值 - 拆卸矩阵算法和简单环理论
Fast Toeplitz eigenvalue computations, joining interpolation-extrapolation matrix-less algorithms and simple-loop theory
论文作者
论文摘要
在适当的技术假设下，简单循环理论允许针对由函数$ f $生成的Toeplitz矩阵的特征值推断出各种类型的渐近扩展。独立及其在一个温和的假设下，$ f $均匀，单调超过[0，π] $，已经为快速的特征值计算而开发了矩阵的算法，用于对矩阵顺序的线性复杂性的快速特征值计算：在矩阵顺序上的线性复杂性：在此类算法的高效率后面，这些算法的高效率与简单的理论相结合，这些算法由构成构成的构图进行了序级，这些算法是由序言组合而来的。 在这里，我们将注意力集中在变量的变化上，然后是新变量的渐近扩展，并将无基质算法调整为已考虑的新设置。 与相关文献中已经提出的无基质程序相比，数值实验显示出更高的精度（直至机器精度）和相同的线性计算成本。在这些优点中，我们简单地提及以下内容：a）当知道简单环函数的系数时，算法可以完美地计算它们； b）虽然所提出的算法更好或最坏的算法可与以前的计算内部特征值相当，但计算极端特征值的算法非常好。
Under appropriate technical assumptions, the simple-loop theory allows to deduce 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 monotonic 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 extremely better for the computation of the extreme eigenvalues.
