diff options
| -rwxr-xr-x | buch/papers/multiplikation/einlteung.tex | 8 | ||||
| -rw-r--r-- | buch/papers/multiplikation/images/bigo.pdf | bin | 28372 -> 28312 bytes | |||
| -rw-r--r-- | buch/papers/multiplikation/images/bigo.tex | 1 | ||||
| -rw-r--r-- | buch/papers/multiplikation/images/meas_c.pdf | bin | 23943 -> 23887 bytes | |||
| -rw-r--r-- | buch/papers/multiplikation/images/meas_c.tex | 3 | ||||
| -rw-r--r-- | buch/papers/multiplikation/images/meas_python.pdf | bin | 22379 -> 22337 bytes | |||
| -rw-r--r-- | buch/papers/multiplikation/images/meas_python.tex | 3 | ||||
| -rw-r--r-- | buch/papers/multiplikation/images/strassen.pdf | bin | 19970 -> 20700 bytes | |||
| -rw-r--r-- | buch/papers/multiplikation/images/strassen.tex | 127 | ||||
| -rwxr-xr-x | buch/papers/multiplikation/loesungsmethoden.tex | 62 | ||||
| -rwxr-xr-x | buch/papers/multiplikation/main.tex | 4 | ||||
| -rwxr-xr-x | buch/papers/multiplikation/problemstellung.tex | 11 |
12 files changed, 156 insertions, 63 deletions
diff --git a/buch/papers/multiplikation/einlteung.tex b/buch/papers/multiplikation/einlteung.tex index fab23ef..2cfbe21 100755 --- a/buch/papers/multiplikation/einlteung.tex +++ b/buch/papers/multiplikation/einlteung.tex @@ -3,10 +3,10 @@ % % (c) 2020 Prof Dr Andreas Müller, Hochschule Rapperswil % -\section{Einleitung \label{multiplikation:section:einleitung}} -\rhead{Einleitung} +\section{Matrizenmultiplikation \label{multiplikation:section:einleitung}} +\rhead{Matrizenmultiplikation} -Die Multiplikation zweier Matrizen ist eine wichtige Operation die in verschiedensten Teilen der Mathematik Anwendung findet. +Die Multiplikation zweier Matrizen ist eine wichtige Operation, die in verschiedensten Teilen der Mathematik Anwendung findet. Die Beschreibung der Multiplikation aus der Definition 2.10: Eine $m\times n$-Matrix $\mathbf{A}\in M_{m\times n}(\Bbbk)$ und eine @@ -34,7 +34,7 @@ C_{11} & C_{12}\\ C_{21} & C_{22} \end{bmatrix} \end{equation} -explizt als Gleichung +explizt als Gleichungen \begin{equation} \label{multiplikation:eq:MM_exp} \begin{split} C_{11} &= A_{11} \cdot B_{11} + A_{12} \cdot B_{21}\\ diff --git a/buch/papers/multiplikation/images/bigo.pdf b/buch/papers/multiplikation/images/bigo.pdf Binary files differindex 8a53398..2519553 100644 --- a/buch/papers/multiplikation/images/bigo.pdf +++ b/buch/papers/multiplikation/images/bigo.pdf diff --git a/buch/papers/multiplikation/images/bigo.tex b/buch/papers/multiplikation/images/bigo.tex index 9ee3a68..63fd0fd 100644 --- a/buch/papers/multiplikation/images/bigo.tex +++ b/buch/papers/multiplikation/images/bigo.tex @@ -54,6 +54,7 @@ xticklabels=\empty, scale only axis=true, width=12cm, height=8cm, + legend cell align={left} ] \addplot [ domain= 1:5000, diff --git a/buch/papers/multiplikation/images/meas_c.pdf b/buch/papers/multiplikation/images/meas_c.pdf Binary files differindex 6e0e2cc..521151e 100644 --- a/buch/papers/multiplikation/images/meas_c.pdf +++ b/buch/papers/multiplikation/images/meas_c.pdf diff --git a/buch/papers/multiplikation/images/meas_c.tex b/buch/papers/multiplikation/images/meas_c.tex index a2a0505..12d3527 100644 --- a/buch/papers/multiplikation/images/meas_c.tex +++ b/buch/papers/multiplikation/images/meas_c.tex @@ -53,7 +53,8 @@ legend pos=north west, very thick, scale only axis=true, width=12cm, height=8cm, - log basis x={10} + log basis x={10}, + legend cell align={left} ] \addlegendentry{Winograd} \addplot[ color=blue, diff --git a/buch/papers/multiplikation/images/meas_python.pdf b/buch/papers/multiplikation/images/meas_python.pdf Binary files differindex 9d7730d..fe89773 100644 --- a/buch/papers/multiplikation/images/meas_python.pdf +++ b/buch/papers/multiplikation/images/meas_python.pdf diff --git a/buch/papers/multiplikation/images/meas_python.tex b/buch/papers/multiplikation/images/meas_python.tex index a30d342..ad43cf6 100644 --- a/buch/papers/multiplikation/images/meas_python.tex +++ b/buch/papers/multiplikation/images/meas_python.tex @@ -53,7 +53,8 @@ legend pos=north west, very thick, scale only axis=true, width=12cm, height=8cm, - log basis x={10} + log basis x={10}, + legend cell align={left} ] \addlegendentry{Winograd} \addplot[ color=blue, diff --git a/buch/papers/multiplikation/images/strassen.pdf b/buch/papers/multiplikation/images/strassen.pdf Binary files differindex a30fdaa..6d81ff5 100644 --- a/buch/papers/multiplikation/images/strassen.pdf +++ b/buch/papers/multiplikation/images/strassen.pdf diff --git a/buch/papers/multiplikation/images/strassen.tex b/buch/papers/multiplikation/images/strassen.tex index 5cf39b4..2e3b727 100644 --- a/buch/papers/multiplikation/images/strassen.tex +++ b/buch/papers/multiplikation/images/strassen.tex @@ -56,7 +56,7 @@ A_{11}B_{11} \& A_{12}B_{12} \& A_{21}B_{12} \& A_{22}B_{12} \\ A_{11}B_{22} \& A_{12}B_{22} \& A_{21}B_{22} \& A_{22}B_{22} \\ };} - + \foreach \j in {1,...,7} { \matrix(M\i\j)[matrix of math nodes,nodes in empty cells, @@ -80,7 +80,7 @@ \node at (-3,-15) {$C_{21}=$} ; \node at (-3,-10) {$C_{12}=$} ; \node at (-3,-5) {$C_{11}=$} ; - + \node at (5,-2) {P}; \node at (10,-2) {Q}; \node at (15,-2) {R}; @@ -100,41 +100,132 @@ \node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=green, fit=(X4-3-3)] {}; \node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=green, fit=(X4-4-4)] {}; +% P \node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=green, fit=(M11-4-1)] {}; \node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=green, fit=(M11-1-4)] {}; \node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=green, fit=(M11-4-4)] {}; \node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=green, fit=(M11-1-1)] {}; -\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=red, fit=(M14-1-4)] {}; -\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=green, fit=(M14-2-4)] {}; -\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=red, fit=(M15-4-1)] {}; -\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=red, fit=(M15-4-2)] {}; -\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=red, fit=(M17-2-4)] {}; -\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=red, fit=(M17-4-4)] {}; -\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=green, fit=(M17-2-2)] {}; -\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=green, fit=(M17-4-2)] {}; -\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=green, fit=(M23-3-1)] {}; -\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=red, fit=(M23-4-1)] {}; -\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=green, fit=(M25-4-1)] {}; -\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=green, fit=(M25-4-2)] {}; +\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=gray, fit=(M21-4-1)] {}; +\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=gray, fit=(M21-1-4)] {}; +\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=gray, fit=(M21-4-4)] {}; +\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=gray, fit=(M21-1-1)] {}; -\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=green, fit=(M32-1-4)] {}; -\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=green, fit=(M32-1-3)] {}; -\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=red, fit=(M34-1-4)] {}; -\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=green, fit=(M34-2-4)] {}; +\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=gray, fit=(M31-4-1)] {}; +\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=gray, fit=(M31-1-4)] {}; +\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=gray, fit=(M31-4-4)] {}; +\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=gray, fit=(M31-1-1)] {}; \node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=green, fit=(M41-4-1)] {}; \node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=green, fit=(M41-1-4)] {}; \node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=green, fit=(M41-4-4)] {}; \node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=green, fit=(M41-1-1)] {}; + +% Q +\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=gray, fit=(M12-1-4)] {}; +\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=gray, fit=(M12-1-3)] {}; + +\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=gray, fit=(M22-1-4)] {}; +\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=gray, fit=(M22-1-3)] {}; + +\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=green, fit=(M32-1-4)] {}; +\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=green, fit=(M32-1-3)] {}; + \node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=red, fit=(M42-1-4)] {}; \node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=red, fit=(M42-1-3)] {}; + +% R + +\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=gray, fit=(M13-3-1)] {}; +\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=gray, fit=(M13-4-1)] {}; + +\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=green, fit=(M23-3-1)] {}; +\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=red, fit=(M23-4-1)] {}; + +\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=gray, fit=(M33-3-1)] {}; +\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=gray, fit=(M33-4-1)] {}; + \node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=green, fit=(M43-3-1)] {}; \node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=red, fit=(M43-4-1)] {}; + +% S + +\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=red, fit=(M14-1-4)] {}; +\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=green, fit=(M14-2-4)] {}; + + +\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=gray, fit=(M24-1-4)] {}; +\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=gray, fit=(M24-2-4)] {}; + +\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=red, fit=(M34-1-4)] {}; +\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=green, fit=(M34-2-4)] {}; + +\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=gray, fit=(M44-1-4)] {}; +\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=gray, fit=(M44-2-4)] {}; + +%T + +\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=red, fit=(M15-4-1)] {}; +\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=red, fit=(M15-4-2)] {}; + +\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=green, fit=(M25-4-1)] {}; +\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=green, fit=(M25-4-2)] {}; + +\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=gray, fit=(M35-4-1)] {}; +\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=gray, fit=(M35-4-2)] {}; + +\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=gray, fit=(M45-4-1)] {}; +\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=gray, fit=(M45-4-2)] {}; + +% U + +\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=gray, fit=(M16-1-3)] {}; +\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=gray, fit=(M16-1-1)] {}; +\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=gray, fit=(M16-3-3)] {}; +\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=gray, fit=(M16-3-1)] {}; + +\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=gray, fit=(M26-1-3)] {}; +\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=gray, fit=(M26-1-1)] {}; +\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=gray, fit=(M26-3-3)] {}; +\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=gray, fit=(M26-3-1)] {}; + +\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=gray, fit=(M36-1-3)] {}; +\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=gray, fit=(M36-1-1)] {}; +\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=gray, fit=(M36-3-3)] {}; +\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=gray, fit=(M36-3-1)] {}; + \node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=green, fit=(M46-1-3)] {}; \node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=red, fit=(M46-1-1)] {}; \node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=green, fit=(M46-3-3)] {}; \node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=red, fit=(M46-3-1)] {}; + +%V + +\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=red, fit=(M17-2-4)] {}; +\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=red, fit=(M17-4-4)] {}; +\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=green, fit=(M17-2-2)] {}; +\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=green, fit=(M17-4-2)] {}; + + +\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=gray, fit=(M27-2-4)] {}; +\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=gray, fit=(M27-4-4)] {}; +\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=gray, fit=(M27-2-2)] {}; +\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=gray, fit=(M27-4-2)] {}; + +\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=gray, fit=(M37-2-4)] {}; +\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=gray, fit=(M37-4-4)] {}; +\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=gray, fit=(M37-2-2)] {}; +\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=gray, fit=(M37-4-2)] {}; + +\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=gray, fit=(M47-2-4)] {}; +\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=gray, fit=(M47-4-4)] {}; +\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=gray, fit=(M47-2-2)] {}; +\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=gray, fit=(M47-4-2)] {}; + + + + + \end{tikzpicture} \end{document} diff --git a/buch/papers/multiplikation/loesungsmethoden.tex b/buch/papers/multiplikation/loesungsmethoden.tex index ac7cb85..90cb9ff 100755 --- a/buch/papers/multiplikation/loesungsmethoden.tex +++ b/buch/papers/multiplikation/loesungsmethoden.tex @@ -7,12 +7,12 @@ \section{Algorithmen} \rhead{Algorithmen} -In diesem Abschnitt werden mehrere Algorithmen zur Berechnung der Matrizenmultiplikation vorgestellt, auch werden Bibliotheken zur automatisierten Verwendung von vordefinierten Algorithmen gezeigt. +In diesem Abschnitt werden mehrere Algorithmen zur Berechnung der Matrizenmultiplikation vorgestellt, auch werden Bibliotheken zur unkomplizierten Verwendung von vordefinierten Algorithmen gezeigt. \subsection{Standard Algorithmus} -Die Standardmethode kann im Algorithmus \ref{multiplikation:alg:smm} gsehen werden. -Hierf\"ur wurde die Gleichung \eqref{multiplikation:eq:MM} direkt implementiert. +Die Standardmethode ist im Algorithmus \ref{multiplikation:alg:smm} implementiert. +Hierf\"ur wurde die Gleichung \eqref{multiplikation:eq:MM} direkt umgesetzt. Die \texttt{for i} Schleife iteriert \"uber alle Zeilen der $\mathbf{A}$ Matrix, die \texttt{for j} Schleife iteriert \"uber alle Spalten der $\mathbf{B}$ Matrix und die \texttt{for k} Schleife iteriert \"uber alle Eintr\"age dieser Zeilen bzw. Spalten. \begin{algorithm}\footnotesize\caption{Matrizenmultiplikation} \label{multiplikation:alg:smm} @@ -37,7 +37,7 @@ Die \texttt{for i} Schleife iteriert \"uber alle Zeilen der $\mathbf{A}$ Matrix, \EndFunction \end{algorithmic} \end{algorithm} -Die Laufzeit dieser Struktur mit drei \texttt{For} Schleifen ist $\mathcal{O} (n^3)$ +Die Laufzeit dieser Struktur mit drei \texttt{for} Schleifen ist $\mathcal{O} (n^3)$. \subsubsection{Divide and Conquer Methode} @@ -65,8 +65,8 @@ Das Matrizen Produkt \mathbf{C}_{21} & \mathbf{C}_{22} \end{bmatrix}, \end{equation} -\begin{equation} -\mathbf{C}_{ij} = \sum_{k=1}^{2n} \mathbf{A}_{ik} \mathbf{B}_{kj} +mit \begin{equation} +\mathbf{C}_{ij} = \sum_{k=1}^{2n} \mathbf{A}_{ik} \mathbf{B}_{kj}, \label{multiplikation:eq:MM_block} \end{equation} ist identisch zu der Gleichung \eqref{multiplikation:eq:MM}, f\"ur die Multiplikation der Untermatrize $\mathbf{A}_{ik}$ und $\mathbf{B}_{kj}$ wird die Matrizenmultiplikation verwendet. @@ -105,11 +105,11 @@ Der rekursive Aufruf wird bis zu der Gr\"osse der Matrizen von $N = 2 \times 2$ Die Laufzeit dieser rekursiven Funktion kann mit dem \textit{Master Theorem} \cite{multiplikation:master_theorem} berechnet werden. Das \textit{Master Theorem} bestimmt die Zeitkomplexit\"at von rekursiven Algorithmen. Ohne auf dieses vertieft einzugehen, bestimmt die Anzahl rekursiver Aufrufe $\mathcal{T} $ der Funktion die Laufzeit. -In diesem Fall wird die Funktion pro Durchlauf acht mal rekursiv aufgerufen, dies f\"uhrt +In diesem Fall wird die Funktion pro Durchlauf acht mal rekursiv aufgerufen, dies f\"uhrt zu \begin{equation} \label{multiplikation:eq:laufzeitdac} - \mathcal{T}(n) = 8 \cdot \mathcal{T} \left(\frac{n}{2}\right ) + n^2 = \mathcal{O}(n^{\log_2 8}) = \mathcal{O} (n^{3} ) + \mathcal{T}(n) = 8 \cdot \mathcal{T} \left(\frac{n}{2}\right ) + n^2 = \mathcal{O}(n^{\log_2 8}) = \mathcal{O} (n^{3} ), \end{equation} -zu einer kubischen Laufzeit. +also einer kubischen Laufzeit. Die Addition zweier Matrizen $\mathbf{A} + \mathbf{B} = \mathbf{C}$ hat eine Laufzeit von $\mathcal{O}(n^{2})$ und kann neben dem dominierendem Anteil von $\mathcal{O}(n^{3})$ ignoriert werden. In diesem Fall hat der \textit{Divide and Conquer} Ansatz zu keiner Verbesserung gef\"uhrt. @@ -187,7 +187,7 @@ der Matrix $\mathbf{C}$ gebraucht. Strassens Methode wird in der Abbildung \ref{multiplikation:fig:strassen} grafisch dargestellt. Jedes Feld steht f\"ur eine Multiplikation zweier Matrizenelementen von $\mathbf{A}$ oder $\mathbf{B}$ . Die gr\"unen Felder auf der linken Seite, zeigen die Addition, welche f\"ur den dazugeh\"origen Term ben\"otigt wird. -Die sieben Spalten beschreiben die Matrizen $\mathbf{P,Q,R, \dotsb, V}$. +Die sieben Spalten beschreiben die Matrizen $\mathbf{P,Q,R, \ldots, V}$. Rote Felder stehen f\"ur eine Subtraktion und die gr\"unen f\"ur eine Addition. \begin{figure} \center @@ -246,7 +246,7 @@ Im Vergleich mit der Methode von Winograd, \end{split} \end{align} %\end{equation} -werden für die berechnung des Skalarproduktes weniger Multiplikationen benötigt, falls $N\leq T$. +werden für die Berechnung des Skalarproduktes weniger Multiplikationen benötigt, falls $N\leq T$. Eine Matrizenmultiplikation mit $\mathbf{A}$ einer $m \times n$ und $\mathbf{B}$ einer $n \times p$ Matrix, entspricht $N=m+p$ Vektoren mit welchen man $T=mp$ Skalarprodukte berechnet. Dies f\"uhrt zu \begin{equation} @@ -266,7 +266,7 @@ sein, damit man etwas einspart. Die Implementation kann Algorithmus \ref{multiplikation:alg:winograd} entnommen werden. Falls $m=n=p$, werden $\frac{n^3}{2}$ Multiplikationen benötigt. Im Abschnitt \ref{muliplikation:sec:bigo} wurde bereits erläutert: falls $n \rightarrow \infty$ können Konstanten vernachlässigt werden und - somit entsteht für diesen Algorithmus wieder die Ursprüngliche Laufzeit von $\mathcal{O}(n^3 )$. + somit entsteht für diesen Algorithmus wieder die ursprüngliche Laufzeit von $\mathcal{O}(n^3 )$. \begin{algorithm}\footnotesize\caption{Winograds Matrizenmultiplikation} \setlength{\lineskip}{7pt} \label{multiplikation:alg:winograd} @@ -406,21 +406,21 @@ Die Hardwareinformationen des verwendeten Computers sind in der Tabelle \ref{mul \begin{table} \begin{center} - \begin{tabular}{l l l l l l} + \begin{tabular}{r l l l l l} \hline \hline \textbf{n} & \textbf{MM (\textit{s})} & \textbf{MM DC (\textit{s})} & \textbf{Strassen (\textit{s})} & \textbf{Winograd (\textit{s})} & \textbf{BLAS (\textit{s})} \\ \hline \multicolumn{6}{c}{} \\ - \textbf{32} & 0.000089 & 0.000594 & 0.0005 & 0.00008 & 0.000021 \\ - \textbf{64} & 0.00069 & 0.0044 & 0.0036 & 0.00064 & 0.00018 \\ - \textbf{128} & 0.0057 & 0.035 & 0.025 & 0.0052 & 0.0012 \\ - \textbf{256} & 0.052 & 0.29 & 0.178 & 0.053 & 0.0096 \\ - \textbf{512} & 0.51 & 2.22 & 1.25 & 0.55 & 0.077 \\ - \textbf{1024} & 4.50 & 17.65 & 8.83 & 4.67 & 0.764 \\ - \textbf{2048} & 129.28 & 141.61 & 61.901 & 136.67 & 7.63 \\ - \textbf{4096} & 1111.31 & 1147.10 & 414.64 & 1179.26 & 55.84 \\ - \textbf{8192} & 9376.17 & 9606.40 & 3014.23 & 10071.51& 478.42 \\ + \textbf{32} & \phantom{000}0.000089 & \phantom{000}0.000594 & \phantom{000}0.0005 & \phantom{0000}0.00008 & \phantom{00}0.000021 \\ + \textbf{64} & \phantom{000}0.00069 & \phantom{000}0.0044 & \phantom{000}0.0036 & \phantom{0000}0.00064 & \phantom{00}0.00018 \\ + \textbf{128} & \phantom{000}0.0057 & \phantom{000}0.035 & \phantom{000}0.025 & \phantom{0000}0.0052 & \phantom{00}0.0012 \\ + \textbf{256} & \phantom{000}0.052 & \phantom{000}0.29 & \phantom{000}0.178 & \phantom{0000}0.053 & \phantom{00}0.0096 \\ + \textbf{512} & \phantom{000}0.51 & \phantom{000}2.22 & \phantom{000}1.25 & \phantom{0000}0.55 & \phantom{00}0.077 \\ + \textbf{1024} & \phantom{000}4.50 & \phantom{00}17.65 & \phantom{000}8.83 & \phantom{0000}4.67 & \phantom{00}0.764 \\ + \textbf{2048} & \phantom{0}129.28 & \phantom{0}141.61 & \phantom{00}61.901 & \phantom{00}136.67 & \phantom{00}7.63 \\ + \textbf{4096} & 1111.31 & 1147.10 & \phantom{0}414.64 & \phantom{0}1179.26 & \phantom{0}55.84 \\ + \textbf{8192} & 9376.17 & 9606.40 & 3014.23 & 10071.51 & 478.42 \\ \multicolumn{6}{c}{} \\ \hline \hline @@ -434,20 +434,20 @@ Die Hardwareinformationen des verwendeten Computers sind in der Tabelle \ref{mul \begin{table} \begin{center} - \begin{tabular}{l l l l l l} + \begin{tabular}{r l l l l l} \hline \hline \textbf{n} & \textbf{MM (\textit{s})} & \textbf{MM DC (\textit{s})} & \textbf{Strassen (\textit{s})} & \textbf{Winograd (\textit{s})} & \textbf{NumPy(\textit{s})} \\ \hline \multicolumn{6}{c}{} \\ - \textbf{32} & 0.0240 &0.0271 & 0.04852& 0.01871 & 0.0000426 \\ - \textbf{64} & 0.186 & 0.265& 0.2204& 0.1530& 0.000118 \\ - \textbf{128} & 1.563 & 1.777& 1.447& 1.1947 & 0.000244 \\ - \textbf{256} & 11.006 & 13.27 & 9.938 & 8.298& 0.000695 \\ - \textbf{512} & 85.476 & 105.397 & 63.961 & 68.36 & 0.00221\\ - \textbf{1024} & 750.757 & 847.321& 461.494 & 537.374 & 0.0188 \\ - \textbf{2048} & 6154.18 & 7375.93& 3860.57 & 4884.61 & 0.215 \\ - \textbf{4096} & 46813.3 & 58466 & 22904.3 & 43597.1 & 1.49 \\ + \textbf{32} & \phantom{000}0.0240 & \phantom{0000}0.0271& \phantom{0000}0.04852 & \phantom{0000}0.01871 & 0.0000426 \\ + \textbf{64} &\phantom{000} 0.186 & \phantom{0000}0.265 & \phantom{0000}0.2204 & \phantom{0000}0.1530& 0.000118 \\ + \textbf{128} &\phantom{000} 1.563 & \phantom{0000}1.777 & \phantom{0000}1.447 & \phantom{0000}1.1947 & 0.000244 \\ + \textbf{256} &\phantom{00} 11.006 & \phantom{000}13.27 & \phantom{0000}9.938 & \phantom{0000}8.298& 0.000695 \\ + \textbf{512} &\phantom{00} 85.476 & \phantom{00}105.397 & \phantom{000}63.961 & \phantom{000}68.360 & 0.00221\\ + \textbf{1024} &\phantom{0} 750.757 & \phantom{00}847.321 & \phantom{00}461.494 & \phantom{00}537.374 & 0.0188 \\ + \textbf{2048} & 6154.18 & \phantom{0}7375.93 & \phantom{0}3860.57 & \phantom{0}4884.61 & 0.215 \\ + \textbf{4096} & 46813.30 & 58466.00 & 22904.30 & 43597.10 & 1.49 \\ \multicolumn{6}{c}{} \\ \hline \hline diff --git a/buch/papers/multiplikation/main.tex b/buch/papers/multiplikation/main.tex index fb1908e..ca93e92 100755 --- a/buch/papers/multiplikation/main.tex +++ b/buch/papers/multiplikation/main.tex @@ -26,8 +26,8 @@ backgroundcolor=\color{backcolour} } -\chapter{Schnelle Matrizen Multiplikation\label{chapter:multiplikation}} -\lhead{FMM} +\chapter{Schnelle Matrizenmultiplikation\label{chapter:multiplikation}} +\lhead{MM} \begin{refsection} \chapterauthor{Michael Schmid} diff --git a/buch/papers/multiplikation/problemstellung.tex b/buch/papers/multiplikation/problemstellung.tex index b8c4142..a9aeda0 100755 --- a/buch/papers/multiplikation/problemstellung.tex +++ b/buch/papers/multiplikation/problemstellung.tex @@ -3,13 +3,12 @@ % % (c) 2020 Prof Dr Andreas Müller, Hochschule Rapperswil % -\section{Problemstellung} +\section{Laufzeiten von Algorithmen} \rhead{Problemstellung} -Wegen der breiten Anwendung der Matrizenmultiplikation ist eine effiziente L\"osung dieser Operation von grosser Bedeutung. +Wegen der breiten Anwendung der Matrizenmultiplikation ist eine effiziente Ausführung dieser Operation von grosser Bedeutung. Das Ziel dieses Papers ist, verschiedenen Algorithmen der Matrizenmultiplikation vorzustellen. Gezielt wird auf Algorithmen eingegangen, welche das Problem schneller als der Standardalgorithmus l\"osen. -\subsection{Big $\mathcal{O}$ Notation} \label{muliplikation:sec:bigo} Die Big $\mathcal{O}$ Notation beschreibt die Laufzeitkomplexit\"at eines Algorithmus in Abhängigkeit zur Inputgrösse \cite{multiplikation:bigo}. $f(x) \in \mathcal{O}(g(x))$ besagt, dass die Funktion $f$ nicht wesentlich schneller w\"achst als $g$ wenn $x \rightarrow \infty$. @@ -26,15 +25,15 @@ Vereinfacht werden f\"ur Algorithmen die folgende Sprechweise verwendet: \item usw. \end{itemize} -Konstanten werden nicht beachtet, eine Laufzeit von $\mathcal{O}(4n^2)$ führt, falls $n \rightarrow \infty$ zu $\mathcal{O}(n^2)$. +Konstanten werden nicht beachtet, eine Laufzeit von $4n^2$ führt, falls $n \rightarrow \infty$ zu $\mathcal{O}(n^2)$. In der Abbildung \ref{multiplikation:fig:bigo} k\"onnen die verschiedenen Laufzeiten miteinander verglichen werden. -Bei einer logarithmischen Darstellung werden Polynome der Form $f(x) = x^k$ als Gerade und Exponentialfunktionen der Form $f(x) = a^x$ als nach oben gekr\"ummte Kurven dargestellt. +Bei einer doppelt logarithmischen Darstellung werden Polynome der Form $f(x) = x^k$ als Gerade und Exponentialfunktionen der Form $f(x) = a^x$ als nach oben gekr\"ummte Kurven abbgebildet. \subsubsection{Beispiel Algorithmen} -Es folgen einige Beispiele von Algorithmen welche zu einer bestimmten Zeitkomplexit\"atsklasse zugeteilt werden k\"onnen. +Es folgen einige Beispiele von Algorithmen, welche zu einer bestimmten Zeitkomplexit\"atsklasse zugeteilt werden k\"onnen. \begin{table}[t] |