计算大型矩阵特征值的最快方法 [英] The fastest way to calculate eigenvalues of large matrices

问题描述

直到现在，我仍使用numpy.linalg.eigvals来计算至少具有1000行/列的二次矩阵的特征值，并且在大多数情况下，约有五分之一的条目为非零值(我不知道是否应该这样做)被视为稀疏矩阵).我发现了另一个 topic ，表明scipy可以可能做得更好.

Until now I used numpy.linalg.eigvals to calculate the eigenvalues of quadratic matrices with at least 1000 rows/columns and, for most cases, about a fifth of its entries non-zero (I don't know if that should be considered a sparse matrix). I found another topic indicating that scipy can possibly do a better job.

但是，由于我必须为成千上万个增大大小的大型矩阵(可能最多20000行/列，是的，我需要它们的所有特征值)计算特征值，所以这总是要花很长的时间.如果我能加快速度，即使是最微小的速度，也很值得付出努力.

However, since I have to calculate the eigenvalues for hundreds of thousands of large matrices of increasing size (possibly up to 20000 rows/columns and yes, I need ALL of their eigenvalues), this will always take awfully long. If I can speed things up, even just the tiniest bit, it would most likely be worth the effort.

所以我的问题是:当不限制自己使用python时，有没有一种更快的方法来计算特征值?

So my question is: Is there a faster way to calculate the eigenvalues when not restricting myself to python?

推荐答案

@HighPerformanceMark在注释中是正确的，因为numpy(LAPACK等)背后的算法是最好的，但也许不是最先进的，用于对角化完整矩阵的数值算法.但是，如果您具有以下条件，则可以大大加快速度:

@HighPerformanceMark is correct in the comments, in that the algorithms behind numpy (LAPACK and the like) are some of the best, but perhaps not state of the art, numerical algorithms out there for diagonalizing full matrices. However, you can substantially speed things up if you have:

如果矩阵是稀疏的，即填充的条目数为k，则k<<N**2则应查看

If your matrix is sparse, i.e. the number of filled entries is k, is such that k<<N**2 then you should look at scipy.sparse.

有许多算法可以处理特定带状结构的矩阵. 在 scipy.linalg.solve.banded 中查看求解器.

There are numerous algorithms for working with matrices of a specific banded structure. Check out the solvers in scipy.linalg.solve.banded.

在大多数情况下，您并不是真的需要所有特征值.实际上，大多数物理信息都来自最大的特征值，而其余的仅仅是高频振荡，只是瞬时的.在那种情况下，您应该研究能够快速收敛到最大特征值/向量的特征值解决方案，例如 Lanczos算法 a>.

Most of the time, you don't really need all of the eigenvalues. In fact, most of the physical information comes from the largest eigenvalues and the rest are simply high frequency oscillations that are only transient. In that case you should look into eigenvalue solutions that quickly converge to those largest eigenvalues/vectors such as the Lanczos algorithm.

这篇关于计算大型矩阵特征值的最快方法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！