Złożoność mocy macierzy obliczeniowych

Jestem zainteresowany obliczania „th moc macierzy . Załóżmy, że mamy algorytm mnożenia macierzy, który działa w czasie . Następnie można łatwo obliczyć w czasie . Czy można rozwiązać ten problem w mniejszym stopniu złożoności? $n$ $n\times n$ $A$ $\mathcal{O}(M(n))$ $A^n$ $\mathcal{O}(M(n)\log(n))$

Wpisy w macierzy mogą na ogół pochodzić z semiringu, ale można założyć dodatkową strukturę, jeśli to pomoże.

Uwaga: rozumieć, że zasadniczo obliczeniowym w czas dałoby algorytm potęgowania. Ale wiele interesujących problemów sprowadza się do specjalnego przypadku potęgowania macierzy, gdzie m = , a ja nie byłem w stanie udowodnić tego samego na temat tego prostszego problemu. $A^m$ $o(M(n)\log(m))$ $o(\log m)$ $\mathcal O(n)$

— Shitikanth
źródło

jakie są wpisy macierzy? Liczby całkowite?

— Kaveh

Wpisy mogą na ogół pochodzić z pół wieku, ale możesz założyć dodatkową strukturę, jeśli to pomoże.

— Shitikanth

Nie mogłem uzyskać redukcji z mnożenia do kwadratu z wyżej zaproponowanej metody (tj. Używając ). Jednak użycie działa. Daje to jednak tylko przy obliczaniu .

(A \pm B)^{2}

$(A\pm B)^2$

{(\begin{array}{cc} 0 & A \\ B & 0 \end{array})}^{2}

$\left( \begin{array}{cc} 0 & A \\ B & 0 \end{array} \right)^2$

Ω (M (n))

$\Omega(M(n))$

A^{n}

$A^n$

— Shitikanth

Odpowiedzi:

Jeżeli matryca jest diagonalizable następnie biorąc th mocy mogą być wykonane w czasie gdzie jest czas diagonalize . $n$

O (D (n) + n \log n)

$O(D(n)+ n\log n)$

D (n)

$D(n)$

A

$A$

Aby uzupełnić szczegóły, jeśli z przekątną , to $A=P^{-1}DP$ $D$

A^{n} = (P^{- 1} D P)^{n} = P^{- 1} D^{n} P

$A^n = (P^{-1}DP)^n = P^{-1}D^nP$

i można obliczyć, po prostu przenosząc każdy element przekątnej (każdą wartość własną ) na tą moc. $D^n$ $A$ $n$

— Ran G.
źródło

Nawet jeśli macierz jest diagonalizowalna, najbardziej znane algorytmy dla składu eigend zajmują czas

. Za pomocą algorytmu Coppersmith-Winograd, że już

algorytm do obliczania

O (n^{3})

$O(n^3)$

O (n^{2.3727} \log (m))

$O(n^{2.3727}\log(m))$

A^{m}

$A^m$

— Shitikanth

(1) Czas, który zacytowałeś, nie pochodzi od Coppersmith-Winograd (jak zapewne wiesz). (2) Wszystkie algorytmy tej formy działają tylko dla pierścieni; nie działają w przypadku semiracji ogólnych (jak na to pozwalasz w swoim pytaniu).

— Ryan Williams

Jednym dobrym wyjściem jest SVD . Biorąc pod uwagę rzeczywistym macierzy z pełno SVD rozdziela się od siebie, jak , gdzie jest macierzą diagonalną, w czasie . Według właściwości SVD, , więc tylko macierz diagonalna musi być potęgowana wykładniczo, i można to zrobić w $n\times n$ $A$ $A=U\Sigma U^T$ $\Sigma$ $O(n^3)$ $A^m = U \Sigma^m U^T$ $O(n\log m)$ czas. Przeprowadzenie końcowego mnożenia wymaga , więc mamy w sumie operacje . $U \times \Sigma^m \times U^T$ $O(n^{2.3727})$ $O(n^3 + n \log m)$

Aktualizacja po komentarzu Chodzi o to, że po znalezieniu SVD każda moc potrzebuje tylko do obliczenia według własnego algorytmu CW. Ale to nie jest twoje pytanie. Jeśli naprawdę istniałby algorytm , natychmiast przekształciłby się w algorytm dla liczb całkowitych. Podejrzewam, że jeden taki nie istnieje. $O(n^{2.3727}+n \log m)$ $o(M(n)\log(m))$ $o(\log n)$

— PKG
źródło

Ponieważ algorytm Coppersmith-Winograd znajduje iloczyn dwóch macierzy w

razem, już

algorytm do obliczania

. Interesuje mnie wiedza, czy można to poprawić bez potrzeby lepszego algorytmu mnożenia macierzy, szczególnie dla

O (n^{2.3727})

$O(n^{2.3727})$

O (n^{2.3727} \log (m))

$O(n^{2.3727}\log(m))$

A^{m}

$A^m$

m = O (n)

$m=O(n)$

— Shitikanth

SVD nie podaje ogólnie

- macierz po prawej stronie to

A = U Σ U^{⊤}

$A = U \Sigma U^\top$

V \neq U^{⊤}

$V \ne U^\top$

— Suresh

Trochę mylące jest również mieć

dla mocy, więc użyję

. Jeżeli

należy wziąć

czasu, aby znaleźć

, co odpowiada pomnożenie liczb

n

$n$

m

$m$

n = 1

$n=1$

O (M (1) \log m

$O(M(1)\log m$

A^{m}

$A^m$

— PKG

@Shitikanth patrz ccrwest.org/gordon/jalg.pdf, aby uzyskać informacje na temat algorytmów szybkiego potęgowania. Zasadniczo nie jest możliwe użycie mniejszej niż wielokrotność

\log m

$\log m$

— Joe

Jak zostało powiedziane, nie było to jasne w twoim pytaniu.

— PKG