Czy istnieją algorytmy potęgowania równoległego macierzy, które są bardziej wydajne niż mnożenie sekwencyjne?

Wymagane jest znalezienie mocy (dodatniej liczby całkowitej) macierzy liczb rzeczywistych. Istnieje wiele wydajnych algorytmów mnożenia macierzy (np. Niektóre algorytmy równoległe to Cannon, DNS ), ale czy istnieją algorytmy, które są przeznaczone właśnie do znalezienia mocy macierzy i które są bardziej wydajne niż sekwencyjne wykonywanie mnożenia macierzy? Szczególnie interesują mnie algorytmy równoległe.

— Do Pana
źródło

Czego próbowałeś? Gdzie utknąłeś? Jakie badania przeprowadziłeś? Gdzie jest pytanie oprócz tytułu? W przypadku wersji decyzyjnej twojego problemu (od tytułu) odpowiedź brzmi „tak”, ale już o tym wiesz, prawda?

— Zło

@TomR To pytanie prawdopodobnie Cię interesuje

— adrianN

Może coś takiego ? A może szukasz czegoś innego? Jakie są rozmiary i moce w twojej aplikacji?

— Zło

Możesz obliczyć n-tą moc z mniejszą niż n-1 mnożeniem, gdy n ≥ 4. W przypadku dużych macierzy zwykle warto znaleźć najmniejszą możliwą liczbę mnożenia (na przykład istnieje prosta metoda obliczenia n ^ 15 za pomocą 6 mnożenia, ale można to zrobić za pomocą 5). Następnie możesz zastosować tę samą zasadę, aby znaleźć najmniejszą liczbę kolejnych zwielokrotnień, co będzie trudniejsze.

— gnasher729,

Powinieneś również wziąć pod uwagę ilość dostępnej równoległości. „Równoległość” polega na wykorzystaniu zasobów, które w innym przypadku byłyby nieużywane. Jeśli implementacja mnożenia macierzy może już efektywnie wykorzystywać wszystkie dostępne zasoby, to nie ma nic więcej do wykorzystania do obliczania mocy macierzy.

— gnasher729,

Odpowiedzi:

$M^{15}$

$M^2$

$M^3 = M^2 * M$ $M^4 = M^2 * M^2$

$M^7 = M^4 * M^3$ $M^8 = M^4 * M^4$

$M^{15} = M^8 * M^7$

$M^5$ $M^5$

$M^3$ $M^3$ $M^2$ $M^4$ $M^2$

$M^2 = M * M$ $M^3 = M^2 * M$ $M^2$ $M^3$ $M^2$ $M^3$ $M^4$

$M^{15}$ $M^{1000}$

$M^2$ $M^5$

$M^6$ $M^{25}$ $M^{25}$

$M^{108}$ $M^{125}$ $k (k+1)^2$

— gnasher729
źródło

Istnieją dwa poziomy, na których można analizować równoległe przyspieszenia z potęgowaniem macierzy: poziom „makro-algorytmiczny”, który decyduje, które macierze należy pomnożyć, oraz poziom „mikro-algorytmiczny”, na którym można przyspieszyć same multiplikacje z równoległością.

$n$ $n$ $O(\log^2(n))$ $O(n)$

(Uwaga: strona wikipedia służy do ogólnego obliczania macierzy. Nie jestem pewien, czy można to zrównoleglić jeszcze bardziej, korzystając z informacji, że kwadraty macierz).

$A^m$ $A$

$A^k$ $O(\log(k))$

Pytanie brzmi: czy możemy to pokonać równolegle? Twierdzę, że odpowiedź brzmi „nie”.

Prostym powodem jest to, że potęgowanie przez kwadrat jest zasadniczo dynamicznym algorytmem programowania; pozwala ominąć całą pracę poprzez ponowne użycie wyników cząstkowych, ale to z kolei tworzy zależność danych, która uniemożliwia równoległość. Jeśli pozbędziemy się zależności danych, ale znacznie zwiększymy ilość pracy, którą musimy wykonać.

$k$

{ZA}_{1} {ZA}_{2)} {ZA}_{3)} {ZA}_{4} {ZA}_{5} . . . {ZA}_{k}

$A_1 A_2 A_3 A_4 A_5 ... A_k$

$\frac{k}{2}$

({ZA}_{1} {ZA}_{2)}) ({ZA}_{3)} {ZA}_{4}) ({ZA}_{5} {ZA}_{6}) . . . ({ZA}_{k - 1} {ZA}_{k})

$(A_1 A_2)(A_3 A_4)(A_5 A_6) ... (A_{k-1}A_k)$

$k$ $O(\log(k))$

Gdybyśmy jednak wykonywali potęgowanie w ten sposób, wyglądałoby to tak:

(ZA ZA) (ZA ZA) (ZA ZA) . . . (ZA ZA)

$(A A)(A A)(A A)...(A A)$

$A^2$

$A^k$ $n$ $n$ $A$ $O(\log^2(n)\log(k))$ $O(n\log(k))$

— Kurt Mueller
źródło

$m$ $\log m$ $2$ $m$

ZA = S. Λ {S.}^{- 1} \to {ZA}^{m} = S. Λ^{m} {S.}^{- 1}

$A = S \Lambda S^{-1} \rightarrow A^m = S \Lambda^m S^{-1}$

m

$m$

O (1)

$O(1)$

m

$m$

— nbubis
źródło