Jaki jest najskuteczniejszy sposób obliczenia wektora własnego gęstej macierzy odpowiadającego wartości własnej największej wielkości?

Mam gęstą prawdziwą symetryczną macierz kwadratową. Wymiar wynosi około 1000 x 1000. Muszę obliczyć pierwszy główny składnik i zastanawiać się, jaki może być najlepszy algorytm.

Wygląda na to, że MATLAB korzysta z algorytmów Arnoldi / Lanczos (dla eigs). Ale po przeczytaniu o nich nie jestem pewien, czy mają one jakąkolwiek przewagę nad prostą iteracją mocy , ponieważ moja macierz nie jest rzadka i interesuje mnie tylko pierwszy wektor własny.

Jakieś rekomendacje, jaki jest najszybszy algorytm w tym przypadku?

linear-algebra algorithms eigensystem

— Mika Fischer
źródło

Na moim komputerze, na losowo wygenerowanej macierzy symetrycznej 1000 X 1000, funkcja „własna” w R zajęła około jednej sekundy, aby obliczyć wszystkie wartości własne i wektory, zaokrąglając w górę. Twój przebieg może się różnić, ale wątpię, czy Twój wybór algorytmu robi jakąkolwiek różnicę w takich momentach.

Tak, to prawda. Naprawdę nie martwię się, aby mój program działał szybciej. Jestem tylko ciekawy, czy wspomniane bardziej skomplikowane techniki są również uważane za lepsze w tym przypadku użycia (gęsty, tylko pierwszy wektor własny), czy też istnieją różne techniki dla gęstych matryc.

Czy masz na myśli wektor własny odpowiadający największej lub najmniejszej wartości własnej? Brzmi jak chcesz tego pierwszego.

— Jack Poulson

Tak, wektor własny odpowiadający wartości własnej o największej wielkości.

— Mika Fischer

Odpowiedzi:

Najszybsza metoda prawdopodobnie zależeć będzie od spektrum i normalności macierzy, ale we wszystkich przypadkach algorytmy Kryłowa powinny być zdecydowanie lepsze niż iteracja mocy. GW Stewart ma miłą dyskusję na ten temat w rozdziale 4, sekcja 3 Matrycowych algorytmów, tom II: Eigensystems :

Sposób zasilania jest oparty na obserwacji, że jeśli ma dominującą eigenpair następnie w łagodnych ograniczeń wektory produkują coraz dokładniejszych przybliżeń dominującemu wektor własny. Jednak na każdym kroku sposób władza uważa tylko jeden wektor $A$ $u$ $A^k u$ $A^k u$ , która wynosi wyrzucać informacji zawartej w poprzednio wytwarzanych wektorów. Okazuje się, że ta informacja jest cenna ... ”

i dalej pokazuje, że dla macierzy diagonalnej z -tą wartością diagonalną ustawioną na (licząc od ), po 25 iteracjach podprzestrzeń Kryłowa przechwytuje dominujący wektor własny o osiem rzędów wielkości lepiej niż iteracja mocy. $100 \times 100$ $i$ $.95^i$ $i=0$

— Jack Poulson
źródło

Hmm, myślałem, że MRRR jest teraz standardową metodą, gdy ktoś chce tylko kilku wektorów własnych ...

— JM

k

$k$

O (k n^{2} + k^{2} n + k^{3})

$O(k n^2 + k^2 n + k^3)$

k

$k$

n

$n$

Widzę; w jakiś sposób miałem wrażenie, że najpierw trzeba zrobić tridiagonalizację przed zrobieniem Kryłowa. Dzięki!

— JM

Lanczos faktycznie stopniowo buduje wspomnianą matrycę trójosiową.

— Jack Poulson

Iteracja mocy jest najprostsza, ale jak wspomniano powyżej, prawdopodobnie zbiegnie się bardzo wolno, gdyby matryca była bardzo nienormalna. Występuje zjawisko „garbu”, w którym sekwencja wydaje się zmieniać na wiele iteracji, zanim zacznie się zachowanie asymptotyczne.

Ponieważ macierz jest symetryczna, można rozważyć iteracje RQI, które w przypadku symetrycznym dają zbieżność sześcienną: http://en.wikipedia.org/wiki/Rayleigh_quotient_iteration .

To, co sprawia, że iteracje Arnoldiego lub Lanczosa są bardzo ładne (przynajmniej moim zdaniem, ale nie badam numerycznej algebry liniowej), jest to, że są bardzo wszechstronne. Zazwyczaj można kontrolować, które wartości własne dają i ile otrzymujesz. Jest to szczególnie prawdziwe w przypadku symetrycznym (a nawet lepiej, jeśli macierz jest określona). W przypadku problemów symetrycznych są bardzo solidne. Jako czarna skrzynka działają dobrze, ale są również bardzo wrażliwe na nowe informacje o problemach, takie jak zdolność do rozwiązywania układów z matrycą.

— Reid.Atcheson
źródło