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

9

To jest wyspecjalizowana wersja poprzedniego pytania: Złożoność znalezienia składowej macierzy .

W przypadku macierzy symetrycznych NxN wiadomo, że czas O (N ^ 3) wystarcza do obliczenia rozkładu własnego. Pytanie brzmi: czy możemy osiągnąć sub-sześcienną złożoność? Dzięki.

ds.algorithms time-complexity matrices linear-algebra na.numerical-analysis Lihong Li
źródło
Czy to naprawdę wymaga osobnego pytania? Z pewnością, gdyby ktoś znał odpowiedź na ten szczególny przypadek, powiedziałby to w innym pytaniu.
Warren Schudy,
Podkreśliłem najgorszy przypadek w moim pytaniu, więc myślę, że to jest sprawiedliwe ...
Lev Reyzin
2
Czy jesteś pewien, że czas O (N ^ 3) jest ograniczony? Zobacz moje powiązane pytanie dotyczące eliminacji Gaussa.
Jeffε
Wygląda na to, że można uzyskać z mathoverflow.net/questions/24287/ ...O(n3))dla przybliżonego rozwiązania.
Lew Reyzin

Odpowiedzi:

2

Moim zdaniem ten szczególny przypadek nie jest łatwiejszy niż ogólny. Czysto symbolicznie można zredukować problem znajdowania rozkładu wartości pojedynczej (SVD) do problemu diagonalizacji macierzy symetrycznej. SVD M można odczytać z wektorów własnych i wartości własnych M * M. Zwróć uwagę, że redukcja obejmuje jedynie mnożenie macierzy do obliczenia M * M. Nie wydaje się, aby istniały jakiekolwiek poważne problemy numeryczne.


źródło