图的特征值求解器
Eigen Value Solver for Graph
假设我有一个包含 10 百万个节点和 100 百万个边的图。我想计算此图的邻接矩阵上的最大特征值。哪个特征值求解器应该适用于这么大的图。注意矩阵是稀疏的。
您可以使用 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
假设我有一个包含 10 百万个节点和 100 百万个边的图。我想计算此图的邻接矩阵上的最大特征值。哪个特征值求解器应该适用于这么大的图。注意矩阵是稀疏的。
您可以使用 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