Multiplikation und Exponentiation der Matrixkette

Wenn ich zwei Matrizen und mit den Dimensionen bzw. und berechnen möchte , ist es effizienter, den Ausdruck zuerst als und nur dann umzuschreiben numerisch auswerten, da Dimension , jedoch die Dimension . $A$ $B$ $1000\times2$ $2\times1000$ $(AB)^{5000}$ $A(BA)^{4999}B$ $AB$ $1000\times1000$ $BA$ $2\times2$

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

... 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 , wobei nicht unbedingt die Identitätsmatrix ist. Mein Algorithmus berücksichtigt jedoch nicht die Möglichkeit, die Exponentiation durch Quadrieren des Algorithmus mit ungleich der Identitätsmatrix zu verwenden. $K A^n$ $A^n K$ $K$ $K$

optimization dynamic-programming linear-algebra 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

Ausdrucks

noch

ist, ihn als

. Der Punkt ist, dass Sie wahrscheinlich zwischen Matrixkettenmultiplikation und anderen Standardalgorithmen für eine schnelle Exponentiation mischen müssen.

A (B A)^{4999} B

$A(BA)^{4999}B$

A (B A)^{2 * (2 * 1249 + 1) + 1} B

$A(BA)^{2*(2*1249+1)+1}B$

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

und so weiter?

A (B A)^{n - 1} B

$A(BA)^{n-1}B$

A B (A B)^{n - 2} A B

$AB(AB)^{n-2}AB$

A B A (B A)^{n - 3} B A B

$ABA(BA)^{n-3}BAB$

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

addieren müssen . Mit anderen Worten, es ist nicht immer so, dass jeder Vektor als lineare Kombination von Eigenvektoren ausgedrückt werden kann.

n \times n

$n \times n$

n

$n$

Pyon

Antworten:

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 optimal lösen, da sich dies zu ausdehnt . Durch erneutes Verketten von 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)^2$ $ABCABC$ $ABC$

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

Zusammenfassend:
1) Der erste Schritt beim Lösen von besteht darin, zu lösen . 2) Das Lösen von wird am besten als Beispiel für das Problem der Matrixkettenmultiplikation betrachtet. 3) Wenn wir die n-Tupel-Ordnung aus der Lösung in (2) verwenden, erhalten wir die Lösung zu (1) als etwas Aroma von $(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$ (beachten Sie, dass auch alle anderen Gruppierungen aus Lösung (2) angewendet werden sollten). $A_1 \cdot A_2 \cdot G^{m-1} \cdot A_n$

Informeller Beweis In
Anbetracht des einfachsten Falls unter Verwendung von zwei Matrizen wir fest, dass und die Dimension bzw. haben. Jedes Produkt, das und hat eine der folgenden Abmessungen: $(AB)^n$ $A$ $B$ $X \times Y$ $Y \times X$ $A$ $B$

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

Wir haben entweder oder . $X < Y$ $Y ≤ X$

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

Annahme , 1b): hat die Dimension . Dies ist die optimale Anordnung für alle Produkte die und . Somit wird die Lösung optimal als . $Y ≤ X$
$BA$ $Y \times Y$ $A$ $B$ $A(BA)^{n-1}B$

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

(A B C)^{2}

$(ABC)^2$

A B C A B C

$ABCABC$

(A B C)^{n}

$(ABC)^n$

(A B C)^{n}

$(ABC)^n$

A (B C A)^{n - 1} B C

$A(BCA)^{n-1}BC$

A B (C A B)^{n - 1} C

$AB(CAB)^{n-1}C$

@ 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

A B C A B C

$ABCABC$

-1

$A_1$ $A_n$ $A_i$ $A_j$ $O (n^3)$

gnasher729
quelle

Dies berücksichtigt keine Unterausdrücke, die zu einer Potenz erhoben werden (wenn die Potenz groß ist, kann dies sehr ineffizient sein), und es berücksichtigt nicht die Möglichkeit, eine schnelle Potenzierung zu verwenden, um bessere Beschleunigungen zu erzielen , daher vermute ich dies ist noch keine optimale Antwort.