Mam dwa wykresy z prawie n ~ 100000 węzłów każdy. Na obu wykresach każdy węzeł jest podłączony dokładnie do 3 innych węzłów, więc macierz przylegania jest symetryczna i bardzo rzadka.
Najtrudniejsze jest to, że potrzebuję wszystkich wartości własnych macierzy przylegania, ale nie wektorów własnych. Mówiąc dokładniej, będzie to raz w życiu (przynajmniej o ile mi wiadomo!), Więc chcę uzyskać wszystkie wartości własne i nie mam nic przeciwko czekaniu kilku dni na ich zdobycie.
Próbowałem scipy
owijać ARPACK
, ale to trwa zbyt długo. Znalazłem wiele bibliotek, ale działają one najlepiej w celu uzyskania podzbioru największych / najmniejszych wartości własnych. Czy jest jakaś biblioteka, która działa dla symetrycznych macierzy rzadkich z prawdopodobnie równoległą implementacją, aby uzyskać wszystkie wartości własne?
Odpowiedzi:
Można użyć transformacji widmowej z odwróconym przesunięciem [1] i obliczyć widmo pasmo po paśmie.
Technikę wyjaśniono również w moim artykule [2]. Oprócz implementacji w [1], implementacja jest dostępna w C ++ w moim oprogramowaniu Graphite [3] ( aktualizacja 17 stycznia : teraz wszystko jest przeniesione do geogramu / grafitu w wersji 3 ), którego użyłem do obliczenia funkcji własnych operatora Laplace'a dla zazębia się z 1 milionem wierzchołków (problem podobny do twojego).
Jak to działa:
[1] http://www.mcs.anl.gov/uploads/cels/papers/P1263.pdf
[2] http://alice.loria.fr/index.php/publications.html?redirect=0&Paper=ManifoldHarmonics@2008
[3] http://alice.loria.fr/software/graphite/doc/html/
źródło
Inną opcją byłoby użycie rotacji Jacobi. Ponieważ macierz jest już prawie ukośna, zebranie nie powinno zająć dużo czasu. Zasadniczo zbiega się w tempie liniowym, ale po wystarczającej liczbie iteracji współczynnik zbieżności staje się kwadratowy.
źródło