update

1 files changed, 31 insertions, 31 deletions

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