图的特征值求解器

Question

假设我有一个图形，包含10万个节点和100万个边。我想计算此图的邻接矩阵上的最大特征值。这个特征值求解器应该为这个图表工作得多。请注意矩阵是稀疏的。

Answer 1

您可以使用Arpack [1]，它只需要一个计算矩阵向量乘积的函数（因此它对于稀疏矩阵非常有效）。

Arpack具有不同的操作模式，用于计算高频（小特征值）或低频（大特征值）。不幸的是，对于高频来说，它的运行速度通常要快得多，但您可以使用稀疏LU分解算法（例如SuperLU [2]）对矩阵进行预分解，然后计算M^-1的高频率求解线性系统而不是计算稀疏矩阵向量积，那么特征值就是Arpack计算出的特征值的倒数。

我试过用十亿分之一百万个节点的网格，它工作得很好。细节是在我的文章[3]和伴随源代码[4]

参考文献：

[1] http://www.caam.rice.edu/software/ARPACK/

[2] http://crd-legacy.lbl.gov/~xiaoye/SuperLU/

[3] http://alice.loria.fr/index.php/publications.html?redirect=0&Paper=ManifoldHarmonics@2007

[4] http://alice.loria.fr/WIKI/index.php/Graphite/ManifoldHarmonics