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

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 × $A$$B$$1000\times2$$2\times1000$$(AB)^{5000}$$A(BA)^{4999}B$$AB$$1000\times1000$$BA$$2\times2$

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:$(A_1 A_2 \ldots A_k)^n$

• $(A_1 A_2 \ldots A_k)^n$
• $A_1 (A_2 \ldots A_k A_1)^{n-1} A_2 \ldots A_k$
• $A_1 A_2 (A_3 \ldots A_k A_1 A_2)^{n-1} A_3 \ldots A_k$
• ...
• $A_1 A_2 \ldots A_{k-1} (A_k A_1 A_2 \ldots A_{k-1})^{n-1} A_k$

... 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 $K A^n$$A^n K$$K$$K$

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 $(ABC)^{50}$$(ABC)^2$$ABCABC$$ABC$

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 $A(B(CA))BC$$A(B(CA))^{49}BC$

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 2 ⋯ A n ) 2 ( A 1 A 2 ⋯ A n ) 2 G A 1 ⋅ A 2 ⋅ G m - 1 ⋅ A $(A_1 A_2 \cdots A_n)^m$$(A_1 A_2 \cdots A_n)^2$
$(A_1 A_2 \cdots A_n)^2$
$G$$A_1 \cdot A_2 \cdot G^{m-1} \cdot A_n$

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 $(AB)^n$$A$$B$$X \times Y$$Y \times X$$A$$B$

Y × X Y × Y X × $X \times Y$
$Y \times X$
$Y \times Y$
$X \times X$

Mamy albo lub .Y ≤ $X < Y$$Y ≤ X$

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 ) $X < Y$
$AB$$X \times X$$A$$B$$(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$Y ≤ X$
$BA$$Y \times Y$$A$$B$$A(BA)^{n-1}B$

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)

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$A_1$$A_n$$A_i$$A_j$$O (n^3)$