Jaka jest złożoność przestrzeni przy obliczaniu wartości własnych?

Szukam pracy ankietowej lub książki obejmującej wyniki dotyczące złożoności przestrzeni typowych operacji algebry liniowej, takich jak ranga macierzy, obliczanie wartości własnych itp. Podkreślam część „złożoności przestrzeni”, która oznacza złożoność przestrzeni pracy, a nie złożoność czasu, ponieważ łatwiej jest prześledzić wyniki czasowe. Doceniam wszelkie odniesienia w tej sprawie.

Dzięki.

linear-algebra space-complexity

— Gil
źródło

Domyślam się, że złożoność jest zawsze co najwyżej liniowa (np. dla macierzy ). Czy interesuje Cię „całkowita przestrzeń” czy „przestrzeń do pracy”?

O (n m)

$O(nm)$

n \times m

$n\times m$

— Yuval Filmus,

powinienem wspomnieć, że interesuje mnie przestrzeń do pracy.

— gil

Jestem pewien, że to

dla macierzy

. Podstawowym powodem jest to, że znam dwie przydatne metody ich obliczania i obie są kwadratowe w przestrzeni. Pierwszym jest obliczenie charakterystycznego wielomianu (kwadratowego) i znalezienie korzeni. Po drugie, stosuję pewne metody aproksymacyjne, które wszystkie muszą przechowywać zmodyfikowaną matrycę (ale nie mogę tego rozwinąć, minęło trochę czasu, odkąd studiowałem numeryczną algebrę liniową).

O (n^{2})

$\mathcal O(n^2)$

n \times n

$n\times n$

— yo „

Aby rozwinąć kwestię przedstawioną przez @Yuval Filmus, złożoność przestrzeni jest dość wrażliwa na określony model obliczeniowy. W szczególności, ponieważ wyjście ma rozmiar liniowy, można odtwarzać sztuczki, używając taśmy wyjściowej jako obszaru roboczego, chyba że model wyraźnie określa taśmę wyjściową tylko do zapisu. Aby uniknąć takich problemów, pokusiłbym się o przeformułowanie jako problemów decyzyjnych (np. Jako dane wejściowe trzy macierze, sprawdź, czy trzecia jest iloczynem pierwszych dwóch). Czy możesz podać model, który miałeś na myśli? (Poza tym nie znam książek o złożoności przestrzeni i nie znalazłem też żadnych przydatnych ankiet.)

— András Salamon,

w odniesieniu do @ AndrásSalamon, więc przydatna dla mnie wersja decyzyjna może być: jest k-tą wartością własną w liczbie większej niż q. dla liczby całkowitej k i wymiernej q. Dzięki.

— gil

Odpowiedzi:

Wersje decyzyjne wielu typowych problemów w algebrze liniowej nad liczbami całkowitymi (lub wymiernymi) znajdują się w klasie , patrz artykuł $\mathsf{DET}$

Gerhard Buntrock, Carsten Damm, Ulrich Hertrampf, Christoph Meinel: Struktura i znaczenie klasy Logspace-MOD. Teoria systemów matematycznych 25 (3): 223–237 (1992)

jest zawarte w . $\mathsf{DET}$ $\mathsf{DSPACE}(\log^2)$

Obliczanie wartości własnych jest nieco bardziej delikatne:

1) W można obliczyć współczynniki charakterystycznego wielomianu. $\mathsf{DSPACE}(\log^2)$

2) Następnie możesz użyć algorytmu równoległego Reifa i Neffa do obliczenia przybliżeń wartości własnych. Algorytm działa na CREW-PRAM w czasie logarytmicznym z wielomianowo wieloma procesorami, dzięki czemu można go symulować za pomocą przestrzeni pollogarytmicznej. (Nie jest to wyraźnie określone w pracy, ale ich pamięć PRAM powinna być jednolita dla log-space). Zastosowana przestrzeń jest polilogarytmiczna pod względem wielkości matrycy wejściowej i dokładności . Precyzja oznacza, że otrzymujesz przybliżenia aż do błędu addytywnego . $p$ $p$ $2^{-p}$

Jest to konkatenacja funkcji obliczalnych w przestrzeni pollogarytmicznej. (Taśmy wyjściowe są tylko do zapisu i jednokierunkowe.)

C. Andrew Neff, John H. Reif: Efektywny algorytm dla problemu złożonych korzeni. J. Complexity 12 (2): 81-115 (1996)

— Markus Bläser
źródło

$log^2$ $NC^2$

— Lior Eldar
źródło