圖的特徵值求解器

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