我刚刚看到这篇论文，其中详细介绍了一种快速获取三对角对称矩阵特征值的方法的实现：
Coakley, Ed S.；Rokhlin, Vladimir, 一种用于计算实对称三对角矩阵谱的快速分治算法
这种方法依赖于分治算法，并且能够以复杂度计算特征值，而传统方法，例如 LAPACK 中的方法具有复杂度。
我很惊讶这还没有成为参考。该算法的细节在论文中提供，但看起来相当乏味。你知道这个方法是否已经在包或第三方库中实现了吗？
实施一个O ( n对数( n ) )O(nlog(n))计算实对称三对角矩阵特征值的方法
计算科学
线性代数
特征值
复杂
2021-12-03 22:06:59
1个回答
我认为该方法的实现复杂性太高，适用性太窄，不值得。
尽管该论文正确地指出了在解决一般对称特征问题的过程中解决三对角对称特征问题的重要性，但它忽略了这两个场景之间的“前端”过程（Householder tridiagonalization）已经需要次失败。无论您如何解决内部三对角问题，这将主导一般对称问题的整体复杂性。
在针对大型稀疏/结构化特征问题的 Lanczos 算法的上下文中也存在类似的困难。尽管它们投影到三对角系统，但这些实例的大小比原始稀疏系统小得多。因此，与 Lanczos 迭代本身所产生的“全尺寸”matvecs 和向量运算的成本相比，解决三对角特征问题仍然不会增加总成本。
三对角特征问题本身并不经常发生，而是通常在其他（更昂贵的）预处理之前发生。所以看起来快速算法可能不值得在这里付出努力。