Multiplikation nach Strassen

24.01.2009, 17:10	tigerbine	Auf diesen Beitrag antworten »
Multiplikation nach Strassen Ich bin so frech und hänge den Text als PDF an. Es geht mir darum Aufgabe b) zu verstehen. Mir liegt auch eine Lösung vor, die ich aber nicht nachvollziehen kann. Knackpunkt ist die Formulierung: "die totale Anzahl von Additionen und Multiplikationen reeller Zahlen". Sei nun k=1, so sind nach Definition die Blockmatrizen von der Abmessung 2x2. Diese werden nun addiert und mulipliziert, dabei gehe ich davon aus, dass die Klammern zu erst zu berechnen sind. Setzt man k=1 in die Formel ein, so erhält man 25. Nun müssen die Matrizen Q ersteinmal bestimmt werden. Die Addition zweier 2x2 MAtrizen benötigt imho 4 Additionen von reellen Zahlen. Die Multiplikation zweier 2x2 Matrizen benötigt dann 4 Additionen und 8 Multiplikationen von reellen Zahlen. Damit brauche ich zur Berechnung von Q1 schon: 2 Matrixadditionen und 1 Matrixprodukt = 8 Additionen + 4 Additonen + 8 Multiplikationen =20 Rechenoperationen. Es müssen noch 6 weitere Matrizen berechnet werden. Und man liegt offensichtlich über den behaupteten 25 Operationen. Über eine Stellungnahme würde ich mich freuen. edit: Imho muss es sich um einen Fehler in der Aufgabenstellung handeln, denn die 25 Operationen erhält man für die Multiplikation zweier 2x2 Matrizen nach Strassen. So wie die Formel aber angeben ist, müßte man für k=1 zwei 4x4 Matrizen multiplizieren. Ein Beispiel findet sich hier
25.01.2009, 13:25	Reksilat	Auf diesen Beitrag antworten »
RE: Multiplikation nach Strassen Hi tigerbine, Der Aufwand für die Multiplikation zweier $\begin{eqnarray} 2^k\times 2^k \end{eqnarray}$ -Matrizen ist: $\begin{eqnarray} S(2^k)=7\cdot (2^k)^{{\rm log}_2(7)}-6\cdot (2^k)^2=7^{k+1}-6\cdot (2^k)^2 \end{eqnarray}$ Und das stimmt auch für $\begin{eqnarray} k=1 \end{eqnarray}$ , denn $\begin{eqnarray} 7^2-6\cdot 4=25 \end{eqnarray}$ Zu Beginn hat mich die die erste Zeile etwas verunsichert, aber wenn Du dort $\begin{eqnarray} A_{ij},B_{ij}\in \mathbb{R}^{2^{k-1}\times 2^{k-1}} \end{eqnarray}$ , mit $\begin{eqnarray} k=1,2,\ldots \end{eqnarray}$ schreibst, sollte alles passen. Gruß, Reksilat.
25.01.2009, 14:13	tigerbine	Auf diesen Beitrag antworten »
RE: Multiplikation nach Strassen Danke für die Bestätigung! In der Nacht ist mir der Induktionsbeweis geglückt, aber wir kommen beide zu dem Urteil, dass dort (k-1) im Exponenten in der Angabe stehen sollte. Super, dann kann ich mich dem nächsten Problem widmen!

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »