计算大矩阵特征值的最快方法

Question

到目前为止，我使用numpy.linalg.eigvals计算至少有1000行/列的二次矩阵的特征值，在大多数情况下，大约五分之一的项是非零的（我不知道这是否应该被视为稀疏矩阵）。我发现另一个topic表明scipy可能做得更好。

然而，由于我必须计算数十万个增大的大型矩阵的特征值（可能高达20000行/列，是的，我需要它们的所有特征值），这总是需要非常长的时间。如果我能加快速度，哪怕是最微小的一点，也很可能是值得的。

所以我的问题是：在不局限于python的情况下，有没有一种更快的方法来计算特征值？

Answer 1

一个简单的方法是将numpy链接到一个更快的线性代数库，比如MKL、ACML或OpenBLAS，这样可以在不改变代码的情况下（特别是在多核机器上）获得一个不错的加速。如果你与一个学术机构有联系，优秀的Anacondapython发行版将让你轻松免费链接到MKL；否则，你可以花30美元（在这种情况下，你应该先尝试30天的优化试用）或do it yourself（一个稍微烦人的过程，但绝对可行）。

不过，我肯定也会尝试稀疏特征值求解器。

Answer 2

@HighPerformanceMark在评论中是正确的，因为numpy背后的算法（LAPACK等）是对角化全矩阵的一些最好的，但可能不是最先进的数值算法。但是，如果你有以下条件，你可以大大加快速度：

稀疏矩阵

如果矩阵是稀疏的，即填充的条目数是k，那么应该看看k<<N**2。

带状矩阵

有许多算法用于处理特定banded structure的矩阵。 查看^{}中的解算器。

最大特征值

大多数时候，你并不需要所有的特征值。事实上，大多数物理信息来自最大的特征值，而其余的仅仅是短暂的高频振荡。在这种情况下，您应该研究快速收敛到最大特征值/向量（如Lanczos algorithm）的特征值解。