The Complexity of the Matrix Eigenproblem (STOC '99, Proceedings of the 第三十一届 ACM symposium on the theory of computing, p. 507-516) 中的结果表明 Hermitian Toeplitz 案例中最著名的算法是，基于第 1.2 节。在本节中，本征问题分为三个阶段（第 1.2 节，文章第 3 页和第 4 页）：$\tilde{O}(n^{2})$

a) 将给定矩阵的特征问题简化为规范形式矩阵的特征问题（即，对于 Frobenius 矩阵，对于具有 Frobenius 对角块的块三角形或块对角矩阵或三对角矩阵）；作为这个阶段的副产品，原始输入矩阵附加操作中被输出或变得容易获得$c_A(x)$$A$$O(n)$

b) 将的零点，以及$A$$c_A(x)$

到规范形式的可用简化来计算近似特征值的特征空间。$A$

一般矩阵文章中所述的阶段 (a) 的算术复杂度的下限是，其中是矩阵-矩阵乘法的算术复杂度。我知道LU分解的算术复杂度相当于矩阵-矩阵乘法的算术复杂度，但我不知道对于单个线性求解是否如此。我不相信这是真的。由于是（即使对于 Toeplitz 矩阵，据我所知），计算特征值（阶段 (a) 和 (b)）必须是，基于文章的结果。$\Omega(M(n))$$M(n)$$M(n)$$\Omega(n^{2})$$\Omega(n^{2})$

为了获得算法，限制步骤是在时间内计算特征多项式。如何做到这一点，我不确定，但阶段 (a) 的输出不能成为限制步骤，因为 Frobenius、块 Frobenius 和三对角矩阵都可以用数据指定。我无法访问与界限一起引用的源，所以我只能推测限制步骤有一系列与基本矩阵运算相关的矩阵 - 矩阵乘法以减少给定矩阵到列出的规范形式之一，在这种情况下，“输出限制步骤”在中间计算中。$\tilde{O}(n)$$\tilde{O}(n)$$O(n)$$\Omega(n^{2})$

已知最快的算法是Ng 和 Trench（1997 年技术报告）提出时间串行计算特征值，并在时间并行计算特征值。$\tilde{O}(n^{2})$$\tilde{O}(n)$

我计算 Hermitian Toeplitz 矩阵特征值的第一个想法是使用快速$O(n \log n)$Toeplitz 矩阵的矩阵乘法与 Lanczos 算法一起得到三对角矩阵。这个过程的复杂性是$O(n^2 \log n)$，它甚至在数值上都不是稳健的。我依稀记得Marlis Hochbruck写过一篇关于与 Toeplitz 矩阵相关的前瞻算法的论文，但我认为这些是为了确保非 Hermitian Toeplitz 系统的鲁棒性，而不是为了降低复杂性。

我的结论是，已经证明存在一个数值稳健的$\tilde{O}(n^2)$计算 Hermitian Toeplitz 矩阵的所有特征值（和特征向量）的算法将是一件好事。我也想知道能够计算特征值有多大用处$\tilde{O}(n)$时间，如果计算相应的特征向量需要$O(n^2)$时间。