Złożoność znalezienia składowej macierzy

40

Moje pytanie jest proste:

Jaki jest najgorszy czas z najbardziej znanych algorytm działa dla wyliczania eigendecomposition danego matrycy? $n \times n$

Czy skład eigend redukuje się do mnożenia macierzy, czy w najgorszym przypadku są najlepiej znanymi algorytmami (przez SVD )? $O(n^3)$

Proszę zauważyć, że proszę o analizę najgorszego przypadku (tylko w kategoriach ), a nie o granice ze stałymi zależnymi od problemu, takimi jak numer warunku. $n$

EDYCJA : Biorąc pod uwagę niektóre odpowiedzi poniżej, pozwolę sobie dopasować pytanie: Byłbym zadowolony z przybliżenia . Przybliżenie może być multiplikatywne, addytywne, wejściowe lub dowolną rozsądną definicję, jaką chcesz. Jestem zainteresowany, czy istnieje znany algorytm, który lepiej zależy od niż coś takiego jak ? $\epsilon$ $n$ $O(\mathrm{poly}(1/\epsilon)n^3)$

EDYCJA 2 : Zobacz to powiązane pytanie dotyczące macierzy symetrycznych .

— Lew Reyzin
źródło

Czy przyjrzałeś się redukcji od inwersji macierzy do mnożenia macierzy w podręczniku algorytmów CLRS? Zacznę od przyjrzenia się tym pomysłom, aby sprawdzić, czy dotyczą one rozkładu własnego.

— Warren Schudy,

Tak - wydaje się, że rozciągają się one na znalezienie rozkładu LU, ale nie wiem, jak sprawić, by działał on dla rozkładu własnego.

— Lew Reyzin

Czy wiesz, czy jest najbardziej znanym algorytmem do obliczania SVD?

O (n^{3})

$O(n^3)$

— Robin Kothari,

1

O ile mi wiadomo jest najbardziej znanym SVD, ale nie jestem pewien. Ale rozkład własny wydaje się mniej ogólny, dotyczy tylko macierzy , które spełniają pewną właściwość, więc wydaje się możliwe, że istnieje lepszy algorytm dla tego przypadku. W ogóle nie jestem ekspertem w tej dziedzinie, więc miałem nadzieję, że ktoś był świadomy najnowocześniejszych rozwiązań w tym zakresie.

O (min (m n^{2}, m^{2} n))

$O(\min(mn^2, m^2n))$

n \times n

$n \times n$

— Lew Reyzin

W porządku. Nie wiem też dużo o tym obszarze, ale być może obliczenia SVD można sprowadzić do eigendecomposition, ponieważ jeśli potrafisz eigendecompose AA * i A * A, dostaniesz prawą i lewą macierz dla SVD.

— Robin Kothari,

18

Ryan odpowiedział na podobne pytanie dotyczące przepływu matematyki. Oto link: mathoverflow-answer

Zasadniczo można zredukować obliczanie wartości własnej do mnożenia macierzy, obliczając symboliczną determinantę. Daje to czas działania O ( ), aby uzyskać bitów wartości własnych; najbardziej znanym obecnie środowiskiem wykonawczym jest O ( ) dla przybliżenia w granicach . $n^{\omega+1}m$ $m$ $n^3+n^2\log^2 n\log b$ $2^{-b}$

Odniesieniem do Ryana jest: `` Victor Y. Pan, Zhao Q. Chen: The Complexity of the Matrix Eigenproblem. STOC 1999: 507-516 ''.

(Wierzę, że jest też dyskusja na temat związku między złożonością wartości własnych a mnożeniem macierzy w starszej książce Aho, Hopcroft i Ullman `` The Design and Analysis of Computer Algorytms '', jednak nie mam tej książki w przede mną i nie mogę podać dokładnego numeru strony).

— dziewice
źródło

13

Znalezienie wartości własnych jest z natury iteracyjnym procesem: Znalezienie wartości własnych jest równoznaczne ze znalezieniem pierwiastków wielomianu. Co więcej, twierdzenie Abla-Ruffiniego stwierdza, że generalnie nie można wyrazić korzeni arbitralnego wielomianu w prostej zamkniętej formie (tj. Z rodnikami takimi jak formuła kwadratowa). Dlatego nie możesz liczyć na dokładne obliczenie wartości własnych.

Oznacza to, że algorytm rozkładu widmowego musi być przybliżony. Czas działania dowolnego ogólnego algorytmu musi zależeć od pożądanej dokładności; nie może zależeć tylko od wymiaru.

Nie jestem w tym ekspertem. Domyślam się, że sześcienna zależność od n jest całkiem dobra. Algorytmy, które widziałem, wykorzystują mnożenie macierz-wektor, a nie mnożenie macierz-macierz. Byłbym więc nieco zaskoczony, gdyby wszystko sprowadzało się do mnożenia macierzy.

Zajrzyj na http://en.wikipedia.org/wiki/List_of_numerical_analysis_topics#Eigenvalue_algorithms

— Tomasz
źródło

Dziękuję za odpowiedź - będę potrzebował trochę czasu, aby to przyswoić! Ale jeśli użyje się mnożenia macierzy i wektora, zależność od n może być lepsza niż n ^ 3.

— Lew Reyzin

6

Dam tylko częściową odpowiedź dotyczącą wartości własnych macierzy.

Jak wspomniano wcześniej, istnieje wiele iteracyjnych metod znajdowania wartości własnych macierzy (np. Iteracja mocy), ale ogólnie znalezienie wartości własnych sprowadza się do znalezienia korzeni charakterystycznego wielomianu. Znalezienie charakterystycznego wielomianu można wykonać w , gdzie jest kosztem mnożenia bitów a jest wielkością bitu maksymalnego wpisu, o symboliczne wyznaczanie wyznaczników za pomocą algorytmu Bareissa . Zobacz książkę Yap na temat „Podstawy algebry algorytmicznej” , w szczególności rozdział. 10, „Systemy liniowe” . $O(n^3 M_B[n(log n + L)] )$ $M_B(s)$ $s$ $L$

Po znalezieniu charakterystycznego wielomianu można znaleźć pierwiastki z dowolnym pożądanym stopniem dokładności, stosując przedziały izolujące. Zobacz książkę Yap, rozdz. 6 „Korzenie wielomianów”, by poznać szczegóły. Zapominam dokładny czas działania, ale jego wielomian w stopniu charakterystycznego wielomianu i pożądanych cyfr dokładności.

Podejrzewam, że obliczanie wektorów własnych do dowolnego stopnia dokładności jest również wielomianowe, ale nie widzę prostego algorytmu. Istnieją oczywiście standardowe torby sztuczek, które zostały wcześniej wspomniane, ale o ile mi wiadomo, żadna z nich nie gwarantuje wielomianowego czasu działania dla pożądanej dokładności.

— użytkownik834
źródło

ciekawe, ale wydaje się to nawet gorsze niż n ^ 3. czy wiemy, że to najlepsze z możliwych?

— Lew Reyzin

Czasy działania algorytmów tego rodzaju są powiązane ze złożonością mnożenia macierzy, które wynosi około O (n ^ 3). Wiem o algorytmie Strassena, ale jeśli nie zignorujesz liczbowych problemów ze stabilnością, to sądzę, że odzyskujesz O (n ^ 3) do mnożenia macierzy. Metody iteracyjne mogą zbiegać się szybciej w przypadku „przeciętnym”, ale ogólnie uważam, że O (n ^ 3) jest najlepszym, co możesz zrobić.

— user834

Więc mówisz, że jeśli nie przejmuję się liczbowymi problemami ze stabilnością, możemy sprowadzić to do O (n ^ 2,376)?

— Lew Reyzin

5

Możesz sprawdzić nowy artykuł Commandur i Kale'a, który podaje kombinatoryczny algorytm dla Max-Cut. Wydaje się (z pobieżnego odczytu), że ich algorytm opiera się na kombinatorycznym znalezieniu wektora własnego odpowiadającego maksymalnej wartości własnej, a następnie zastosowaniu algorytmu Luca Trevisana, gdy tylko ten wektor własny się pojawi.

Wygląda na to, że używają alternatywnego podejścia do algorytmu Lanczosa w celu znalezienia takiego wektora własnego, więc może być interesujące. Nie jestem pewien, jaka jest złożoność ich metody znalezienia wektora własnego, ale warto się temu przyjrzeć. Ponadto, ponieważ interesuje ich stosunek przybliżenia, a nie czas jako taki, są oni zainteresowani, niezależnie od podanych granic czasowych mogą nie być optymalne.

— gwiazdka
źródło

1

To stare pytanie, ale wydaje się, że brakuje ważnej literatury.

Istnieją algorytmy, dla których mamy silniejsze wsparcie teoretyczne. Na przykład istnieją iteracje oparte na funkcji znaku macierzy, patrz na przykład „Szybka algebra liniowa jest stabilna” autorstwa Demmela, Dumitriu i Holtza . W tym artykule pokazano, że problem wartości własnej można rozwiązać w czasie , gdzie jest wykładnikiem mnożenia macierzy, a jest dowolną liczbą . $(O^{\omega+\eta})$ $\omega$ $\eta$ $>0$

Tak, istnieje dokument Pan + Chen + Zheng, który sugeruje złożenie charakterystycznego wielomianu i obliczenie w BigFloat, ponieważ na końcu tracisz wiele bitów dokładności, ale niewiele osób uważa to za praktyczne podejście.

Wspominam również, że najczęściej używany algorytm, iteracja Francisa QR, nie ma żadnego dowodu zbieżności dla ogólnych matryc; książka Kressnera omawia kilka kontrprzykładów.

— Sébastien Loisel
źródło

0

Tak, prawie całą numeryczną algebrę liniową można sprowadzić do mnożenia macierzy, choć jak zawsze problemem jest stabilność numeryczna. Ponadto w przypadku takich problemów, jak skład eigend, powinieneś być zadowolony z przybliżenia, ponieważ rozwiązanie może być nieracjonalne. Sprawdź książkę Obliczenia wielomianowe i macierzowe Bini i Pan.

Oto kolejne odniesienie - szybka algebra liniowa jest stabilna http://www.netlib.org/lapack/lawnspdf/lawn186.pdf

— Anonimowy
źródło

3

Dzięki za wskaźnik, ale przeszukując książkę w książkach Google, nie mogłem znaleźć redukcji do mnożenia macierzy. Czy masz wskaźnik do konkretnego odniesienia lub algorytmu? Ich algorytmy SVD wydają się zależeć od liczby warunków macierzy, co nie jest najgorszym przypadkiem analizy. Jeśli chodzi o problemy ze stabilnością liczbową itp., Załóżmy idealny przypadek, w którym wszystkie mnożenia i podziały zajmują czas jednostkowy i dają dokładne odpowiedzi.

— Lew Reyzin