diff options
Diffstat (limited to 'buch/papers/multiplikation/presentation/slides')
| -rw-r--r-- | buch/papers/multiplikation/presentation/slides/algo.tex | 111 | ||||
| -rw-r--r-- | buch/papers/multiplikation/presentation/slides/bigO.tex | 251 | ||||
| -rw-r--r-- | buch/papers/multiplikation/presentation/slides/blas.tex | 18 | ||||
| -rw-r--r-- | buch/papers/multiplikation/presentation/slides/conclusuion.tex | 0 | ||||
| -rw-r--r-- | buch/papers/multiplikation/presentation/slides/logo.pdf | bin | 0 -> 8987 bytes | |||
| -rw-r--r-- | buch/papers/multiplikation/presentation/slides/meas.tex | 42 | ||||
| -rw-r--r-- | buch/papers/multiplikation/presentation/slides/nn.tex | 97 | ||||
| -rw-r--r-- | buch/papers/multiplikation/presentation/slides/parcomp.tex | 66 | ||||
| -rw-r--r-- | buch/papers/multiplikation/presentation/slides/slides.tex | 15 | ||||
| -rw-r--r-- | buch/papers/multiplikation/presentation/slides/strassen.tex | 429 |
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 Binary files differnew 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} |