图的特征值求解器

Question

假设我有一个具有10百万节点和100百万边的图。我想计算这个图的邻接矩阵上的最大特征值。哪个特征值的求解者应该为这么大的图工作。注意，矩阵是稀疏的。

Answer 1

您可以使用Arpack 1，它只需要一个计算矩阵向量乘积的函数(因此它对稀疏矩阵很好地工作)。

Arpack有不同的工作模式，用于计算高频(小特征值)或低频(大特征值)。不幸的是，对于高频，它的工作速度要快得多，但是你可以做的是使用稀疏的LU分解算法，例如SuperLU 2，对矩阵进行预分解，然后通过求解一个线性系统而不是计算稀疏矩阵向量乘积来计算M^-1的高频，然后特征值就是由Arpack计算出来的矩阵的逆。

我试着用1/10百万节点的网格，它运行得很好。详细信息见我的文章3和配套的源代码4。

参考文献：

1

2

3

4