Jaka jest faktyczna złożoność czasowa eliminacji Gaussa?

W odpowiedzi na wcześniejsze pytanie wspomniałem o powszechnym, ale fałszywym przekonaniu, że eliminacja „gaussowska” przebiega w czasie . Chociaż oczywiste jest, że algorytm wykorzystuje operacje arytmetyczne , nieostrożna implementacja może tworzyć liczby z wykładniczo wieloma bitami. Jako prosty przykład, załóżmy, że chcemy diagonalizować następującą macierz: $O(n^3)$ $O(n^3)$

[\begin{matrix} 2 & 0 & 0 & \dots & 0 \\ 1 & 2 & 0 & \dots & 0 \\ 1 & 1 & 2 & \dots & 0 \\ ⋮ & ⋮ & ⋮ & ⋱ & ⋮ \\ 1 & 1 & 1 & \dots & 2 \end{matrix}]

$\begin{bmatrix} 2 & 0 & 0 & \cdots & 0 \\ 1 & 2 & 0 & \cdots & 0 \\ 1 & 1 & 2 & \cdots & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots\\ 1 & 1 & 1 & \cdots & 2 \\ \end{bmatrix}$

Jeśli użyjemy wersji algorytmu eliminacji bez podziału, która dodaje tylko liczby całkowite jednego wiersza do drugiego, i zawsze obracamy się po ukośnym wejściu macierzy, macierz wyjściowa ma wektor wzdłuż przekątnej. $(2, 4, 16, 256, \dots, 2^{2^{n-1}})$

Ale jaka jest faktyczna złożoność czasowa eliminacji Gaussa? Większość kombinatorycznych autorów optymalizacji wydaje się być zadowolona z „silnie wielomianu”, ale jestem ciekawa, czym tak naprawdę jest wielomian.

Artykuł Jacka Edmondsa z 1967 r. Opisuje wersję eliminacji Gaussa („prawdopodobnie z powodu Gaussa”), która działa w silnie wielomianowym czasie. Kluczowym spostrzeżeniem Edmondsa jest to, że każdy wpis w każdej macierzy pośredniej jest wyznacznikiem niewielkiej części oryginalnej macierzy wejściowej. Dla macierzy z wpisami liczb całkowitych bitowych, Edmonds udowadnia, że jego algorytm wymaga liczb całkowitych z co najwyżej bitów. Przy „rozsądnym” założeniu, że , algorytm Edmondsa działa w czasie jeśli używamy arytmetyki liczb całkowitych podręcznika, lub w czasie jeśli użyj mnożenia opartego na FFT, na standardowej całkowitej liczbie RAM, która może wykonywać $n\times n$ $m$ $O(n(m+\log n))$ $m=O(\log n)$ $O(n^5)$ $\tilde{O}(n^4)$ $O(\log n)$ -bitowa arytmetyka w stałym czasie. (Edmonds nie przeprowadził tej analizy czasu; twierdził tylko, że jego algorytm jest „dobry”).

Czy to wciąż najlepsza znana analiza? Czy istnieje standardowe odniesienie, które zapewnia lepsze wyraźne ograniczenie czasowe lub przynajmniej lepsze ograniczenie wymaganej precyzji?

Mówiąc bardziej ogólnie: Jaki jest czas działania (na całkowitej pamięci RAM) najszybszego algorytmu znanego z rozwiązywania dowolnych układów równań liniowych?

ds.algorithms reference-request linear-algebra Jeffε
źródło

(wstawianie gwałtownej fali ręcznej) czy nie można ominąć dużego problemu z liczbami całkowitymi w tym konkretnym przypadku przy użyciu małych haszysz modulo? algorytm byłby losowy, ale nadal… To prawda, że to nie odpowiada na pytanie, które zadałeś ...

Suresh Venkat,

Może pomocne byłyby następujące odniesienia? notatki wykładu Lovasz'a , rozdział yap o wyznacznikach (Yap daje złożoność bitową do obliczania wyznaczników za pomocą algorytmu Bareissa). Z książki Yapa (ćwiczenie 10.1.1 (iii)) miałem wrażenie, że nie wiadomo, czy redukcja Gaussa dawała wartości pośrednie, które rosły wykładniczo w rozmiarze bitowym, ale teraz nie jestem pewien.

O (n^{3} M_{B} [n (\log n + L)])

$O(n^3 M_B[n (\log n + L)])$

user834,

Standardowy algorytm eliminacji Gaussa dzieli rząd przestawny przez element przestawny przed zmniejszeniem późniejszych wierszy. Pytanie otwarte odnosi się do tej standardowej wersji. W przykładzie podanym na początku mojego pytania użyto innego wariantu, który NIE dzieli przez element przestawny.

Jeffε

Ciekawy. Czas Yapa dla algorytmu Bereissa jest identyczny z czasem implikowanym przez analizę eliminacji Gaussa przez Edmondsa.

Jeffε

rjlipton przeprowadził ostatnio badania w tym obszarze i cytuje pracę doktorską na ten temat. kluczową częścią analizy jest normalna forma Smitha

2015

Odpowiedzi:

Myślę, że odpowiedź brzmi , gdzie pomijamy czynniki (poli) logarytmiczne. Granica jest przedstawiona w „W. Eberly, M. Giesbrecht, P. Giorgi, A. Storjohann, G. Villard. Rozwiązywanie rzadkich całkowitych układów liniowych. Proc. ISSAC'06, Genova, Włochy, ACM Press, 63-70, lipiec 2006 ”, ale opiera się na pracy Dixona:„ Dokładne rozwiązanie równań liniowych z wykorzystaniem rozszerzeń P-adycznych, John D. Dixon, NUMERISCHE MATHEMATIK, Tom 40, Numer 1, 137-141 ”. $\widetilde O(n^3 \log( \|A\| + \|b\|))$

Elias
źródło

Dzięki za referencje! To odpowiada na moje drugie pytanie, ale nie na moje pierwsze.

Jeffε

Jeśli użyjesz przestawiania, wówczas bitowa wielkość wyników pośrednich w eliminacji Gaussa (GE) jest wielomianowa, nie ma eksplozyjnej eksplozji. Myślę, że to wynik Bareiss. Jeśli chodzi o złożoność GE, w książce Gathena i Gerharda znajduje się algorytm „Nowoczesna algebra komputerowa” do obliczania wyznacznika macierzy , który jest oparty na GE, modułowej arytmetyki i twierdzeniu o reszcie chińskiej (rozdział 5.5, strony 101-105). Złożoność wynosi . Myślę, że współczynnik można by zaoszczędzić za pomocą szybkiej arytmetyki. Jeśli się nie mylę, jest to granica, o której wspomniał użytkownik 834.

A

$A$

O (n^{4} \log^{2} ‖ A ‖)

$O(n^4 \log^2\|A\|)$

n

$n$

Elias

@Elias, jaka jest definicja normy w tym wyrażeniu? Czy jest to największy współczynnik wielkości bezwzględnej? Czy to rozmiar bitów? Czy jest to również wynik dla dowolnych racjonalnych macierzy?

Juan Bermejo Vega

Myślę, że odpowiedź na twoje pierwsze pytanie brzmi również powodu następujących argumentów: praca Edmondsa nie opisuje wariantu eliminacji Gaussa ale dowodzi to, że dowolna liczba obliczona na jednym etapie algorytmu jest wyznacznikiem pewnej podmacierzy A. W książce Schrijvera o teorii programowania liniowego i liczb całkowitych wiemy, że jeśli kodowanie A wymaga bitów (b powinno być w $\widetilde O(n^3 \log( \|A\| + \|b\|))$ $\widetilde O(\log( \|A\|)$ ), to którykolwiek z jego subdeterminantów potrzebuje co najwyżej 2b bitów (Twierdzenie 3.2). Aby eliminacja Gaussa była algorytmem wielomianowym, musimy dbać o obliczone ilorazy: Musimy zlikwidować wspólne czynniki z każdej frakcji, którą obliczamy w dowolnym kroku pośrednim, a następnie wszystkie liczby mają długość kodowania liniową w długości kodowania A.

Matthias Walter
źródło