Moje pytanie jest proste:
Jaki jest najgorszy czas z najbardziej znanych algorytm działa dla wyliczania eigendecomposition danego matrycy?
Czy skład eigend redukuje się do mnożenia macierzy, czy w najgorszym przypadku są najlepiej znanymi algorytmami (przez SVD )?
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.
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 ?n O ( p o l y ( 1 / ϵ ) n 3 )
EDYCJA 2 : Zobacz to powiązane pytanie dotyczące macierzy symetrycznych .
Odpowiedzi:
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ω+1m m n3+n2log2nlogb 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).
źródło
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
źródło
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(n3MB[n(logn+L)]) MB(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.
źródło
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.
źródło
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ω+η) ω η >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.
źródło
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
źródło