Jaki jest najszybszy sposób obliczenia największej wartości własnej ogólnej macierzy?

EDYCJA: Testuję, czy jakieś wartości własne mają wartość jednego lub więcej.

Muszę znaleźć największą absolutną wartość własną dużej, rzadkiej, niesymetrycznej macierzy.

Korzystam z eigen()funkcji R , która korzysta z algo QR z EISPACK lub LAPACK, aby znaleźć wszystkie wartości własne, a następnie używam, abs()aby uzyskać wartości bezwzględne. Jednak muszę to zrobić szybciej.

Próbowałem także użyć interfejsu ARPACK w igraphpakiecie R. Dało to jednak błąd jednej z moich matryc.

Ostateczne wdrożenie musi być dostępne od R.

Prawdopodobnie będzie wiele wartości własnych tej samej wielkości.

Masz jakieś sugestie?

EDYCJA: Dokładność musi być tylko 1e-11. A „typowy” matryca dotąd . Byłem w stanie dokonać na tym faktoryzacji QR. Jednak możliwe jest również posiadanie znacznie większych. Obecnie zaczynam czytać o algorytmie Arnoldiego. Rozumiem, że jest to związane z Lanczsos.$386\times 386$

EDYCJA 2: Jeśli mam wiele macierzy, które „ testuję ” i wiem, że istnieje duża podmacierz, która się nie zmienia. Czy można to zignorować / odrzucić?

Zależy to w dużej mierze od rozmiaru matrycy, w przypadku dużej skali również od tego, czy jest ona rzadka, oraz od dokładności, którą chcesz osiągnąć.

Jeśli matryca jest zbyt duża, aby pozwolić na pojedynczą faktoryzację, a potrzebujesz dużej dokładności, algorytm Lanczsos jest prawdopodobnie najszybszym sposobem. W przypadku niesymetrycznym potrzebny jest algorytm Arnoldiego, który jest liczbowo niestabilny, więc implementacja musi rozwiązać ten problem (jest nieco trudny do wyleczenia).

Jeśli nie dotyczy to twojego problemu, podaj bardziej szczegółowe informacje w swoim pytaniu. Następnie dodaj komentarz do tej odpowiedzi, a ja ją zaktualizuję.

Edycja: [To było dla starej wersji pytania, szukając największej wartości własnej.] Ponieważ twoja matryca jest mała i pozornie gęsta, zrobiłbym iterację Arnoldiego na B = (IA) ^ {- 1}, używając początkowej permutowane trójkątne rozkładanie na IA, aby uzyskać tanie mnożenie przez B. (Lub obliczyć wyraźną odwrotność, ale kosztuje to 3 razy więcej niż rozkład na czynniki). Chcesz sprawdzić, czy B ma ujemną wartość własną. Pracując z B zamiast A, ujemne wartości własne są znacznie lepiej oddzielone, więc jeśli istnieje, powinieneś szybko zbiegać się.

Ale jestem ciekawy, skąd bierze się twój problem. Macierze niesymetryczne zwykle mają złożone wartości własne, więc „największy” nie jest nawet dobrze zdefiniowany. Dlatego musisz dowiedzieć się więcej o swoim problemie, co może pomóc zasugerować, jak rozwiązać go jeszcze szybciej i / lub bardziej niezawodnie.

Edycja2: Trudno jest uzyskać z Arnoldi konkretny podzbiór zainteresowań. Aby niezawodnie uzyskać absolutnie największe wartości własne, należy wykonać iterację podprzestrzeni przy użyciu oryginalnej macierzy, z rozmiarem podprzestrzeni dopasowującym lub przekraczającym liczbę wartości własnych, które powinny być bliskie 1 lub większej. Na małych matrycach będzie to wolniejsze niż algorytm QR, ale na dużych matrycach będzie znacznie szybsze.

$\left|\lambda_{n-1}/\lambda_{n}\right|$

$\lambda_{n-1}$$\lambda_n$

Ostatnio przeprowadzono na ten temat kilka dobrych badań. Nowe podejścia wykorzystują „algorytmy losowe”, które wymagają tylko kilku odczytów macierzy, aby uzyskać dobrą dokładność przy największych wartościach własnych. Jest to w przeciwieństwie do iteracji mocy, które wymagają kilku multiplikacji macierz-wektor, aby osiągnąć wysoką dokładność.

Możesz przeczytać więcej o nowych badaniach tutaj:

http://math.berkeley.edu/~strain/273.F10/martinsson.tygert.rokhlin.randomized.decomposition.pdf

http://arxiv.org/abs/0909.4061

Ten kod zrobi to za Ciebie:

http://cims.nyu.edu/~tygert/software.html

https://bitbucket.org/rcompton/pca_hgdp/raw/be45a1d9a7077b60219f7017af0130c7f43d7b52/pca.m

http://code.google.com/p/redsvd/

https://cwiki.apache.org/MAHOUT/stochastic-singular-value-decomposition.html

Jeśli twojego języka nie ma, możesz łatwo zrolować swój własny randomizowany SVD; wymaga tylko zwielokrotnienia wektora macierzy, a następnie wywołania gotowego SVD.

Tutaj znajdziesz wprowadzenie do algorytmu algorytmu Jacobi-Davidson, który oblicza maksymalną wartość własną.

W tym artykule badane są aspekty matematyczne. JD pozwala na macierze ogólne (rzeczywiste lub złożone) i może być używane do obliczania zakresów wartości własnych.

Tutaj możesz znaleźć różne implementacje bibliotek JDQR i JDQZ (w tym interfejs C, do którego powinieneś mieć możliwość połączenia z R).

W swoim oryginalnym poście mówisz:

„Próbowałem także użyć interfejsu ARPACK w pakiecie igraph R. Jednak dało to błąd jednej z moich matryc.”

Byłbym zainteresowany dowiedzieć się więcej o błędzie. Jeśli możesz gdzieś udostępnić tę matrycę, byłbym zainteresowany wypróbowaniem na niej ARPACK.

Na podstawie tego, co przeczytałem powyżej, spodziewałbym się, że ARPACK wykonałby bardzo dobrą robotę, wyodrębniając największe (lub kilka największych) wartości własnych rzadkiej macierzy. Mówiąc ściślej, spodziewałbym się, że metody Arnoldi będą dobrze działać w tym przypadku i na tym oczywiście opiera się ARPACK.

Powolną konwergencję metody mocy, gdy w interesującym regionie są blisko siebie wartości własne, wspomniano powyżej. Arnoldi poprawia to poprzez iterację z kilkoma wektorami zamiast metody mocy.

Nie jest to najszybszy sposób, ale dość szybki sposób polega na wielokrotnym trafianiu (początkowo losowym) wektora macierzą, a następnie normalizowaniu co kilka kroków. Ostatecznie zbiegnie się do największego wektora własnego, a zysk w normie dla jednego kroku jest powiązaną wartością własną.

Działa to najlepiej, gdy największa wartość własna jest znacznie większa niż jakakolwiek inna wartość własna. Jeśli inna wartość własna jest zbliżony wielkością do największego, to potrwać do konwergencji, a to może być trudne do ustalenia, czy został konwergentnych.

Pakiet R rARPACK działa dla mnie. I wydaje się być bardzo szybki, ponieważ jest to tylko interfejs dla ARPACK, standardowego pakietu dla rzadkiej algebry liniowej (co oznacza obliczenie kilku wartości własnych i wektorów własnych).