寻找大矩阵的 k-最小特征值及其对应的特征向量

Question

对于大小为 300,000*300,000 的对称稀疏方阵，在任何语言或程序包中，在一个小时左右的时间内找到 10 个最小特征值及其对应特征向量的最佳方法是什么。

Answer 1

在 Hermitian 矩阵上运行的 Lanczos 算法是一种找到最小和最大特征值以及相应特征向量的好方法。请注意，根据定义，实对称矩阵是 Hermitian 矩阵。 Lanczos 需要 O(N) 存储空间和大约 O(N) 时间来评估极端 eigenvalues/eigenvectors。这与需要 O(N^2) 存储空间和 O(N^3) 运行 时间的蛮力对角化形成对比。出于这个原因，Lanczos 算法使得以前在计算上不可行的许多问题的近似解成为可能。

Here is a useful link 到加州大学戴维斯分校网站，其中列出了 Lanczos 在许多 languages/packages 中的实现，包括 FORTRAN、C/C++ 和 MATLAB。