Minimalna liczba operacji arytmetycznych do obliczenia wyznacznika

Czy były prace nad znalezieniem minimalnej liczby elementarnych operacji arytmetycznych potrzebnych do obliczenia wyznacznika macierzy na dla małej i stałej ? Na przykład . $n$ $n$ $n$ $n=5$

cc.complexity-theory linear-algebra determinant Lembik
źródło

Zapytałem o to ekspertów i najwyraźniej obecnie nie wiadomo nawet, czy do obliczenia wyznacznika macierzy 3x3 potrzebne jest 9 multiplikacji.

Jeffrey Shallit

@JeffreyShallit Jeśli możliwe jest

9

$9$ jest to już interesujące (ponieważ na przykład jest mniejsze niż

n^{3}

$n^3$ ). A może

n = 4

$n=4$ ?

Lembik

Nie, wcale nie interesujące. Po 9 pomnożeniach dla n = 3 następuje ekspansja nieletnich. Dla n = 4 ponownie, ekspansja nieletnich daje 40. Nie wiem, jak to zrobić w mniej niż 40 multiplikacjach.

Jeffrey Shallit

@JeffreyShallit Oh rozumiem, dobry punkt. To zadziwiające (przynajmniej dla mnie), jeśli nie ma nic lepszego niż naiwne dla jakiegokolwiek ustalonego .

n

$n$

Lembik

Jeśli ktoś wie, być może może nam powiedzieć.

Jeffrey Shallit

Wiadomo, że liczba operacji arytmetycznych niezbędnych do obliczenia wyznacznika macierzy wynosi , gdzie jest stałą mnożenia macierzy. Zobacz na przykład tę tabelę na Wikipedii, a także jej przypisy i odniesienia. Zauważ, że asymptotyczna złożoność inwersji macierzy jest również taka sama jak mnożenie macierzy w tym samym sensie. $n\times n$ $n^{\omega+o(1)}$ $\omega$

Równoważność jest dość skuteczna. W szczególności możesz rekurencyjnie obliczać wyznacznik macierzy , pracując na blokach przy użyciu dopełniacza Schur: $n\times n$ $(n/2) \times (n/2)$

re odwracalny ⟹ det (\begin{matrix} ZA & b \\ do & re \end{matrix}) = det (re) det (ZA - b {re}^{- 1} do) .

$\text{$D$ invertible}\qquad\implies\qquad\det \begin{pmatrix}A&B\\C&D\end{pmatrix} = \det(D) \det(A-BD^{-1}C).$

Zatem można obliczyć wyznacznik , obliczając dwa wyznaczniki , odwracając jedną macierz , mnożąc dwie pary macierze i niektóre prostsze operacje. Po rozszerzeniu rekurencyjnych wywołań złożoność zostaje zdominowana przez mnożenie i inwersję macierzy. $n\times n$ $(n/2)\times (n/2)$ $(n/2)\times (n/2)$ $(n/2)\times (n/2)$

Działa to dobrze nawet dla małych a nawet bez użycia algorytmów macierzy sub-sześciennej. (Oczywiście kończy się to mniej więcej równoważnością eliminacji Gaussa.) Na przykład dla możemy obliczyć z dwoma mnożeniami, z czterema podziałami, z mnożenia, z dwoma mnożeniami, a ostateczna odpowiedź z jednym mnożeniem. Łączna liczba wynosi pomnożeń plus podziałów, czyli mniej niż $n$ $n=4$ $\det(D)$ $D^{-1}$ $BD^{-1}C$ $2\times 8=16$ $\det(A-BD^{-1}C)$ $2+4+16+2+1=25$ $40$ z ekspansji kofaktora. Użycie algorytmu Strassena zapisuje tutaj dwa mnożenia, ale bardziej asymptotycznie.

Możesz zauważyć, że to rozszerzenie używa podziału. Jeśli chcesz uniknąć podziału, możesz to zrobić w operacjach , pracując z sekwencjami Clow i programowaniem dynamicznym . Jest również znany sposób w celu uzyskania mnożenia i nie podziałów. $O(n^4)$ $n^{2+\omega/2+o(1)}$

A. Rex
źródło

Czy znasz dolną granicę tylko liczby mnożeń? Nawet dla n = 3?

Jeffrey Shallit

Twoje sformułowanie „liczba operacji arytmetycznych niezbędnych do obliczenia wyznacznika macierzy wynosi ” sugeruje, że dolna granica jest znana. Ale nie widziałem tego w żadnej z cytowanych prac. Czy coś brakuje?

n \times n

$n \times n$

n^{ω + o (1)}

$n^{\omega +o(1)}$

Jeffrey Shallit

Dolna granica znajduje się w artykule W.Baura i V. Strassena „Złożoność pochodnych cząstkowych” ( dx.doi.org/10.1016/0304-3975(83)90110-X )

Vladimir Lysikov

Minimalna liczba operacji arytmetycznych do obliczenia wyznacznika

Odpowiedzi: