Merge branch 'master' into master

10 files changed, 1029 insertions, 0 deletions

diff --git a/buch/papers/multiplikation/presentation/slides/algo.tex b/buch/papers/multiplikation/presentation/slides/algo.tex
new file mode 100644
index 0000000..0c3d130
--- /dev/null
+++ b/buch/papers/multiplikation/presentation/slides/algo.tex
@@ -0,0 +1,111 @@
+\begin{frame}
+  \frametitle{Algorithm}
+  \begin{columns}
+    \begin{column}{0.6\textwidth}
+  \begin{algorithm}[H]\caption{Square Matrix Multiplication}
+    \setlength{\lineskip}{7pt}
+    \begin{algorithmic}[1]
+      \Function{MM}{$\textbf{A}, \textbf{B}, \textbf{C}$}
+      \State $sum \gets 0$
+      \State $n \gets columns(\textbf{A}) == rows(\textbf{B})$
+      \State $m \gets rows(\textbf{A})$
+      \State $p \gets columns(\textbf{B})$
+
+        \For{$i = 0,1,2 \dots,m-1$}
+        \For{$j = 0,1,2 \dots,p-1$}
+        \State $sum \gets 0$
+        \For{$k = 0,1,2 \dots,n-1$}
+          \State $sum \gets  sum + \textbf{A}[i][k] \cdot \textbf{B}[k][j]$
+        \EndFor
+        \State $\textbf{C}[i][j] \gets  sum $
+        \EndFor
+        \EndFor
+        \State \textbf{return} $\textbf{C}$
+     \EndFunction
+    \end{algorithmic}
+  \end{algorithm}
+\end{column}
+\begin{column}{0.4\textwidth}
+  \scalebox{0.6}{\parbox{\linewidth}{
+
+  \begin{tikzpicture}[ampersand replacement=\&,remember picture,overlay]
+
+    \matrix (A)[matrix of math nodes, label skeleton, left delimiter=[,right delimiter={]}] at (2,-2.8)
+     {
+     A_{1,1} \& \cdots \& A_{1,k} \& \cdots \& A_{1,n} \\
+     \vdots \&  \& \vdots \&  \& \vdots \\
+     A_{i,1} \& \cdots \& A_{i,k} \& \cdots \& A_{i,n} \\
+     \vdots \&  \& \vdots \& \& \vdots \\
+     A_{m,1} \& \cdots \& A_{m,k} \& \cdots \& A_{m,n} \\
+     };
+
+     \matrix (B)[matrix of math nodes, label skeleton, left delimiter=[,right delimiter={]}] at (7.5,1.2)
+      {
+      B_{1,1} \& \cdots \& B_{1,j} \& \cdots \& B_{1,p} \\
+      \vdots \&  \& \vdots \&  \& \vdots \\
+      B_{k,1} \& \cdots \& B_{k,j} \& \cdots \& B_{k,p} \\
+      \vdots \&  \& \vdots \& \& \vdots \\
+      B_{n,1} \& \cdots \& B_{n,j} \& \cdots \& B_{n,p} \\
+      };
+
+     \matrix (C)[matrix of math nodes, label skeleton, left delimiter=[,right delimiter={]}] at (7.5,-2.8)
+      {
+      C_{1,1} \& \cdots \& C_{1,j} \& \cdots \& C_{1,p} \\
+      \vdots \&  \& \vdots \&  \& \vdots \\
+      C_{i,1} \& \cdots \& C_{i,j} \& \cdots \& C_{i,p} \\
+      \vdots \&  \& \vdots \& \& \vdots \\
+      C_{m,1} \& \cdots \& C_{m,j} \& \cdots \& C_{m,p} \\
+      };
+
+
+               \begin{scope}[on background layer]
+               \node[opacity=0.5, rounded corners=2pt, inner sep=-1pt, fill=green, fit=(A-3-1)(A-3-5)] {};
+               \node[opacity=0.5, rounded corners=2pt, inner sep=-1pt, fill=blue, fit=(B-1-3)(B-5-3)] {};
+               \node[opacity=0.5, rounded corners=2pt, inner sep=-1pt, fill=red, fit=(C-3-3)] {};
+
+               \end{scope}
+
+
+
+
+   \end{tikzpicture}
+   }}
+ \end{column}
+\end{columns}
+\end{frame}
+
+
+\begin{frame}
+  \frametitle{Algorithm}
+
+\begin{columns}
+  \begin{column}{0.6\textwidth}
+\begin{algorithm}[H]\caption{Square Matrix Multiplication}
+  \setlength{\lineskip}{7pt}
+  \begin{algorithmic}[1]
+    \Function{MM}{$\textbf{A}, \textbf{B}, \textbf{C}$}
+    \State $sum \gets 0$
+    \State $n \gets columns(\textbf{A}) == rows(\textbf{B})$
+    \State $m \gets rows(\textbf{A})$
+    \State $p \gets columns(\textbf{B})$
+
+      \For{$i = 0,1,2 \dots,m-1$}
+      \For{$j = 0,1,2 \dots,p-1$}
+      \State $sum \gets 0$
+      \For{$k = 0,1,2 \dots,n-1$}
+        \State $sum \gets  sum + \textbf{A}[i][k] \cdot \textbf{B}[k][j]$
+      \EndFor
+      \State $\textbf{C}[i][j] \gets  sum $
+      \EndFor
+      \EndFor
+      \State \textbf{return} $\textbf{C}$
+   \EndFunction
+  \end{algorithmic}
+\end{algorithm}
+\end{column}
+\begin{column}{0.4\textwidth}
+\Huge$\mathcal{O}(n^3)$
+\end{column}
+\end{columns}
+
+\end{frame}
diff --git a/buch/papers/multiplikation/presentation/slides/bigO.tex b/buch/papers/multiplikation/presentation/slides/bigO.tex
new file mode 100644
index 0000000..d425da8
--- /dev/null
+++ b/buch/papers/multiplikation/presentation/slides/bigO.tex
@@ -0,0 +1,251 @@
+
+\begin{frame}
+  \frametitle{Big $\mathcal{O}$ notation}
+\begin{itemize}
+  \item <1-> Time complexity of an algorithm
+  \item <2-> How many multiplications in a function
+  \item <3-> Drop Constants
+\end{itemize}
+\end{frame}
+
+
+\begin{frame}
+  \frametitle{Big $\mathcal{O}$ notation}
+  \onslide<1->{
+
+  \begin{algorithm}[H]\caption{Foo 1}
+    \setlength{\lineskip}{7pt}
+    \begin{algorithmic}[1]
+      \Function{foo}{$a, b$}
+        \State \textbf{return} $a+b$
+     \EndFunction
+    \end{algorithmic}
+  \end{algorithm}
+}
+\onslide<2->{
+$\mathcal{O}(1)$
+  }
+\end{frame}
+
+\begin{frame}
+  \frametitle{Big $\mathcal{O}$ notation}
+  \onslide<1->{
+
+  \begin{algorithm}[H]\caption{Foo 2}
+    \setlength{\lineskip}{7pt}
+    \begin{algorithmic}[1]
+      \Function{foo}{$a, b$}
+        \State $ x \gets a+b $
+        \State $ y \gets a \cdot b $
+        \State \textbf{return} $x+y$
+     \EndFunction
+    \end{algorithmic}
+  \end{algorithm}
+}
+\onslide<2->{
+$\mathcal{O}(1) + \mathcal{O}(1) = 2\mathcal{O}(1) = \mathcal{O}(1) $
+  }
+\end{frame}
+
+\begin{frame}
+  \frametitle{Big $\mathcal{O}$ notation}
+  \onslide<1->{
+
+  \begin{algorithm}[H]\caption{Foo 3}
+    \setlength{\lineskip}{7pt}
+    \begin{algorithmic}[1]
+      \Function{foo}{$\mathbf{A}, \mathbf{B}$,n}
+      \State $ sum \gets 0$
+      \For{$i = 0,1,2 \dots,n$}
+        \State $ sum \gets sum + A[i] \cdot B[i] $
+        \EndFor
+
+        \State \textbf{return} $sum$
+
+     \EndFunction
+    \end{algorithmic}
+  \end{algorithm}
+}
+\onslide<2->{
+$\mathcal{O}(n)$
+  }
+\end{frame}
+
+\begin{frame}
+  \frametitle{Big $\mathcal{O}$ notation}
+  \onslide<1->{
+
+  \begin{algorithm}[H]\caption{Foo 4}
+    \setlength{\lineskip}{7pt}
+    \begin{algorithmic}[1]
+      \Function{foo}{$\mathbf{A}, \mathbf{B}$,n}
+      \State $ sum \gets 0$
+      \For{$i = 0,1,2 \dots,n$}
+      \For{$j = 0,1,2 \dots,n$}
+      \State $ sum \gets sum + A[i] \cdot B[j] $
+      \EndFor
+      \EndFor
+        \State \textbf{return} $sum$
+     \EndFunction
+    \end{algorithmic}
+  \end{algorithm}
+}
+\onslide<2->{
+$\mathcal{O}(n^2)$
+  }
+\end{frame}
+
+% \begin{frame}
+%   \frametitle{Big $\mathcal{O}$ notation}
+%   \onslide<1->{
+%
+%   \begin{algorithm}[H]\caption{Fibonacci}
+%     \setlength{\lineskip}{7pt}
+%     \begin{algorithmic}[1]
+%       \Function{fib}{$n$}
+%       \If{$n <= 1$}
+%       \State \textbf{return} $1$
+%       \Else
+%         \State \textbf{return} fib($n-1$) + fib($n-2$)
+%         \EndIf
+%
+%      \EndFunction
+%     \end{algorithmic}
+%   \end{algorithm}
+% }
+% \onslide<2->{
+% \[
+% \langle x,y \rangle =
+% \begin{cases}
+%  \displaystyle $\mathcal{O}(1)$  & \text{if  $n \leq 2$}\\
+% \displaystyle $ 2 \mathcal{T}(\frac{n}{2})$  & \text{if  $n > 2$}
+% \end{cases}
+% \]  }
+% \end{frame}
+
+
+\begin{frame}
+  \frametitle{Big $\mathcal{O}$ notation}
+\begin{tikzpicture}
+\begin{axis}[
+    axis lines = left,
+    xlabel = $n$ (Data Input),
+    ylabel = {$t$ (time)},
+    legend pos=north east,
+    very thick,
+    ymax = 20,
+    yticklabels=\empty,
+    xticklabels=\empty,
+    scale only axis=true,
+  width=12cm, height=6cm,
+    ]
+%Below the red parabola is defined
+\addplot [
+    domain= 1:6,
+    samples=100,
+    color=red,
+]
+{1};
+\addlegendentry{$\mathcal{O}(1)$}
+%Here the blue parabloa is defined
+\addplot [
+    domain= 1:6,
+    samples=100,
+    color=green,
+]
+{x};
+\addlegendentry{$\mathcal{O}(n)$}
+\addplot [
+    domain= 1:6,
+    samples=100,
+    color=blue,
+]
+{x^2};
+\addlegendentry{$\mathcal{O}(n^2)$}
+\addplot [
+    domain= 1:6,
+    samples=100,
+    color=purple,
+]
+{x^3};
+\addlegendentry{$\mathcal{O}(n^3)$}
+\addplot [
+    domain= 1:3,
+    samples=100,
+    color=black,
+]
+{exp(x)};
+\addlegendentry{$\mathcal{O}(e^n)$}
+\addplot [
+    domain= 1:6,
+    samples=100,
+    color=orange,
+]
+{log2(x)};
+\addlegendentry{$\mathcal{O}(\log n)$}
+\end{axis}
+\end{tikzpicture}
+
+\end{frame}
+
+\begin{frame}
+  \frametitle{Big $\mathcal{O}$ notation}
+\begin{tikzpicture}
+\begin{axis}[
+    axis lines = left,
+    xlabel = $n$ (Data Input),
+    ylabel = {$t$ (time)},
+    legend pos=north east,
+    very thick,
+    ymax = 500,
+    yticklabels=\empty,
+    xticklabels=\empty,
+    scale only axis=true,
+  width=12cm, height=6cm,
+    ]
+\addplot [
+    domain= 1:20,
+    samples=100,
+    color=red,
+]
+{1};
+\addlegendentry{$\mathcal{O}(1)$}
+\addplot [
+    domain= 1:20,
+    samples=100,
+    color=green,
+]
+{x};
+\addlegendentry{$\mathcal{O}(n)$}
+\addplot [
+    domain= 1:20,
+    samples=100,
+    color=blue,
+]
+{x^2};
+\addlegendentry{$\mathcal{O}(n^2)$}
+\addplot [
+    domain= 1:10,
+    samples=100,
+    color=purple,
+]
+{x^3};
+\addlegendentry{$\mathcal{O}(n^3)$}
+\addplot [
+    domain= 1:10,
+    samples=100,
+    color=black,
+]
+{exp(x)};
+\addlegendentry{$\mathcal{O}(e^n)$}
+\addplot [
+    domain= 1:20,
+    samples=100,
+    color=orange,
+]
+{log2(x)};
+\addlegendentry{$\mathcal{O}(\log n)$}
+\end{axis}
+\end{tikzpicture}
+
+\end{frame}
diff --git a/buch/papers/multiplikation/presentation/slides/blas.tex b/buch/papers/multiplikation/presentation/slides/blas.tex
new file mode 100644
index 0000000..ed498a3
--- /dev/null
+++ b/buch/papers/multiplikation/presentation/slides/blas.tex
@@ -0,0 +1,18 @@
+\begin{frame}
+\frametitle{BLAS, LAPACK}
+\begin{itemize}
+  \item Basic Linear Algebra Subprograms
+  \begin{itemize}
+    \item $\mathbf{y} = \alpha \mathbf{x}+\mathbf{y}$
+    \item $\mathbf{y} = \alpha \mathbf{A}\mathbf{x}+ \beta \mathbf{y}$
+    \item $\mathbf{C} = \alpha \mathbf{A}\mathbf{B}+ \beta \mathbf{C}$
+
+  \end{itemize}
+  \item Linear Algebra Package
+  \begin{itemize}
+    \item QR decomposition
+    \item Singular value decomposition
+    \item Eigenvalues
+  \end{itemize}
+\end{itemize}
+\end{frame}
diff --git a/buch/papers/multiplikation/presentation/slides/conclusuion.tex b/buch/papers/multiplikation/presentation/slides/conclusuion.tex
new file mode 100644
index 0000000..e69de29
--- /dev/null
+++ b/buch/papers/multiplikation/presentation/slides/conclusuion.tex
diff --git a/buch/papers/multiplikation/presentation/slides/logo.pdf b/buch/papers/multiplikation/presentation/slides/logo.pdf
new file mode 100644
index 0000000..d78ca88
--- /dev/null
+++ b/buch/papers/multiplikation/presentation/slides/logo.pdf
diff --git a/buch/papers/multiplikation/presentation/slides/meas.tex b/buch/papers/multiplikation/presentation/slides/meas.tex
new file mode 100644
index 0000000..489c010
--- /dev/null
+++ b/buch/papers/multiplikation/presentation/slides/meas.tex
@@ -0,0 +1,42 @@
+\begin{frame}
+  \frametitle{Measurements Python}
+  \only<1>{
+  \includegraphics[width=\textwidth,height=0.9\textheight,keepaspectratio]{../code/meas_8.pdf}}
+  \only<2>{
+  \includegraphics[width=\textwidth,height=0.9\textheight,keepaspectratio]{../code/meas_16.pdf}}
+  \only<3>{
+  \includegraphics[width=\textwidth,height=0.9\textheight,keepaspectratio]{../code/meas_32.pdf}}
+  \only<4>{
+  \includegraphics[width=\textwidth,height=0.9\textheight,keepaspectratio]{../code/meas_64.pdf}}
+  \only<5>{
+  \includegraphics[width=\textwidth,height=0.9\textheight,keepaspectratio]{../code/meas_128.pdf}}
+  \only<6>{
+  \includegraphics[width=\textwidth,height=0.9\textheight,keepaspectratio]{../code/meas_256.pdf}}
+  \only<7>{
+  \includegraphics[width=\textwidth,height=0.9\textheight,keepaspectratio]{../code/meas_512.pdf}}
+  \only<8>{
+  \includegraphics[width=\textwidth,height=0.9\textheight,keepaspectratio]{../code/meas_1024.pdf}}
+\end{frame}
+
+
+\begin{frame}
+  \frametitle{Measurements C}
+  \only<1>{
+  \includegraphics[width=\textwidth,height=0.9\textheight,keepaspectratio]{../code/c_meas_8.pdf}}
+  \only<2>{
+  \includegraphics[width=\textwidth,height=0.9\textheight,keepaspectratio]{../code/c_meas_16.pdf}}
+  \only<3>{
+  \includegraphics[width=\textwidth,height=0.9\textheight,keepaspectratio]{../code/c_meas_32.pdf}}
+  \only<4>{
+  \includegraphics[width=\textwidth,height=0.9\textheight,keepaspectratio]{../code/c_meas_64.pdf}}
+  \only<5>{
+  \includegraphics[width=\textwidth,height=0.9\textheight,keepaspectratio]{../code/c_meas_128.pdf}}
+  \only<6>{
+  \includegraphics[width=\textwidth,height=0.9\textheight,keepaspectratio]{../code/c_meas_256.pdf}}
+  \only<7>{
+  \includegraphics[width=\textwidth,height=0.9\textheight,keepaspectratio]{../code/c_meas_512.pdf}}
+  \only<8>{
+  \includegraphics[width=\textwidth,height=0.9\textheight,keepaspectratio]{../code/c_meas_1024.pdf}}
+  \only<9>{
+  \includegraphics[width=\textwidth,height=0.9\textheight,keepaspectratio]{../code/c_meas_2048.pdf}}
+\end{frame}
diff --git a/buch/papers/multiplikation/presentation/slides/nn.tex b/buch/papers/multiplikation/presentation/slides/nn.tex
new file mode 100644
index 0000000..e74e970
--- /dev/null
+++ b/buch/papers/multiplikation/presentation/slides/nn.tex
@@ -0,0 +1,97 @@
+
+\begin{frame}
+  \frametitle{Neural Network}
+  \centering
+\newcommand{\inputnum}{4}
+
+% Hidden layer neurons'number
+\newcommand{\hiddennumA}{5}
+\newcommand{\hiddennumB}{6}
+
+% Output layer neurons'number
+\newcommand{\outputnum}{4}
+
+\begin{tikzpicture}
+
+
+% Input Layer
+\foreach \i in {1,...,\inputnum}
+{
+	\node[circle,
+		minimum size = 6mm,
+		fill=blue!30] (Input-\i) at (0,-\i) {};
+}
+
+% Hidden Layer1
+\foreach \i in {1,...,\hiddennumA}
+{
+	\node[circle,
+		minimum size = 6mm,
+		fill=red!50,
+		yshift=(\hiddennumA-\inputnum)*5 mm
+	] (Hidden1-\i) at (2.5,-\i) {};
+}
+
+% Hidden Layer2
+\foreach \i in {1,...,\hiddennumB}
+{
+	\node[circle,
+		minimum size = 6mm,
+		fill=red!50,
+		yshift=(\hiddennumB-\inputnum)*5 mm
+	] (Hidden2-\i) at (5,-\i) {};
+}
+
+% Output Layer
+\foreach \i in {1,...,\outputnum}
+{
+	\node[circle,
+		minimum size = 6mm,
+		fill=green!50,
+		yshift=(\outputnum-\inputnum)*5 mm
+	] (Output-\i) at (7.5,-\i) {};
+}
+
+% Connect neurons In-Hidden
+\foreach \i in {1,...,\inputnum}
+{
+	\foreach \j in {1,...,\hiddennumA}
+	{
+		\draw[->, shorten >=1pt] (Input-\i) -- (Hidden1-\j);
+	}
+}
+
+% Connect neurons In-Hidden
+\foreach \i in {1,...,\hiddennumA}
+{
+	\foreach \j in {1,...,\hiddennumB}
+	{
+		\draw[->, shorten >=1pt] (Hidden1-\i) -- (Hidden2-\j);
+	}
+}
+
+% Connect neurons Hidden-Out
+\foreach \i in {1,...,\hiddennumB}
+{
+	\foreach \j in {1,...,\outputnum}
+	{
+		\draw[->, shorten >=1pt] (Hidden2-\i) -- (Output-\j);
+	}
+}
+
+% Inputs
+\foreach \i in {1,...,\inputnum}
+{
+	\draw[<-, shorten <=1pt] (Input-\i) -- ++(-1,0)
+		node[left]{\LARGE{$x_{\i}$}};
+}
+
+% Outputs
+\foreach \i in {1,...,\outputnum}
+{
+	\draw[->, shorten <=1pt] (Output-\i) -- ++(1,0)
+		node[right]{\LARGE{$y_{\i}$}};
+}
+
+\end{tikzpicture}
+\end{frame}
diff --git a/buch/papers/multiplikation/presentation/slides/parcomp.tex b/buch/papers/multiplikation/presentation/slides/parcomp.tex
new file mode 100644
index 0000000..1ba39ee
--- /dev/null
+++ b/buch/papers/multiplikation/presentation/slides/parcomp.tex
@@ -0,0 +1,66 @@
+% !TEX root = presentation.tex
+
+\begin{frame}
+  \frametitle{Vector-Matrix Multiplication}
+\center{
+  \begin{tikzpicture}[ampersand replacement=\&]
+
+    \matrix (A)[matrix of math nodes, label skeleton, left delimiter=[,right delimiter={]}]
+     {
+     A_{1,1} \& A_{1,2} \& A_{1,3} \& A_{1,4} \\
+     };
+
+    \matrix (B)[matrix of math nodes, label skeleton, left delimiter=[,right delimiter={]}] at (5,-0.95)
+     {
+     B_{1,1} \& B_{1,2} \& B_{1,3} \& B_{1,4} \& B_{1,5} \\
+     B_{2,1} \& B_{2,2} \& B_{2,3} \& B_{2,4} \& B_{2,5} \\
+     B_{3,1} \& B_{3,2} \& B_{3,3} \& B_{3,4} \& B_{3,5} \\
+     B_{4,1} \& B_{4,2} \& B_{4,3} \& B_{4,4} \& B_{4,5} \\
+     };
+
+     \matrix (C)[matrix of math nodes, label skeleton, left delimiter=[,right delimiter={]}] at (5,-3)
+      {
+      C_{1,1} \& C_{1,2} \& C_{1,3} \& C_{1,4} \& C_{1,5}\\
+      };
+
+      \foreach \i in {1,...,4}
+      {
+      \pgfmathtruncatemacro{\ii}{\i+1}
+          \onslide<\ii>{
+
+       \foreach \j in {1,...,5}
+       {
+        \draw[thick] (A-1-\i.south) to [out=-90,in=135]node[visible on=<\i->, anchor=north]{} (B-\i-\j.center);
+
+          }
+        }
+        }
+
+
+     \end{tikzpicture}
+}
+\end{frame}
+
+
+\begin{frame}
+  \frametitle{DSP Architecture}
+\scalebox{2}{
+  \begin{tikzpicture}
+    \node (mul) at (0,0) [circle,draw=black,inner sep=0pt,minimum size=0.5cm] {X};
+    \node (mac) at (2,0) [circle,draw=black,inner sep=0pt,minimum size=0.5cm] {\textbf{+}};
+
+    \node at (-2,0.3) {$A[n]$};
+    \node at (0.4,2) {$B[n]$};
+    \node at (4,0.3) {$C[n]$};
+
+    \draw[thick, ->] (-2,0) --++ (mul);
+    \draw[thick, ->] (0,2) --++ (mul);
+    \draw[thick, ->] (mul) -- (mac);
+    \draw[thick] (mac) --++ (1,0) node (i) {};
+    \draw[thick, ->] (i.center) --++ (0,1) --++ (-1,0) -- (mac);
+    \draw[thick, ->] (i.center) --++ (1,0);
+
+
+  \end{tikzpicture}
+  }
+\end{frame}
diff --git a/buch/papers/multiplikation/presentation/slides/slides.tex b/buch/papers/multiplikation/presentation/slides/slides.tex
new file mode 100644
index 0000000..64edb86
--- /dev/null
+++ b/buch/papers/multiplikation/presentation/slides/slides.tex
@@ -0,0 +1,15 @@
+% !TEX root = presentation.tex
+\begin{frame}
+\titlepage
+\end{frame}
+%
+\section{Big $\mathcal{O}$}
+\input{slides/BigO.tex}
+\section{Strassen's Algorithm}
+\input{slides/strassen.tex}
+% \input{slides/nn.tex}
+\section{Measurements}
+\input{slides/meas.tex}
+% \input{slides/parcomp.tex}
+\section{How To Matrix Multiply}
+\input{slides/blas.tex}
diff --git a/buch/papers/multiplikation/presentation/slides/strassen.tex b/buch/papers/multiplikation/presentation/slides/strassen.tex
new file mode 100644
index 0000000..c3398d5
--- /dev/null
+++ b/buch/papers/multiplikation/presentation/slides/strassen.tex
@@ -0,0 +1,429 @@
+\begin{frame}
+  \frametitle{Strassen's Algorithm}
+            \includegraphics[page=1,width=\textwidth,height=0.8\textheight,keepaspectratio]{../papers/Strassen_original_1969.pdf}
+      \includegraphics[page=2,width=\textwidth,height=0.8\textheight,keepaspectratio]{../papers/Strassen_original_1969.pdf}      \includegraphics[page=3,width=\textwidth,height=0.8\textheight,keepaspectratio]{../papers/Strassen_original_1969.pdf}
+          \end{frame}
+
+\begin{frame}
+  \frametitle{Strassen's Algorithm}
+  \centering
+  \large
+\onslide<1->{
+  $
+  \mathbf{A B = C}
+  $
+}
+
+\onslide<2->{
+
+
+\medskip
+  $
+  \begin{bmatrix}
+  A_{11} & A_{12}\\
+  A_{21} & A_{22}
+  \end{bmatrix}
+  \begin{bmatrix}
+  B_{11} & B_{12}\\
+  B_{21} & B_{22}
+  \end{bmatrix}
+  =
+  \begin{bmatrix}
+  C_{11} & C_{12}\\
+  C_{21} & C_{22}
+  \end{bmatrix}
+  $
+  }
+
+
+  \onslide<3->{
+
+\medskip
+$
+C_{11} = A_{11} \cdot B_{11} + A_{12} \cdot B_{21}
+$
+
+$
+C_{12} = A_{11} \cdot B_{12} + A_{12} \cdot B_{22}
+$
+
+$
+C_{21} = A_{21} \cdot B_{11} + A_{22} \cdot B_{21}
+$
+
+$
+C_{22} = A_{21} \cdot B_{12} + A_{22} \cdot B_{22}
+$
+}
+\end{frame}
+
+\input{slides/algo.tex}
+
+
+
+\begin{frame}
+  \frametitle{Strassen's Algorithm}
+  \begin{columns}
+    \begin{column}{0.5\textwidth}
+      \onslide<1->{
+      \large
+      \begin{math}
+      \begin{aligned}
+      \text{I}   &= (A_{11} + A_{22}) \cdot (B_{11} + B_{22}) \\
+      \text{II}  &= (A_{21} + A_{22}) \cdot B_{11} \\
+      \text{III} &= A_{11} \cdot (B_{12}-B_{22}) \\
+      \text{IV}  &= A_{22} \cdot (-B_{11}+B_{21}) \\
+      \text{V}   &= (A_{11} + A_{12}) \cdot B_{22} \\
+      \text{VI}  &= (-A_{11} + A_{21}) \cdot (B_{11} + B_{12}) \\
+      \text{VII} &= (A_{12} - A_{22}) \cdot (B_{21} + B_{22}) \\
+      \end{aligned}
+      \end{math}
+      }
+    \end{column}
+
+    \begin{column}{0.5\textwidth}
+        \onslide<2->{
+        \large
+        \begin{math}
+        \begin{aligned}
+        C_{11} &= \text{I} + \text{IV} - \text{V} + \text{VII} \\
+        C_{21} &= \text{II} + \text{IV} \\
+        C_{12} &= \text{III} + \text{V}\\
+        C_{22} &= \text{I} + \text{III} - \text{II} + \text{VI} \\
+        \end{aligned}
+        \end{math}
+        }
+    \end{column}
+\end{columns}
+
+\onslide<3->{
+
+\bigskip
+\centering
+\tiny
+\begin{math}
+\begin{aligned}
+  C_{11} &= (A_{11} + A_{22}) \cdot (B_{11} + B_{22}) + A_{22} \cdot (-B_{11}+B_{21}) - (A_{11} + A_{12}) \cdot B_{22} + (A_{12} - A_{22}) \cdot (B_{21} + B_{22}) \\
+  C_{11} &= A_{11}B_{11} + A_{11}B_{22} + A_{22}B_{11} + A_{22}B_{22} -A_{22}B_{11}+A_{22}B_{21} - A_{11}B_{22} - A_{12}B_{22}+ A_{12}B_{21} + A_{12}B_{22} - A_{22}B_{21} - A_{22}B_{22} \\
+  C_{11} &= A_{11}B_{11} + A_{12}B_{21}
+\end{aligned}
+\end{math}
+}
+
+\end{frame}
+
+
+\begin{frame}
+\begin{adjustbox}{width=\textwidth}
+\begin{tikzpicture}[ampersand replacement=\&]
+
+  \foreach \i in {1,...,4}
+  {
+  \small{
+    \matrix (X\i)[matrix of math nodes,nodes in empty cells,
+              nodes = {draw, minimum size=10mm,
+                       anchor=center,
+                       inner sep=0pt, outer sep=0pt},
+              column sep=-\pgflinewidth,
+              row sep=-\pgflinewidth,
+              ] at (0,-\i*5)
+   {
+   A_{11}B_{11} \& A_{12}B_{11} \& A_{21}B_{11} \& A_{22}B_{11} \\
+   A_{11}B_{21} \& A_{12}B_{21} \& A_{21}B_{21} \& A_{22}B_{21} \\
+   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,
+                nodes = {draw, minimum size=10mm,
+                         anchor=center,
+                         inner sep=0pt, outer sep=0pt},
+                column sep=-\pgflinewidth,
+                row sep=-\pgflinewidth,
+                ] at (\j*5,-\i*5)
+     {
+     \& \& \& \\
+     \& \& \& \\
+     \& \& \& \\
+     \& \& \& \\
+     };
+   }
+ }
+
+\huge{
+ \node at (-3,-20)  {$C_{22}=$};
+ \node at (-3,-15) {$C_{21}=$} ;
+ \node at (-3,-10) {$C_{12}=$} ;
+ \node at (-3,-5) {$C_{11}=$} ;
+
+ \node at (5,-2)  {I};
+ \node at (10,-2)  {II};
+ \node at (15,-2)  {III};
+ \node at (20,-2)  {IV};
+ \node at (25,-2)  {V};
+ \node at (30,-2)  {VI};
+ \node at (35,-2)  {VII};
+ }
+
+
+ \node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=green, fit=(X1-1-1)] {};
+ \node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=green, fit=(X1-2-2)] {};
+ \node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=green, fit=(X2-3-1)] {};
+ \node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=green, fit=(X2-4-2)] {};
+ \node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=green, fit=(X3-1-3)] {};
+ \node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=green, fit=(X3-2-4)] {};
+ \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)] {};
+
+ \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=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=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)] {};
+ \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)] {};
+ \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)] {};
+ \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)] {};
+\end{tikzpicture}
+\end{adjustbox}
+\end{frame}
+
+
+\begin{frame}
+  \frametitle{Strassen's Algorithm}
+  \begin{columns}
+    \begin{column}{0.5\textwidth}
+      \large
+      \begin{math}
+      \begin{aligned}
+      \text{I}   &= (A_{11} + A_{22}) \cdot (B_{11} + B_{22}) \\
+      \text{II}  &= (A_{21} + A_{22}) \cdot B_{11} \\
+      \text{III} &= A_{11} \cdot (B_{12}-B_{22}) \\
+      \text{IV}  &= A_{22} \cdot (-B_{11}+B_{21}) \\
+      \text{V}   &= (A_{11} + A_{12}) \cdot B_{22} \\
+      \text{VI}  &= (-A_{11} + A_{21}) \cdot (B_{11} + B_{12}) \\
+      \text{VII} &= (A_{12} - A_{22}) \cdot (B_{21} + B_{22}) \\
+      \end{aligned}
+      \end{math}
+
+    \end{column}
+
+    \begin{column}{0.5\textwidth}
+        \large
+        \begin{math}
+        \begin{aligned}
+        C_{11} &= \text{I} + \text{IV} - \text{V} + \text{VII} \\
+        C_{21} &= \text{II} + \text{IV} \\
+        C_{12} &= \text{III} + \text{V}\\
+        C_{22} &= \text{I} + \text{III} - \text{II} + \text{VI} \\
+        \end{aligned}
+        \end{math}
+
+    \end{column}
+\end{columns}
+\end{frame}
+
+
+
+\begin{frame}
+  \frametitle{Strassen's Algorithm}
+
+\begin{columns}
+  \begin{column}{0.5\textwidth}
+\large
+\begin{math}
+\begin{aligned}
+\text{\textbf{I}}   &= (\mathbf{A_{11}} + \mathbf{A_{22}}) \cdot (\mathbf{B_{11}} + \mathbf{B_{22}}) \\
+\text{\textbf{II}}  &= (\mathbf{A_{21}} + \mathbf{A_{22}}) \cdot \mathbf{B_{11}} \\
+\text{\textbf{III}} &= \mathbf{A_{11}} \cdot (\mathbf{B_{12}}-\mathbf{B_{22}}) \\
+\text{\textbf{IV}}  &= \mathbf{A_{22}} \cdot (-\mathbf{B_{11}}+\mathbf{B_{21}}) \\
+\text{\textbf{V}}   &= (\mathbf{A_{11}} + \mathbf{A_{12}}) \cdot \mathbf{B_{22}} \\
+\text{\textbf{VI}}  &= (-\mathbf{A_{11}} + \mathbf{A_{21}}) \cdot (\mathbf{B_{11}} + \mathbf{B_{12}}) \\
+\text{\textbf{VII}} &= (\mathbf{A_{12}} - \mathbf{A_{22}}) \cdot (\mathbf{B_{21}} + \mathbf{B_{22}}) \\
+\end{aligned}
+\end{math}
+
+\end{column}
+
+\begin{column}{0.5\textwidth}
+  \large
+  \begin{math}
+  \begin{aligned}
+  \mathbf{C_{11}} &= \text{\textbf{I}} + \text{\textbf{IV}} - \text{\textbf{V}} + \text{\textbf{VII}} \\
+  \mathbf{C_{21}} &= \text{\textbf{II}} + \text{\textbf{IV}} \\
+  \mathbf{C_{12}} &= \text{\textbf{III}} + \text{\textbf{V}}\\
+  \mathbf{C_{22}} &= \text{\textbf{I}} + \text{\textbf{III}} - \text{\textbf{II}} + \text{\textbf{VI}} \\
+  \end{aligned}
+  \end{math}
+
+\end{column}
+\end{columns}
+
+\end{frame}
+
+\begin{frame}
+  \frametitle{Algorithm}
+  \onslide<1->{
+
+  \scalebox{0.45}{\parbox{\linewidth}{
+    \begin{algorithm}[H]\caption{Strassen Matrix Multiplication}
+      \setlength{\lineskip}{7pt}
+      \begin{algorithmic}[1]
+        \Function{strassen}{$\textbf{A}, \textbf{B}, n$}
+        \If{$n = 2$}
+        \State  $ \mathbf{C} \gets zeros((n, n))$
+        \State $P  \gets (A[0][0]+A[1][1])\cdot( B[0][0]+B[1][1])$
+        \State   $Q  \gets (A[1][0]+A[1][1])\cdot B[0][0]$
+        \State   $R  \gets A[0][0]\cdot (B[0][1]-B[1][1])$
+        \State   $S  \gets A[1][1]\cdot (B[1][0]-B[0][0])$
+        \State   $T  \gets (A[0][0]+A[0][1])\cdot B[1][1]$
+        \State   $U  \gets (A[1][0]-A[0][0])\cdot (B[0][0]+B[0][1])$
+        \State   $V  \gets (A[0][1]-A[1][1])\cdot (B[1][0]+B[1][1])$
+        \State   $C[0][0]  \gets P+S-T+V$
+        \State   $C[0][1]  \gets R+T$
+        \State   $C[1][0]  \gets Q+S$
+        \State   $C[1][1]  \gets P+R-Q+U$
+        \Else
+      \State  $ m \gets n/2$
+  \State $\mathbf{A11}, \mathbf{A12}, \mathbf{A21}, \mathbf{A22} \gets \mathbf{A}[:m][:m], \mathbf{A}[:m][m:], \mathbf{A}[m:][:m], \mathbf{A}[m:][m:]$
+  \State $\mathbf{B11}, \mathbf{B12}, \mathbf{B21}, \mathbf{B22} \gets \mathbf{B}[:m][:m], \mathbf{B}[:m][m:], \mathbf{B}[m:][:m], \mathbf{B}[m:][m:]$
+
+  \State $ \mathbf{P} \gets \text{strassen}((\mathbf{A11}+ \mathbf{A22}),(\mathbf{B11}+\mathbf{B22}), m)$
+  \State $ \mathbf{Q} \gets \text{strassen}((\mathbf{A21}+ \mathbf{A22}), \mathbf{B11},m)$
+  \State $ \mathbf{R} \gets \text{strassen}( \mathbf{A11},(\mathbf{B12}-  \mathbf{B22}),m)$
+  \State $ \mathbf{S} \gets \text{strassen}( \mathbf{A22},(\mathbf{B21}-  \mathbf{B11}),m)$
+  \State $ \mathbf{T} \gets \text{strassen}((\mathbf{A11}+ \mathbf{A12}), \mathbf{B22},m)$
+  \State $ \mathbf{U} \gets \text{strassen}((\mathbf{A21}- \mathbf{A11}),(\mathbf{B11}+\mathbf{B12}),m)$
+  \State $ \mathbf{V} \gets \text{strassen}((\mathbf{A12}- \mathbf{A22}),(\mathbf{B21}+\mathbf{B22}),m)$
+
+
+
+  \State   $\mathbf{C11}  \gets \mathbf{P+S-T+V}$
+  \State   $\mathbf{C12}  \gets \mathbf{R+T}$
+  \State   $\mathbf{C21}  \gets \mathbf{Q+S}$
+  \State   $\mathbf{C22}  \gets \mathbf{P+R-Q+U}$
+  \State $  C \gets vstack((hstack((C11, C12)), hstack((C21, C22))))$
+
+        \EndIf
+        \State \textbf{return} $\textbf{C}$
+
+       \EndFunction
+      \end{algorithmic}
+  \end{algorithm}
+    }}}
+%     \[
+%   \mathcal{T}(n) = \left\{\begin{array}{lr}
+%       1, & \text{if}  n \leq 2\\
+%       7 \mathcal{T}(\frac{n}{2}) + n^2, & \text{if} n > 2\\
+%       \end{array}\right\}
+% \]
+\only<2>{
+    $
+    \mathcal{T}(n) =
+    \begin{cases}
+      1  & \text{if }  n \leq 2\\
+      7 \cdot \mathcal{T}(\frac{n}{2}) + n^2  & \text{if }  n > 2
+    \end{cases} = \mathcal{O}(n^{\log_2 7})$
+
+}
+\only<3>{
+    $
+    \mathcal{T}(n) =
+    \begin{cases}
+      1  & \text{if }  n \leq 2\\
+      7 \cdot \mathcal{T}(\frac{n}{2}) + n^2  & \text{if }  n > 2
+    \end{cases} = \mathcal{O}(n^{2.81})$
+
+}
+
+\end{frame}
+
+\begin{frame}
+  \frametitle{Algorithm}
+  \onslide<1->{
+
+  \scalebox{0.45}{\parbox{\linewidth}{
+    \begin{algorithm}[H]\caption{Strassen Matrix Multiplication}
+      \setlength{\lineskip}{7pt}
+      \begin{algorithmic}[1]
+        \Function{MM}{$\textbf{A}, \textbf{B}, n$}
+        \If{$n = 2$}
+        \State  $ \mathbf{C} \gets zeros((n, n))$
+                \State  $C[0, 0] \gets  A[0][0]*B[0][0]+A[0][1]*B[1][0]$
+                \State  $C[0, 1] \gets  A[0][0]*B[0][1]+A[0][1]*B[1][1]$
+                \State  $C[1, 0] \gets  A[1][0]*B[0][0]+A[1][1]*B[1][0]$
+                \State  $C[1, 1] \gets  A[1][0]*B[0][1]+A[1][1]*B[1][1]$
+        \Else
+      \State  $ m \gets n/2$
+  \State $\mathbf{A11}, \mathbf{A12}, \mathbf{A21}, \mathbf{A22} \gets \mathbf{A}[:m][:m], \mathbf{A}[:m][m:], \mathbf{A}[m:][:m], \mathbf{A}[m:][m:]$
+  \State $\mathbf{B11}, \mathbf{B12}, \mathbf{B21}, \mathbf{B22} \gets \mathbf{B}[:m][:m], \mathbf{B}[:m][m:], \mathbf{B}[m:][:m], \mathbf{B}[m:][m:]$
+
+    \State $\mathbf{C11} \gets \text{MM}(\mathbf{A11}, \mathbf{B11}) + \text{MM}(\mathbf{A12}, \mathbf{B21})$
+    \State $\mathbf{C12} \gets \text{MM}(\mathbf{A11},\mathbf{B12}) + \text{MM}(\mathbf{A12},\mathbf{B22})$
+    \State $\mathbf{C21} \gets \text{MM}(\mathbf{A21}, \mathbf{B11}) + \text{MM}(\mathbf{A22}, \mathbf{B21})$
+    \State $\mathbf{C22} \gets \text{MM}(\mathbf{A21}, \mathbf{B12}) + \text{MM}(\mathbf{A22}, \mathbf{B22})$
+    \State $  C \gets vstack((hstack((C11, C12)), hstack((C21, C22))))$
+
+        \EndIf
+        \State \textbf{return} $\textbf{C}$
+
+       \EndFunction
+      \end{algorithmic}
+  \end{algorithm}
+  \bigskip
+  \bigskip
+  \bigskip
+  \bigskip
+  \bigskip
+    }}}
+
+\only<2>{
+
+
+    $
+    \mathcal{T}(n) =
+    \begin{cases}
+      1  & \text{if }  n \leq 2\\
+      8 \cdot \mathcal{T}(\frac{n}{2}) + n^2  & \text{if }  n > 2
+    \end{cases} = \mathcal{O}(n^{\log_2 8})$
+
+}
+\only<3>{
+    $
+    \mathcal{T}(n) =
+    \begin{cases}
+      1  & \text{if }  n \leq 2\\
+      8 \cdot \mathcal{T}(\frac{n}{2}) + n^2  & \text{if }  n > 2
+    \end{cases} = \mathcal{O}(n^{3})$
+
+}
+
+\end{frame}