imported>Crazy1880: dafür kein HTML (ID 11)

2019-04-02T06:55:32Z

dafür kein HTML (ID 11)

Neue Seite

'''Matrix-Kettenmultiplikation''' bezeichnet die [[Matrizenmultiplikation|Multiplikation]] von mehreren [[Matrix (Mathematik)|Matrizen]]. Da die Matrizenmultiplikation [[Assoziativgesetz|assoziativ]] ist, kann man dabei beliebig klammern. Dadurch wächst die Anzahl der möglichen Berechnungswege überpolynomial mit der Länge der Matrizenkette an. Mit der Methode der [[Dynamische Programmierung|dynamischen Programmierung]] kann die Klammerung der Matrix-Kette optimiert werden, so dass die Gesamtanzahl arithmetischer Operationen minimiert wird. Der Algorithmus hat eine Laufzeit von [[Landau-Symbole|<math>O</math>]]<math>(n^3)</math>.

Die Anzahl der möglichen Klammerungen für <math>n</math> Matrizen lässt sich mit der [[Catalan-Zahl]] C<sub>n-1</sub> bestimmen.

Beispiel: Sei <math>A</math> eine 10×30 Matrix, <math>B</math> eine 30×5 Matrix und <math>C</math> eine 5×60 Matrix. Dann gibt es zwei verschiedene Arten, das Matrizenprodukt <math>ABC</math> zu klammern:

:<math>(AB)C</math>
:<math>A(BC)</math>

Die Anzahl der grundlegenden Operationen berechnet sich wie folgt:

:<math>(AB)C \rightarrow (10\cdot 30\cdot 5) + (10\cdot 5\cdot 60) = 1500 + 3000 = 4500</math>
:<math>A(BC) \rightarrow (30\cdot 5\cdot 60) + (10\cdot 30\cdot 60) = 9000 + 18000 = 27000</math>

== Algorithmus ==
Der Algorithmus berechnet mittels dynamischer Programmierung eine Ergebnis-Matrix. Bei einer Kette <math>A_0A_1A_2\ldots A_{n-1}</math> von <math>n</math> Matrizen ist die Eingabe des Algorithmus die Sequenz <math>s</math> der Dimensionspaare <math>s = [ ( \mathit{firstdim}(A_i), \mathit{seconddim}(A_i) ) | 0 \le i < n]</math>, wobei die Funktion firstdim bzw. seconddim angewendet auf eine <math>m\times n</math>-Matrix <math>m</math> bzw. <math>n</math> zurückgibt.

<math>s[0..2]</math> bezeichnet die Teilsequenz von s, die die ersten beiden Dimensionspaare enthält. Also ist <math>s[0..\mathit{length}(s)] = s</math>.

Der Algorithmus wird durch eine Matrix-Rekurrenz spezifiziert.

;Initialisierung
<math>M[i,i+2] = \mathit{firstdim}(i)\cdot \mathit{seconddim}(i+1)\cdot \mathit{firstdim}(i+1),~0\le i<\mathit{length}(s)-1</math>

Für alle zwei Matrizen lange Ketten gibt es nur eine Möglichkeit der Klammerung.

;Rekursion
<math>M[i,j]=\min_{i<k<j} \big\{ M[i,k] + M[k+1,j] + \mathit{firstdim}(i)\cdot \mathit{seconddim}(j-1)\cdot \mathit{firstdim}(k) \big\}</math>,

wobei <math>i+2<j, 0\le i\le \mathit{length}(s), 0\le j\le \mathit{length}(s)</math>.

In der Zelle <math>M[i,j]</math> steht die minimale Anzahl von grundlegenden arithmetischen Operationen, um die Teilsequenz <math>s[i..j]</math> der Matrizenkette zu multiplizieren. Also ist die minimale Anzahl der Operationen bei der Multiplikation der gesamten Kette in der Zelle <math>M[0, \mathit{length}(s)]</math> gespeichert.

Um die optimale Klammerung zu konstruieren, die zu dem optimalen Ergebnis in <math>M[0, \mathit{length}(s)]</math> geführt hat, muss der Pfad in der DP-Matrix <math>M</math> mittels [[Backtracking]] von <math>M[0, \mathit{length}(s)]</math> aus zurückverfolgt werden.

== Effizienz ==
Die Länge der Eingabesequenz wird mit <math>n</math> bezeichnet. Der Algorithmus benötigt zum Speichern der Zwischenergebnisse für alle Teilsequenzen eine quadratische <math>n\times n</math>-Matrix. Also liegt der Speicherbedarf in <math>O(n^2)</math>.

Für jede Zelle muss über <math>O(n)</math> Aufteilungen optimiert werden. Also ist die Gesamtlaufzeit in <math>O(n^3)</math>

== Varianten ==
Der Optimierungsalgorithmus ist für beliebige Sequenzen von Objekten verwendbar, welche durch eine assoziative Operation verkettet sind, wenn eine Kostenfunktion für die Ausführung der Operation existiert.

Durch eine einfache Modifikation der Rekurrenz kann die Anzahl der Klammerungen in <math>O(n^3)</math> berechnet werden.

== Abgrenzung ==
Cormen, 2001 (S. 369), verweist auf einen Algorithmus von Hu und Shing<ref>[http://i.stanford.edu/pub/cstr/reports/cs/tr/81/875/CS-TR-81-875.pdf Hu Shing, Computation of Matrix Chain Products, Part I, Part II. 1980, Report.]</ref> zur Optimierung der Klammerung bei der Matrix-Kettenmultiplikation, der eine Laufzeit von <math>O(n\log n)</math> hat.

== Literatur ==
* {{BibISBN|0262032937|Seite=331–338}}
* {{Literatur |Autor=T. C. Hu, M. T. Shing |Titel=Computation of Matrix Chain Products. Part I |Sammelwerk=SIAM Journal on Computing |Band=11 |Nummer=2 |Datum=1982 |Seiten=362–373 |DOI=10.1137/0211028}}

== Quellen ==
<references />

[[Kategorie:Dynamische Programmierung]]

Matrix-Kettenmultiplikation - Versionsgeschichte

imported>Crazy1880: dafür kein HTML (ID 11)