Jaki jest najszybszy sposób obliczenia wszystkich wartości własnych bardzo dużej i rzadkiej macierzy przylegania w pythonie?

Próbuję dowiedzieć się, czy istnieje szybszy sposób obliczenia wszystkich wartości własnych i wektorów własnych bardzo dużej i rzadkiej macierzy przylegania niż przy użyciu scipy.sparse.linalg.eigsh O ile mi wiadomo, metody te wykorzystują tylko rzadkość i atrybuty symetrii macierzy. Macierz przylegania jest również binarna, co sprawia, że myślę, że istnieje szybszy sposób, aby to zrobić.

Utworzyłem losową macierz rzadkiej przylegalności 1000 x 1000 i porównałem kilka metod na moim laptopie z Ubuntu 13.04 x230:

scipy.sparse.linalg.eigs: 0,65 sekundy
scipy.sparse.linalg.eigsh: 0,44 sekundy
scipy.linalg.eig: 6,09 sekund
scipy.linalg.eigh: 1,60 sekundy

W przypadku rzadkich eigsh i eigsh ustawiam k, liczbę pożądanych wartości własnych i wektorów własnych, jako rangę macierzy.

Problem zaczyna się od większych matryc - na matrycy 9000 x 9000 zajęło scipy.sparse.linalg.eigsh 45 minut!

linear-algebra python performance eigensystem scipy Noam Peled
źródło

NB scipy.sparse.linalg.eigsh jest ARPACK

pv.

W dalszej kolejności, im większa macierz, tym mniej prawdopodobne jest dokładne obliczenie wewnętrznych wartości własnych (to znaczy ani największych, ani najmniejszych wartości własnych). Jakich informacji potrzebujesz z matrycy, którą rozkładasz?

Geoff Oxberry

To pytanie zostało zamieszczone tutaj . Mam zamiar zalecić zamknięcie opublikowanej wersji.

Aron Ahmadia

Chcę obliczyć A ^ k. Po przemyśleniu wydaje mi się, że przy takiej macierzy obliczenie bezpośredniego mnożenia (A A A ...) jest znacznie szybsze niż użycie składni eigend. Oczywiście zależy to od k.

Noam Peled

Tak, zrób to bezpośrednio. Wyniki składu eigend nie są rzadkie, więc będziesz mieć problemy z pamięcią (z drugiej strony A ^ k, jeśli k jest wystarczająco duży). Powiązane stackoverflow.com/a/9495457/424631

dranxo

Odpowiedzi:

FILTLAN to biblioteka C ++ do obliczania wewnętrznych wartości własnych rzadkich macierzy symetrycznych. Fakt, że jest to cały pakiet poświęcony właśnie temu, powinien powiedzieć, że jest to dość trudny problem. Znalezienie największej lub najmniejszej wartości własnej macierzy symetrycznej można wykonać poprzez przesunięcie / odwrócenie i użycie algorytmu Lanczosa, ale środek widma to inna sprawa. Jeśli chcesz tego użyć, możesz użyć SWIG do wywołania programu C ++ z Pythona.

Jeśli twoim ostatecznym celem jest obliczenie dużych mocy macierzy, możesz po prostu obliczyć wektory własne odpowiadające największym wartościom własnym, wiedząc, że mniejsze tryby będą mniej ważne, gdy weźmiesz duże moce.

$k$

Wybacz mi, jeśli są one dla ciebie oczywiste: możesz wykorzystać binarny charakter macierzy, mówiąc numpy, że składa się ona z liczb całkowitych zamiast liczb zmiennoprzecinkowych, powiedzmy, używając

a = np.zeros(100,dtype=np.uint)

$A^{16}$ $A^2$ $A^4$ $A^8$ $\approx\log_2 k$ $k$

Możesz także zbadać wywołanie równoległej rzadkiej biblioteki algebry liniowej, takiej jak CUSP lub cuSPARSE z Pythona, jeśli zależy Ci na prędkości i masz kartę graficzną NVIDIA.

Daniel Shapero
źródło

Chciałbym skomentować odpowiedź Daniela Shapero, ale nie mam wystarczającej reputacji SE.

Przyjęta odpowiedź bardzo mnie dezorientuje. Myślę, że tryb shift-invert można łatwo wykorzystać do obliczenia wewnętrznych wartości własnych. Zobacz: https://docs.scipy.org/doc/scipy/reference/tutorial/arpack.html

Aby odpowiedzieć na pierwotne pytanie: rzadko zdarza się, że potrzebne są wszystkie wartości własne dużej rzadkiej macierzy. Zwykle potrzebujesz ekstremów lub jakiegoś skupiska wartości wewnętrznych. W takim przypadku matryca hermitowska eigshjest szybsza. Dla nie-Hermitianów będziesz musiał iść z eigs. I są znacznie szybsze niż numpy eiglub eigh.

Alex
źródło