Oblicz wszystkie wartości własne bardzo dużej i bardzo rzadkiej macierzy przylegania

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 scipyowijać 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?

— Mahdi
źródło

Z ciekawości, dlaczego dokładnie potrzebujesz wszystkich wartości własnych? Większość problemów tego rozmiaru jest przybliżeniem nawet większych (lub nawet nieskończonych wymiarów) problemów, więc wartości własne małych problemów są jedynie przybliżone do problemu, który naprawdę chcemy rozwiązać. Najczęściej jakość aproksymacji jest dobra tylko w przypadku najmniejszych lub największych wartości własnych, a wszystkie pozostałe są tylko słabo aproksymowane, a zatem nie mają większego znaczenia praktycznego.

— Wolfgang Bangerth,

powiązane pytanie i odpowiedź

— GoHokies,

@WolfgangBangerth: (Wybacz mi, jeśli są dla ciebie oczywiste) Problem pochodzi z fizyki materiałów. Jest to związane z dokładnym przybliżeniem wiązania materiałów w celu uzyskania struktury pasma, właściwości wibracyjnych i elektrycznych. Aby je uzyskać, potrzebuję pełnego spektrum wartości własnych. BTW, to nie jest nic nowego i sięga lat 70. i 80., ale ponieważ mój system jest amorficzny, musiałem mieć bardzo duży system, aby uzyskać dobre wyniki. Chociaż większość ludzi dba tylko o kryształy, co jest niezwykle łatwe w porównaniu do mojego przypadku.

— Mahdi

@Mahdi: Cóż, miałem na myśli to, że właściwości fizyczne są określone przez widmo jakiegoś operatora częściowej różniczki. Podejrzewam (ale oczywiście nie wiem, ponieważ nie opisujesz, skąd pochodzi problem), że duży problem wartości własnej macierzy jest jedynie przybliżeniem problemu PDE. W związku z tym wartości własne będą również jedynie przybliżeniami.

— Wolfgang Bangerth,

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:

$A$ $(V,\lambda)$ $A$ $(V, 1/\lambda)$ $A^{-1}$ $A$ $A^{-1}$ $A$ $LL^t$ $Ax=b$ $A - \sigma Id$ $\sigma$ $(A-\sigma Id)^{-1}$ $\sigma$

[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/

— BrunoLevy
źródło

Dzięki Bruno! Te wyglądają bardzo obiecująco, przyjrzę się im!

— Mahdi

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.

— Gil
źródło