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

Question

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

Answer 1

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

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