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.

$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$

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$

$\frac{k}{2}$

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

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

$A^2$

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

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