Aufgaben Lösung

Aus ProgrammingWiki
< AuK < Teile und Herrsche 2 SS10
Archivierte Version vom 2010-04-18T15:52:45+00:00. Aktuelle Version

Diese Seite hält die Lösungen der Aufgaben auf der Seite AuK/Teile und Herrsche 2 SS10/Aufgaben bereit.

Lösungen zu den Übungsaufgaben

Multiplikation großer ganzer Zahlen nach KARATSUBA und OFMAN

Schnelle Matrixmultiplikation nach STRASSEN

Gegeben sind die zwei Matrizen A und B mit:

A=\begin{pmatrix} 3 & 4 & 8 & 9\\ 1 & 5 & 9 & 2\\ 5 & 7 & 4 & 3\\ 2 & 3 & 8 & 1 \end{pmatrix} und

B=\begin{pmatrix} 3 & 2 & 8 & 6\\ 1 & 4 & 9 & 5\\ 7 & 6 & 4 & 3\\ 2 & 9 & 2 & 3 \end{pmatrix}

Die Matrizen zerlegt man nach folgendem Muster in Teilmatrizen:


C=A\cdot B= \begin{pmatrix} A_{1,1} & A_{1,2}\\ A_{2,1} & A_{2,2} \end{pmatrix}\cdot \begin{pmatrix} B_{1,1} & B_{1,2}\\ B_{2,1} & B_{2,2} \end{pmatrix} =\begin{pmatrix} C_{1,1} & C_{1,2}\\ C_{2,1} & C_{2,2} \end{pmatrix}

Daraus ergeben sich die 8 Teilmatrizen:

A_{1,1}=\begin{bmatrix}3 & 4\\1 & 5\end{bmatrix}\text{, } A_{1,2}=\begin{bmatrix}8 & 7\\9 & 2\end{bmatrix}\text{, } A_{2,1}=\begin{bmatrix}5 & 7\\2 & 3\end{bmatrix}\text{, } A_{2,2}=\begin{bmatrix}4 & 3\\8 & 1\end{bmatrix}\\ B_{1,1}=\begin{bmatrix}3 & 2\\1 & 4\end{bmatrix}\text{, } B_{1,2}=\begin{bmatrix}8 & 6\\9 & 5\end{bmatrix}\text{, } B_{2,1}=\begin{bmatrix}7 & 6\\2 & 9\end{bmatrix}\text{, } B_{2,2}=\begin{bmatrix}4 & 3\\2 & 3\end{bmatrix}

Damit lassen sich M_{1} bis M_{7} berechnen:

M_{1}=(A_{1,2}+A_{2,2})\cdot(B_{2,1}+B_{2,2})=\begin{pmatrix}3 & 5\\1 & -1\end{pmatrix}\cdot\begin{pmatrix}-1 & -2\\4 & -1\end{pmatrix}=\begin{pmatrix}17 & -11\\-5 & -1\end{pmatrix}\\ M_{2}=(A_{1,1}-A_{2,2})\cdot(B_{1,1}-B_{2,2})=\begin{pmatrix}-3 & 6\\-1 & -3\end{pmatrix}\cdot\begin{pmatrix}-2 & -4\\-2 & -3\end{pmatrix}=\begin{pmatrix}-6 & -6\\8 & 13\end{pmatrix}\\ M_{3}=(A_{1,1}-A_{2,1})\cdot(B_{1,1}-B_{1,2})=\begin{pmatrix}-1 & 5\\-1 & -4\end{pmatrix}\cdot\begin{pmatrix}-1 & -1\\1 & -8\end{pmatrix}=\begin{pmatrix}6 & -39\\-3 & 33\end{pmatrix}\\ M_{4}=(A_{1,1}-A_{1,2})\cdot B_{2,2}=\begin{pmatrix}-6 & 1\\-2 & -2\end{pmatrix}\cdot B_{2,2}=\begin{pmatrix}-43 & -44\\-26 & -24\end{pmatrix}\\ M_{5}=A_{1,1}\cdot(B_{1,2}-B_{2,2})=A_{1,1}\cdot\begin{pmatrix}-1 & -3\\-3 & 5\end{pmatrix}=\begin{pmatrix}-27 & 31\\-12 & -8\end{pmatrix}\\ M_{6}=A_{2,2}\cdot(B_{2,1}-B_{1,2})=A_{2,2}\cdot\begin{pmatrix}0 & 1\\7 & -6\end{pmatrix}=\begin{pmatrix}14 & -6\\35 & -23\end{pmatrix}\\ M_{7}=(A_{2,1}-A_{2,2})\cdot B_{1,1}=\begin{pmatrix}-2 & 1\\0 & 1\end{pmatrix}\cdot B_{1,1}=\begin{pmatrix}-9 & -7\\3 & 1\end{pmatrix}

Danach kann man die 4 Teilmatrizen von C durch Addition bzw. Subtraktion berechnen.

C_{1,1}=M_1 + M_2 - M_4 + M_6=\begin{pmatrix}17 & -11\\-5 & -1\end{pmatrix}+\begin{pmatrix}-6 & -6\\8 & 13\end{pmatrix}-\begin{pmatrix}-43 & -44\\-26 & -24\end{pmatrix}+\begin{pmatrix}14 & -6\\35 & -23\end{pmatrix}=\begin{pmatrix}68 & 21\\64 & 13\end{pmatrix}\\ C_{1,2}=M_4 + M_5=\begin{pmatrix}-43 & -44\\-26 & -24\end{pmatrix}+\begin{pmatrix}-27 & 31\\-12 & -8\end{pmatrix}=\begin{pmatrix}-70 & -13\\-38 & -32\end{pmatrix}\\ C_{2,1}=M_6 + M_7=\begin{pmatrix}14 & -6\\35 & -23\end{pmatrix}+\begin{pmatrix}-9 & -7\\3 & 1\end{pmatrix}=\begin{pmatrix}5 & -13\\38 & -22\end{pmatrix}\\ C_{2,2}=M_2 - M_3 + M_5 - M_7=\begin{pmatrix}-6 & -6\\8 & 13\end{pmatrix}-\begin{pmatrix}6 & -39\\-3 & 33\end{pmatrix}+\begin{pmatrix}-27 & 31\\-12 & -8\end{pmatrix}-\begin{pmatrix}-9 & -7\\3 & 1\end{pmatrix}=\begin{pmatrix}-30 & 71\\-4 & -29\end{pmatrix}

Durch Zusammensetzen der Teilmatrizen zur Ergebnismatrix C ergibt sich das Ergebnis der Rechnung:

C=\begin{pmatrix}C_{1,1} & C_{1,2}\\C_{2,1} & C_{2,2}\end{pmatrix}= \begin{pmatrix} 68 & 21 & -70 & -13\\ 64 & 13 & -38 & -32\\ 5 & -13 & -30 & 71\\ 38 & -22 & -4 & -29 \end{pmatrix}