Determinant uogólnionej macierzy Vandermonde'a

Macierz Moore'a jest podobna do macierzy Vandermonde, ale ma nieco zmodyfikowaną definicję. http://en.wikipedia.org/wiki/Moore_matrix

Jaka jest złożoność obliczenia wyznacznika danego pełnego rzędu macierzy Moore'a modulo jakiejś liczby całkowitej? $n \times n$

Czy wyznacznik Moore'a można zredukować z przy użyciu technik FFT do dla niektórych ? $O(n^{3})$ $O(n\log^{a}n)$ $a \in \mathbb{R}_{+} \cup \{0\}$

Czy złożoność Moore det modulo jest liczbą całkowitą, a Vandermonde jest taka sama? Złożoność wyznacznika Vandermonde'a to (Strona 644 w Handbook of Theoretical Computer Science: Algorytmy i złożoność Jan Leeuwen) $O(n\log^{2}n)$

Post podobny do bieżącego: Determinant modulo m

cc.complexity-theory algebraic-complexity T ....
źródło

Czy wyznacznik Moore'a można nawet obliczyć w czasie O (n ^ 3) (na całkowitej liczbie RAM)?

Jeffε

@ Jɛ ff E Dlatego wspomniałem modulo losowa

N \in N

$N \in \mathbb{N}$

T ....

Nawiasem mówiąc, jestem ciekawy, czy istnieją znane aplikacje, które mogłyby skorzystać z takiego „superszybkiego” algorytmu?

Juan Bermejo Vega

ffE, czy wiesz, czy obliczenie podwójnego modularnego potęgowania przez

jest w BPP dla trywialnego

? Ponieważ jest to problem przy obliczaniu współczynników macierzy.

ε

$\varepsilon$

N

$N$

N

$N$

Juan Bermejo Vega

Odpowiedzi:

Ogólnie rzecz biorąc, istnieje teoretyczny algorytm czasowy do znajdowania dekompozycji LU dowolnej macierzy przy użyciu algorytmu Coppersmitha-Winograda , który następnie oczywiście wyznacza wyznacznik (dodając czas ). Istnieje jednak problem polegający na tym, że algorytm Coppersmith – Winograd nie jest uważany za przydatny w praktyce. Afaik, ludzie najczęściej używają algorytmu Strassena czasu . Czy Bo_Factorize nie wykorzystuje Boost w UBLAS ? $O(n^{2.376})$ $O(n)$ $O(n^{2.807})$

W twoim przypadku macierz Moore'a powinna pozwolić na znaczną optymalizację, ponieważ w zasadzie każda procedura eliminacji Gaussa, taka jak rozkład LU, może być przeprowadzona abstrakcyjnie. Rzeczywiście, znajdziesz fajną formułę do obliczania wyznacznika Moore'a , do którego odwołuje się wikipedia , co prawdopodobnie można udowodnić, po prostu opracowując rozkład LU w ogóle. $O(n)$

Jeff Burdges
źródło

Cześć Jeff: Które referencje odwołujesz się do formuły O (n ^ 2). Myślę, że Vandermonde det można obliczyć w O (nlogn), ale nie mogę znaleźć odniesienia. Więc czy Moore powinien również znajdować się w O (nlogn)?

T ....

Tak, powinienem był powiedzieć O (n) oczywiście, naprawdę O (n log n) dla dużego n.

Jeff Burdges

Cześć Jeff: Czy masz referencje?

T ....

@JeffBurdges: Jeśli czas działania wynosi O (n log n) „dla dużego n”, to z definicji czas działania to O (n log n), a nie O (n).

Jeffε

Nie widzę formuły

odwołuje się Wikipedia. W najlepszym razie wygląda

O (n)

$O(n)$

Θ (n^{2})

$\Theta(n^2)$

Peter Taylor,

Ważne jest, aby w podanej definicji macierz żyła w polu skończonym, powiedzmy gdzie jest liczbą pierwszą. Pozwala to użyć twierdzenia Eulera do obliczenia podwójnych wykładniczych $\mathbb{Z}_m$ $m$ które pojawiają się w macierzy w czasie $a^{q^e}\mod m$ . $O(\log (mn) \; M(\log m))$ W przeciwnym razie wydaje się trudne nawet obliczenie współczynników macierzy bez faktoryzacji .

a^{q^{i}} \equiv a^{q^{i} (\mod φ (m))} (\mod m)

$a^{q^i}\equiv a^{q^i\pmod{\varphi(m)}}\pmod m$

m

$m$

Jeśli jest liczbą pierwszą lub można je efektywnie rozłożyć na czynniki, w najgorszym przypadku złożoność jest zdominowana przez liczbę kroków potrzebnych do mnożenia macierzy . Na przykład podejście normalnej formy Smitha , o którym wspomniałem w poście partnerskim , obliczałoby wyznacznik w czasie $m$ $O(n^\omega)$ jeśli używasz „powolnych” algorytmów mnożenia . można wybrać jako 2,373. $O\left( n^\omega \; \log^2m\; \log (mn) \right)$ $^*$ $\omega$

Dostajesz spowolnienie w Moore vs Vandermonde ponieważ należy podwoić-exponentiate współczynniki macierzy. Kiedy można wyliczyć to spowolnienie jest po prostu polilogarytmiczne na . Jeśli nie, przedstawiony algorytm daje redukcję Cooka do potęgowania podwójnego modułowego na . $m$ $m$ $\mathbb{Z}_m$

Uwaga *: szybsze algorytmy mnożenia liczb całkowitych pozwalają zastąpić z . $\log^2 m$ $M(\log m \log\log m)$

Aktualizacja : w sprawie możliwości osiągnięcia . $O(n\log^a n)$

Nie mam na to jednoznacznej odpowiedzi, ale znalazłem informacje, które mogą przyspieszyć wyszukiwanie.

Algorytmy dla strukturalnych macierzy, które obliczają wielkości takie jak wyznaczniki w czasie są w literaturze nazywane „superszybkimi”. Wszystkie znane „superszybkie” algorytmy dla matryc strukturalnych (Vandermonde, Toeplitz, Hankel) wydają się polegać na wspólnej właściwości tych matryc, znanej jako „niski stopień przemieszczenia”. Przeprowadź dyskusję na temat pierwszego rozdziału tej książki (strony z otwartym dostępem) lub w tym artykule [ACM] , [PDF] . $O(n\log^a n)$

Z tego, co przeczytałem, biorąc pod uwagę macierzy Moore'a , gdybyś był w stanie znaleźć macierze , takie, że nowa macierz (lub alternatywnie ) ma następującą strukturę $m\times n$ $M$ $A$ $B$ $L(M)=AM-MB$ $L(M)=M- AMB$

L. (M.) = \sum_{k = 1}^{r} {sol}_{k} h_{k}^{T.}

$L(M) = \sum_{k=1}^r g_k h_k^T$

, a ranga jest mała (stała lub ograniczona przez $r>0$ ), a następnie możesz zastosować istniejące techniki (sprawdź rozdział 5 książki, strony z otwartym dostępem) do trójkątnego a zatem obliczyć , używając . Powyżej,,oznaczają wektory. Jeśli nie możesz znaleźć powyższej książki, aby przeczytać całość,ten artykułzawiera również wiele informacji na temat tych metod. $o(\text{min} \;\{m,n\})$ $M$ $\det{M}$ $O(n\log^2 n)$ $g_k$ $h_k$

Niestety, nie byłem w stanie znaleźć struktury o niskim stopniu przesunięcia dla matrycy Moore'a (ma Vandermonde). Wydaje się, że główna komplikacja wynika z „nieliniowej” natury podwójnego wykładniczego. Jeśli to pomoże, sprawy dotyczące Vandermonde, Cauchy, Toeplitz, Hankel zostały opracowane w książce.

Juan Bermejo Vega
źródło

3

$3$

m

$m$

3^{k}

$3^{k}$

k

$k$

3^{k}

$3^k$

to nie upraszcza złożoności, powiedziałbym, ponieważ pole jest bardzo bardzo duże.

T ....

φ (3^{k}) = 3^{k} - 3^{k - 1}

$\varphi(3^k)=3^k-3^{k-1}$

a^{q^{i}} \mod m

$a^{q^i}\mod m$

b = q^{i} \mod φ (3^{k})

$b=q^i\mod \varphi(3^k)$

a^{b} \mod 3^{k}

$a^b\mod 3^k$

O (\log (n 3^{k}) M (k \log 3))

$O(\log(n3^k)M(k \log3))$

M (n) = n^{2}

$M(n)=n^2$

O (n^{ω} k^{2} l o g^{2} 3 (\log n + k \log 3))

$O(n^\omega k^2 log^2 3 (\log n + k\log 3))$

ω

$\omega$

1 + ϵ

$1 + \epsilon$

ω \geq 2

$\omega \ge 2$