\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}