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

27

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

linear-algebra algorithms eigensystem sparse-matrix moc
źródło

Zobacz moją odpowiedź tutaj: scicomp.stackexchange.com/a/1679/979 . Jest to aktualny temat badań, a obecne metody mogą być lepsze niż Lanczos. Problem obliczania pojedynczych wartości jest równoważny problemowi obliczania wartości własnych.

dranxo

2

Matryca 400 x 400! = Duża. Co również oznacza największy, jeśli „Prawdopodobnie będzie wiele wartości własnych tej samej wielkości”. W numpy land: linalg.eig (random.normal (size = (400,400))) zajmuje około pół sekundy. Czy to jest zbyt wolne?

meawoppl

@meawoppl tak, pół sekundy jest za wolne. Wynika to z faktu, że jest częścią innego algorytmu, który wykonuje te obliczenia wiele razy.

moc

1

@power gotcah. Czy masz przybliżenie do wektora własnego. tzn. czy jest prawdopodobne, że jest podobne do ostatniego rozwiązania, czy też możesz zgadnąć co do jego struktury?

meawoppl

14

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.

Arnold Neumaier
źródło

Muszę sprawdzić, czy największa wartość własna jest większa niż 1. Dokładność musi wynosić tylko 1e-11. Jak dotąd „typowa” matryca ma wymiary 386 x 386. Udało mi się dokonać na tej podstawie 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.

moc

Te informacje należą do twojego pytania - więc edytuj je, a także dodaj więcej informacji (dlaczego wartości własne są prawdziwe? Lub co to znaczy największe?) - zobacz edycję mojej odpowiedzi.

Arnold Neumaier

przepraszam, że nie wyjaśniłem się jasno. Nie wyjaśniłem też jasno, że wartości własne są złożone. Testuję, czy jakieś wartości własne mają wartość jednego lub więcej.

moc

1

(I - A)^{- 1}

$(I-A)^{-1}$

1

patrz edycja 2 w mojej odpowiedzi

Arnold Neumaier

7

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

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

Pedro
źródło

1

co jeśli | λ (n − 1) | = | λ (n) | ?

moc

@power, wtedy zwykła iteracja mocy nie zbiegnie się. Nie wiem, jak dobrze metody ekstrapolacji będą rozróżniać różne wartości własne, w tym celu trzeba przeczytać artykuł.

Pedro

2

| λ_{n - 1} | = | λ_{n} |

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

λ_{n}

$\lambda_n$

λ_{n - 1}

$\lambda_{n-1}$

czy masz odniesienie do pracy naukowej lub książki, która to popiera? A co jeśli \ lambda_ {n} jest złożony?

moc

5

Jeśli istnieje kilka różnych wartości własnych maksymalnego modułu, iteracja mocy zbiega się tylko w wyjątkowych okolicznościach. Generalnie oscyluje w nieco nieprzewidywalny sposób.

Arnold Neumaier,

5

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.

dranxo
źródło

4

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).

Oddech śmierci
źródło

Nie udało mi się znaleźć żadnej literatury, która jednoznacznie stwierdza, że metoda Jacobiego-Davidsona działa dla prawdziwej, ogólnej matrycy.

moc

Chyba że każdy artykuł wyraźnie określa ograniczenie, a argument konwergencji opiera się na ograniczeniu, które nie ma znaczenia.

Deathbreath

Oto inne wyjaśnienie JD. Rozważane macierze są całkowicie ogólne. Żadna specjalna struktura nie jest wykorzystywana, a wyniki specyficzne dla matryc hermitowskich są porównywane i kontrastowane, np. Zbieżność dla matryc ogólnych jest kwadratowa, ale sześcienna dla matryc hermitowskich.

Deathbreath

dzięki za to. Nie znajduję żadnego kodu C dla ogólnej matrycy, więc będę musiał napisać własny. Łącza do algorytmów wydają się być tylko dla macierzy hermetycznych.

moc

1

@power nie znajdziesz również w literaturze wyniku, który stwierdza, że standardowe implementacje QR są zbieżne dla prawdziwej, ogólnej matrycy - jest to otwarty problem i rzeczywiście niedawno znaleziono kontrprzykład dla kodu QR w LAPACK.

Federico Poloni

2

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.

Bill Greene
źródło

Zobaczę, czy wtedy znajdę swoją pracę. Pracowałem nad tym rok temu.

moc

0

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.

Dan
źródło

1

Dziękuję Danowi jednak: w moich matrycach niektóre inne wartości własne będą miały podobną (jeśli nie taką samą) wielkość jak największa. Czy twoja metoda jest podobna do iteracji mocy i ilorazu ilorazu Rayleigha? Batterson i Smillie (1990) piszą, że w przypadku niektórych niesymetrycznych matryc iteracja ilorazowa Rayleigha nie będzie zbieżna. Batterson, S. Smillie, J. (1990) "Rayleigha Iloraz powtórzenie niesymetrycznej matryc" Mathematics of obliczeń, tom 55, Num 191, P 169 - 178

moc

Jeśli inne wartości własne mają taką samą wielkość jak największa ... to czy te wartości również nie są również „największe”?

ely

@EMS: Nadal byłyby „największymi wartościami własnymi”, ale obecność więcej niż jednej największej nadal zabiłaby konwergencję.

Dan

Zastanawiam się tylko, do której wartości własnej chcesz, aby była zbieżna. Rzeczy takie jak iloraz Rayleigha / metoda Mocy mają na celu, gdy istnieje wyraźnie największa wartość własna. Twoje pytanie wymaga znalezienia największej wartości własnej, ale brzmi to tak, jakby to nie było właściwie zdefiniowane dla twojego problemu. Jestem po prostu wprowadzony w błąd przez tytuł postu.

ely

-1

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).

HoangDT
źródło

Witamy w SciComp! Jak mówi pytanie, ARPACK nie działa dla OP, więc ta odpowiedź nie jest naprawdę pomocna.

Christian Clason

@HoangDT To pytanie poprzedza rARPACK

moc

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

Odpowiedzi: