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

Question

直到现在，我使用numpy.linalg.eigvals来计算至少有1000行/列的二次矩阵的特征值，并且对于大多数情况，其约五分之一的条目为非零（我不知道是否应将其视为稀疏矩阵）。我找到了另一个topic，表明scipy可能可以做得更好。

然而，由于我必须计算成千上万个逐渐增加大小的大型矩阵的特征值（可能高达20000行/列，是的，我需要它们的所有特征值），这将始终需要非常长的时间。如果我能加快速度，即使只是微小的一点，这很可能是值得努力的。

因此，我的问题是：在不限制自己使用Python的情况下，是否有更快的方法来计算特征值？

- alice

---

如果Python不是必须的话，那么任何其他低级语言（如C++ /甚至C#）都可以提高速度。只需要适当的实现即可。 - ZorleQ

无论你做什么，要记住很多numpy都是Python友好的包装器，它包装了用C、Fortran、汇编语言等编写的功能。从文档中我看到numpy.linalg.eigvals是LINPACK库中函数的包装器。这并不意味着你找不到更快的求解器，但你可能需要超越numpy、scipy和LAPACK去寻找它们。 - High Performance Mark

你使用迭代方法吗？如果是的话，也许你可以并行化它们？ - Darek

Answer 1

@HighPerformanceMark在评论中是正确的，numpy背后的算法（LAPACK等）是一些最好的数值算法，但也许不是对于完整矩阵对角化而言最先进的。然而，如果你有以下内容，你可以 显著 加速：

稀疏矩阵

如果您的矩阵是稀疏的，即填充条目的数量为k，满足 k<<N**2 ，那么您应该查看scipy.sparse.

带状矩阵

有许多算法适用于处理特定类型的矩阵带状结构。请查看scipy.linalg.solve.banded中的求解器。

最大特征值

大多数时候，您实际上并不需要所有的特征值。事实上，大部分物理信息来自最大的特征值，其余的只是短暂的高频振荡。在这种情况下，您应该研究快速收敛于最大特征值/向量的特征值解法，例如Lanczos算法。

- Hooked

---

OP明确表示他们需要所有的特征值，并且矩阵大约有80%的稀疏度。我不知道80%的稀疏度是否足够使稀疏特征值算法胜过密集算法，但值得一试。 - Danica

@Dougal 我知道他认为他需要所有的特征值，但我已经学到了通常只用最大的特征值就可以得到很好的近似（显而易见的原因！）。Lancozs算法最终会收敛到越来越小的特征值，这些信息肯定比没有特征值要好得多！ - Hooked

是的，抱歉，我太快地阅读了你回答的那一部分，并假设你没有真正阅读问题 - 抱歉。 :) 但是一个小提示：用户名“alice”和代词“he”通常不搭配。最好坚持使用性别中立的单数they。 - Danica

@Dougal 我有什么权利在用户名上强加性别？但我认为，在 Stack Exchange 的所有请求中，OP 是适当的代词。也许这是一个适合在 http://english.stackexchange.com 上发问的好问题？ - Hooked

Answer 2

一种简单的方法，可以在不改变代码的情况下（特别是在多核机器上），通过将numpy链接到更快的线性代数库，例如MKL、ACML或OpenBLAS，来获得较好的加速效果。如果您与学术机构有关联，则出色的Anaconda Python发行版将让您轻松免费链接到MKL；否则，您可以花费$30美元（在这种情况下，您应该先尝试优化的30天试用版）或自己动手（这是一个略微烦人但绝对可行的过程）。

我也会尝试稀疏特征值求解器。

- Danica