Mnożenie łańcucha macierzy i potęgowanie


13

Jeśli mam dwie macierze i , odpowiednio o wymiarach i , i chcę obliczyć , bardziej wydajne jest najpierw przepisanie wyrażenia jako i dopiero wtedy oceniaj liczbowo, ponieważ ma wymiar ale ma wymiar .B 1000 × 2 2 × 1000 ( A B ) 5000 A ( B A ) 4999 B A B 1000 × 1000 B A 2 × 2AB1000×22×1000(AB)5000A(BA)4999BAB1000×1000BA2×2

Chcę rozwiązać uogólnioną wersję tego problemu. Czy istnieje dość wydajny algorytm (nie brutalna siła) do optymalizacji wyrażenia zawierającego:

  • Dowolne zmienne macierzowe o znanych wymiarach
  • Produkty dowolnych podwyrażeń
  • Arbitralne podwyrażenia podniesione do naturalnej mocy

... aby oszacowanie numeryczne wymagało najmniejszej ilości pracy, po zastąpieniu zmiennych zmiennych macierzy konkretnymi wartościami macierzy?

Łańcuch mnożenie macierzy problemem jest to szczególny przypadek mojego problemu.


Edytować:

To jest wstępna odpowiedź. Wydaje mi się intuicyjnie słuszne, ale nie mam dowodu, że jest to poprawne. Jeśli okaże się to prawidłowe, wciąż jestem zainteresowany dowodem. (Jeśli to nie jest poprawne, proszę, popraw mnie.)

Dla każdego produktu podniesionego do potęgi, powiedzmy, , rozważ każdą cykliczną permutację czynników:(A1A2Ak)n

  • (A1A2Ak)n
  • A1(A2AkA1)n1A2Ak
  • A1A2(A3AkA1A2)n1A3Ak
  • ...
  • A1A2Ak1(AkA1A2Ak1)n1Ak

... rekurencyjnie. Każdą moc oblicza się za pomocą potęgowania przez podniesienie do kwadratu (oczywiście), a wszystkie inne produkty należy obliczać przy użyciu optymalnej kolejności zwracanej przez algorytm mnożenia łańcucha macierzy.


Edytować:

Pomysł nakreślony w mojej poprzedniej edycji jest nadal nieco nieoptymalny. Potęgowanie przez algorytm kwadratu faktycznie ocenia wyrażenia postaci lub , gdzie niekoniecznie jest macierzą tożsamości. Ale mój algorytm nie bierze pod uwagę możliwości zastosowania potęgowania przez kwadrat algorytmu z nie równym macierzy tożsamości.A n K K KKAnAnKKK


@ gnasher729: Przepraszam, powinienem był wyrazić bardziej otwarcie. Nie chcę brutalnej siły wszystkich możliwości, z dokładnie tego samego powodu, dla którego nie chciałbyś rozwiązać mnożenia łańcucha macierzy przez brutalną siłę. Właśnie odpowiednio zredagowałem pytanie.
pyon

Należy pamiętać, że nawet po czynnikiem sprytnie pan wyrażenie jest jeszcze bardziej sprytny, aby czynnik go jako . Chodzi o to, że prawdopodobnie musisz wymieszać pomnożenie łańcucha macierzy z innym standardowym algorytmem dla szybkiego potęgowania. A ( B A ) 2 ( 2 1249 + 1 ) + 1 B.A(BA)4999B
A(BA)2(21249+1)+1B
Apiwat Chantawibul

@Billiska: Rzeczywiście, właśnie to chcę zrobić: połączyć mnożenie łańcucha macierzy i potęgowanie przez podniesienie kwadratu do jednego algorytmu dla połączonego problemu. Ale są pewne nieznośne problemy. Biorąc pod uwagę , w jaki sposób mam zapobiec dalszemu próbowaniu algorytmu , i tak dalej? A B ( A B ) n - 2 A B A B A ( B A ) n - 3 B A BA(BA)n1BAB(AB)n2ABABA(BA)n3BAB
pyon

Zmieniamy podstawę na wektor własny dla potęgowania macierzy, a gdy cała macierz ma moc 1, możemy użyć mnożenia łańcucha macierzy.
Deep Joshi,

@DeepJoshi Niestety, twój komentarz jest raczej zwięzły. Ale jeśli dobrze rozumiem twój pomysł, obawiam się, że nie zadziała w ogólnym przypadku, ponieważ wymiary przestrzeni własnych macierzy nie muszą się sumować do . Innymi słowy, nie zawsze jest tak, że każdy wektor można wyrazić jako liniową kombinację wektorów własnych. nn×nn
pyon

Odpowiedzi:


3

Oświadczenie: Następująca metoda nie została dokładnie udowodniona jako optymalna. Dostarczony jest nieformalny dowód.

Problem sprowadza się do znalezienia najbardziej efektywnego zamówienia, biorąc pod uwagę kwadrat produktu.

Na przykład, patrząc na np. , musimy tylko optymalnie rozwiązać ponieważ rozszerza się do . Żadne przydatne informacje dotyczące zamawiania nie są dodawane przez ponowne połączenie . Intuicja polega na tym, że ponieważ problem optymalnego uporządkowania można rozwiązać oddolnie, wyższe uporządkowania składające się z większej liczby elementów korzystających z tych samych macierzy są nieistotne. ( A B C ) 2 A B C A B C A B C(ABC)50(ABC)2ABCABCABC

Znalezienie najlepszej kolejności sprowadza się do problemu mnożenia łańcucha macierzy. Po znalezieniu optymalnego uporządkowania zastosuj potęgowanie do trypletu (ogólnie n-krotki) w uporządkowaniu.ABCABC

Na przykład, jeśli optymalnym uporządkowaniem kwadratu jest , rozwiązaniem początkowego problemu jest .A ( B ( C A ) ) 49 B CA(B(CA))BCA(B(CA))49BC

Podsumowując:
1) Pierwszym krokiem do rozwiązania jest rozwiązanie . 2) Rozwiązanie najlepiej jest podejść jako przykład problemu mnożenia łańcucha macierzy. 3) Użycie n-krotki zamawiając z rozwiązania w (2) da nam rozwiązanie (1) jako pewien smak (zauważ, że każdy inny należy również zastosować grupowanie z rozwiązania (2)). ( A 1 A 2A n ) 2 ( A 1 A 2A n ) 2 G A 1A 2G m - 1A n(A1A2An)m(A1A2An)2
(A1A2An)2
GA1A2Gm1An

Nieformalny dowód
Uwzględniając najprostszym przypadku przy pomocy dwóch matryc, , możemy zauważyć, że i mają wymiary wzdłuż i , odpowiednio. Każdy produkt wykorzystujący i ma jeden z następujących wymiarów: A B X × Y Y × X A B(AB)nABX×YY×XAB

Y × X Y × Y X × XX×Y
Y×X
Y×Y
X×X

Mamy albo lub .Y XX<YYX

Założenie 1a): ma wymiar , a to uporządkowanie gwarantuje optymalne podejście od dołu do góry. Każda inna konfiguracja i jest albo równie dobra, albo gorsza. Zatem problem został optymalnie rozwiązany jako .A B X × X A B ( A B ) nX<Y
ABX×XAB(AB)n

Założenie 1b): ma wymiar . Jest to optymalna zamawiania wszystkich produktów związanych z i . Tak więc, roztwór jest optymalnie znalezione .B A Y × Y A B A ( B A ) n - 1 BYX
BAY×YABA(BA)n1B

To kończy dowód i przyjrzeliśmy się tylko dwóm zamówieniom znalezionym w , problemie kwadratowym.ABAB

Przy użyciu większej liczby macierzy argument jest podobny. Być może możliwy jest dowód indukcyjny? Ogólna idea polega na tym, że rozwiązanie MCM dla kwadratu znajdzie optymalny rozmiar dla operacji z uwzględnieniem wszystkich zaangażowanych macierzy.

Studium przypadku:

julia> a=rand(1000,2);
julia> b=rand(2,1000);
julia> c=rand(1000,100);
julia> d=rand(100,1000);
julia> e=rand(1000,1000);

julia> @time (a*b*c*d*e)^30;
  0.395549 seconds (26 allocations: 77.058 MB, 1.58% gc time)

# Here I use an MCM solver to find out the optimal ordering for the square problem
julia> Using MatrixChainMultiply
julia> matrixchainmultiply("SOLVE_SQUARED", a,b,c,d,e,a,b,c,d,e)
Operation: SOLVE_SQUARED(A...) = begin  # none, line 1:
    A[1] * (((((A[2] * A[3]) * (A[4] * (A[5] * A[6]))) * (A[7] * A[8])) * A[9]) * A[10])
  end
Cost: 6800800

# Use the ordering found, note that exponentiation is applied to the group of 5 elements
julia> @time a*(((((b*c)*(d*(e*a)))^29*(b*c))*d)*e);
  0.009990 seconds (21 allocations: 7.684 MB)

# I also tried using the MCM for solving the problem directly
julia> @time matrixchainmultiply([30 instances of a,b,c,d,e]);
  0.094490 seconds (4.02 k allocations: 9.073 MB)

1
Czy możesz uzasadnić twierdzenie, że wystarczy rozważyć ? Nie wydaje mi się to oczywiste. (ABC)2
David Richerby

@DavidRicherby Nie mam na to żadnych dowodów, ale wydaje się to intuicyjne, ponieważ problem ma charakter cykliczny, a każde unikalne uporządkowanie cykliczne występuje w i żadne dalsze warunki nie stanowią żadnej nowej grupy cyklicznej. My hipotezą jest to, że jest optymalnie obliczono jako jedno z następujących: , lub . Spróbuję to udowodnić jutro, jeśli będzie czasu. ( A B C ) n ( A B C ) n A ( B C A ) n - 1 B C A B ( C A B ) n - 1 CABCABC(ABC)n(ZAbdo)nZA(bdoZA)n-1bdoZAb(doZAb)n-1do
matteyas

@DavidRicherby jest dodanym nieformalnym dowodem jakiegokolwiek zastosowania?
matteyas

@matteyas: To mniej więcej to, co powiedziałem w pierwszej edycji mojego pytania, prawda?
pyon

@ matteyas OK, więc myślę, że chodzi o to, że ponieważ mamy powtarzającą się sekwencję, istnieje tylko stała liczba rozmiarów macierzy pośrednich i widziałeś je wszystkie, zanim spojrzałeś na . ZAbdoZAbdo
David Richerby

-1

Jeśli chcesz obliczyć iloczyn n macierzy od do w jak najlepszym czasie, możesz łatwo obliczyć, ile operacji jest potrzebnych do obliczenia iloczynu do dla wszystkich 1 ≤ i ≤ j ≤ n w kroki.A n A i A j O ( n 3 )ZA1ZAnZAjaZAjotO(n3))


3
Nie uwzględnia to podwyrażeń podniesionych do potęgi (jeśli moc jest duża, może to być bardzo nieefektywne) i nie uwzględnia możliwości użycia szybkiego potęgowania w celu uzyskania lepszych przyspieszeń , więc podejrzewam, że to nie jest jeszcze optymalną odpowiedzią.
DW
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.