Multiplikation und Exponentiation der Matrixkette

13

Wenn ich zwei Matrizen und B mit den Dimensionen 1000 × 2 bzw. 2 × 1000 habe und ( A B ) 5000 berechnen möchte , ist es effizienter, den Ausdruck zuerst als A ( B A ) 4999 B und nur dann umzuschreiben numerisch auswerten, da A B die Dimension 1000 × 1000 hat , B A jedoch die Dimension 2 × 2 hat .AB1000×22×1000(AB)5000A(BA)4999BAB1000×1000BA2×2

Ich möchte eine verallgemeinerte Version dieses Problems lösen. Gibt es einen einigermaßen effizienten Algorithmus (keine Brute Force), um einen Ausdruck zu optimieren, der Folgendes enthält:

  • Freie Matrixvariablen bekannter Dimensionen
  • Produkte beliebiger Unterausdrücke
  • Willkürliche Unterausdrücke, die zur natürlichen Macht erhoben werden

... damit die numerische Auswertung nach dem Ersetzen der freien Matrixvariablen durch konkrete Matrixwerte den geringsten Arbeitsaufwand erfordert?

Das Matrix - Kette Multiplikation Problem ist ein Spezialfall meines Problems.


Bearbeiten:

Dies ist eine vorläufige Antwort. Es scheint mir intuitiv richtig zu sein, aber ich habe keinen Beweis dafür, dass es richtig ist. Wenn es sich als richtig herausstellt, interessiert mich der Beweis immer noch. (Wenn es natürlich nicht korrekt ist, korrigieren Sie mich bitte.)

Berücksichtigen Sie für jedes Produkt, das zu einer Potenz erhoben wird, beispielsweise , jede zyklische Permutation der Faktoren:(A1A2Ak)n

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

... rekursiv. Jede Potenz ist unter Verwendung der Exponentiation durch Quadrieren (offensichtlich) zu berechnen, und alle anderen Produkte sind unter Verwendung der vom Matrixkettenmultiplikationsalgorithmus zurückgegebenen optimalen Reihenfolge zu berechnen.


Bearbeiten:

Die in meiner vorherigen Bearbeitung skizzierte Idee ist immer noch etwas nicht optimal. Die Potenzierung durch Quadrierungsalgorithmus wertet tatsächlich Ausdrücke der Form oder A n K aus , wobei K nicht unbedingt die Identitätsmatrix ist. Mein Algorithmus berücksichtigt jedoch nicht die Möglichkeit, die Exponentiation durch Quadrieren des Algorithmus mit K ungleich der Identitätsmatrix zu verwenden.KAnAnKKK

pyon
quelle
@ gnasher729: Entschuldigung, ich hätte expliziter sein sollen. Ich möchte nicht alle Möglichkeiten brutal erzwingen, aus genau dem gleichen Grund möchten Sie die Multiplikation der Matrixkette nicht durch rohe Gewalt lösen. Ich habe die Frage gerade entsprechend bearbeitet.
Pyon
Beachten Sie, dass es auch nach dem cleveren Faktorisieren des Ausdrucks noch klüger ist, ihn als A ( B A ) 2 ( 2 1249 + 1 ) + 1 B zu faktorisieren . Der Punkt ist, dass Sie wahrscheinlich zwischen Matrixkettenmultiplikation und anderen Standardalgorithmen für eine schnelle Exponentiation mischen müssen. A(BA)4999B
A(BA)2(21249+1)+1B
Apiwat Chantawibul
@ Billiska: Genau das möchte ich tun: Kombinieren Sie die Multiplikation und Exponentiation der Matrixkette, indem Sie sie zu einem einzigen Algorithmus für das kombinierte Problem quadrieren. Aber es gibt einige lästige Probleme. Gegeben , wie verhindere ich den Algorithmus von weiterem Versuch A B ( A B ) n - 2 A B , A B A ( B A ) n - 3 B A B und so weiter? A(BA)n1BAB(AB)n2ABABA(BA)n3BAB
pyon
Wir ändern die Basis für die Matrixexponentiation in den Eigenvektor. Wenn alle Matrizen die Potenz 1 haben, können wir die Matrixkettenmultiplikation verwenden.
Deep Joshi
@ DeepJoshi Sorry, ich finde deinen Kommentar eher knapp. Aber wenn ich Ihre Idee richtig verstehe, wird sie im allgemeinen Fall leider nicht funktionieren, da die Dimensionen der Eigenräume einer Matrix nicht zu n addieren müssen . Mit anderen Worten, es ist nicht immer so, dass jeder Vektor als lineare Kombination von Eigenvektoren ausgedrückt werden kann. n×nn
Pyon

Antworten:

3

Haftungsausschluss: Die folgende Methode hat sich nicht konsequent als optimal erwiesen. Ein informeller Nachweis wird erbracht.

Das Problem besteht darin, die effizienteste Bestellung zu finden, wenn das Quadrat des Produkts berücksichtigt wird.

Wenn wir zum Beispiel , müssen wir nur ( A B C ) 2 optimal lösen, da sich dies zu A B C A B C ausdehnt . Durch erneutes Verketten von A B C werden keine nützlichen Bestellinformationen hinzugefügt . Die Intuition hier ist, dass höhere Ordnungen, die aus mehr Elementen bestehen, die dieselben Matrizen verwenden, irrelevant sind, da das Problem der optimalen Ordnung von unten nach oben gelöst werden kann.(ABC)50(ABC)2ABCABCABC

Das Finden der besten Reihenfolge von reduziert sich auf das Problem der Matrixkettenmultiplikation. Wenden Sie nach dem Finden einer optimalen Reihenfolge eine Exponentiation auf das Triplett (im Allgemeinen n-Tupel) in der Reihenfolge an.ABCABC

Wenn die optimale Reihenfolge für das Quadrat wird als Beispiel , die Lösung für das ursprüngliche Problem ist A ( B ( C A ) ) 49 B C .A(B(CA))BCA(B(CA))49BC

Zusammenfassend:
1) Der erste Schritt beim Lösen von besteht darin, ( A 1 A 2A n ) 2 zu lösen . 2) Das Lösen von ( A 1 A 2A n ) 2 wird am besten als Beispiel für das Problem der Matrixkettenmultiplikation betrachtet. 3) Wenn wir die n-Tupel-Ordnung G aus der Lösung in (2) verwenden, erhalten wir die Lösung zu (1) als etwas Aroma von A 1A.(A1A2An)m(A1A2An)2
(A1A2An)2
G (beachten Sie, dass auch alle anderen Gruppierungen aus Lösung (2) angewendet werden sollten).A1A2Gm1An

Informeller Beweis In
Anbetracht des einfachsten Falls unter Verwendung von zwei Matrizen wir fest, dass A und B die Dimension X × Y bzw. Y × X haben. Jedes Produkt, das A und B verwendet, hat eine der folgenden Abmessungen:(AB)nABX×YY×XAB

Y × X Y × Y X × X.X×Y
Y×X
Y×Y
X×X

Wir haben entweder oder Y X .X<YYX

Annahme 1a): A B hat die Dimension X × X , und diese Reihenfolge ist bei einem Bottom-up-Ansatz garantiert optimal. Jede andere Konfiguration von A und B ist entweder gleich gut oder schlechter. Somit ist das Problem als ( A B ) n optimal gelöst .X<Y
ABX×XAB(AB)n

Annahme , 1b): B A hat die Dimension Y × Y . Dies ist die optimale Anordnung für alle Produkte die A und B . Somit wird die Lösung optimal als A ( B A ) n - 1 B gefunden .YX
BAY×YABA(BA)n1B

Damit ist der Beweis abgeschlossen, und wir haben uns nur die beiden Ordnungen angesehen, die in , dem quadratischen Problem, zu finden sind.ABAB

Bei Verwendung von mehr Matrizen ist das Argument ähnlich. Vielleicht ist ein induktiver Beweis möglich? Die allgemeine Idee ist, dass das Lösen des MCM für das Quadrat die optimale Größe für die Operationen unter Berücksichtigung aller beteiligten Matrizen findet.

Fallstudie:

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)
Matteyas
quelle
1
(ABC)2
ABCABC(ABC)n(ABC)nA(BCA)n1BCAB(CAB)n1C
@ DavidRicherby ist der zusätzliche informelle Beweis für jede Verwendung?
Mattyas
@matteyas: Das habe ich mehr oder weniger in der ersten Bearbeitung meiner Frage gesagt, oder?
Pyon
ABCABC