% This is not TeX, it's -*- LaTeX -*- (for emacs)
\documentclass{beamer}
% Copyright by Marco Bodrato, 2010
% Released under the Creative Common 3.0 BY-NC-SA licence, available at
% http://creativecommons.org/licenses/by-nc-sa/3.0/
\usepackage{hyperref}
\usepackage{xcolor}
\usepackage{enumerate}
\usepackage{beamerthemesplit}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsfonts}

\usepackage{graphicx}
\usepackage{arydshln}

\usetheme{Copenhagen}
\usenavigationsymbolstemplate{}

%%%%%% Inizio font cirillico %%%%%%
\usepackage[OT2,OT1]{fontenc}
\newcommand\cyr{%
  \renewcommand\rmdefault{wncyr}%
  \renewcommand\sfdefault{wncyss}%
  \renewcommand\encodingdefault{OT2}%
  \normalfont
  \selectfont}
\DeclareTextFontCommand{\textcyr}{\cyr} 
%%%%%%% Fine font cirillico %%%%%%%

\setlength\dashlinedash{.4pt}
\setlength\dashlinegap{1.2pt}

% oggetti matematici
\def\NN{{\ensuremath{\mathbb{N}}}}
\def\ZZ{{\ensuremath{\mathbb Z}}}
\def\RR{{\ensuremath{\mathbb R}}}
\def\u{{{\mathbf 1}}}
\def\N{\mathbb{N}}
\def\setZ{\mathbb{Z}}
\def\R{\mathbb{R}}
\def\K{\mathbb{K}}
\def\F{\mathbb{F}}
\def\T{{{\cyr Toom}}}
\def\TC{\T-Cook}

\newcommand{\per}{\ensuremath{\cdot}}
\newcommand{\zsupz}[1][p]{{\ensuremath{\ZZ_{\!/\!#1\ZZ}}}}
\newcommand{\pol}[1][p]{\mathfrak{#1}}
\newcommand{\vet}[1]{\overline{#1}}
\newcommand{\hex}[1]{\mathrm{#1}}
\newcommand{\zsunz}{\zsupz[n]}
\newcommand{\zsuppz}{\zsupz[p^2]}
\newcommand{\GF}[1][2]{{\ensuremath{\mathrm{GF}\!\left(#1\right)}}}
\newcommand{\GFx}[1][2]{{\ensuremath{\GF[#1]\!\left[x\right]}}}
\newcommand{\Zx}{{\ensuremath{\setZ\left[x\right]}}}
\newcommand{\Ogr}{\mathrm{O}}
\newcommand{\opi}{\mathrm{o}}
\newcommand{\evide}[1]{\textcolor{green!70!black}{#1}}
\newcommand{\bluco}[1]{\textcolor{blue!70!black}{#1}}
\newcommand{\grigio}[1]{\textcolor{white!60!black}{#1}}

\begin{document}

\title[Strassen-like Matrix Squaring and Chain Products]{A Strassen-like Matrix Multiplication}
\subtitle{Suited for Squaring and Higher Power Computation}
\author[Marco Bodrato \ \ \ \ \ \ \ \ \ \ \ \ \ \ (0xC1A000B0)]{Marco Bodrato}

\date[ISSAC 2010]{ISSAC 2010 - July 28$^\mathrm{th}$}

\subject{Fast matrix squaring and power computation.}
\keywords{Polynomial matrix, exponentiation, optimal squaring, fast
  multiplication, recursive algorithm.}

\frame{\titlepage}
\part{Symbolic}
\frame[label=indice]{\tableofcontents
\hfill\hyperlink{appendices}{\beamergotobutton{see appendices}}
}

\section{A new Strassen-like sequence for matrix squaring}
\frame{
  \frametitle{Matrix $2\times2$ product \only<1>{\dots}\only<2>{and squaring}}
  We start from \only<1>{two matrices}\only<2>{one matrix}
  $A\only<1>{,B} \in M_{2\times2}$

  and we need the \only<1>{product}\only<2>{square of it}:
  $$ M_{2\times2} \ni C =
  \begin{pmatrix}
    C_{11}&C_{12}\\
    C_{21}&C_{22}
  \end{pmatrix}
  =
  \onslide<2>{
    \begin{pmatrix}
      A_{11}&A_{12}\\
      A_{21}&A_{22}
    \end{pmatrix}^2
  }
  \onslide<1>{\hspace{-23.5mm}
    \begin{pmatrix}
      A_{11}&A_{12}\\
      A_{21}&A_{22}
    \end{pmatrix}
    \begin{pmatrix}
      B_{11}&B_{12}\\
      B_{21}&B_{22}
    \end{pmatrix}
  }
  $$
  \begin{block}{Na\"ive \hfill vs. \hfill Strassen}
    The na\"ive algorithm requires 8 multiplications:
    \only<2>{\hfill\hyperlink{commutativesquaring}{\beamergotobutton{commutative case}}}
    $$ C =
    \begin{pmatrix}
      \alert<2>{A_{11}\only<1>{B}\only<2>{A}_{11}}+A_{12}\only<1>{B}\only<2>{A}_{21}&A_{11}\only<1>{B}\only<2>{A}_{12}+A_{12}\only<1>{B}\only<2>{A}_{22}\\
      A_{21}\only<1>{B}\only<2>{A}_{11}+A_{22}\only<1>{B}\only<2>{A}_{21}&A_{21}\only<1>{B}\only<2>{A}_{12}+\alert<2>{A_{22}\only<1>{B}\only<2>{A}_{22}}
    \end{pmatrix} ;
    $$
    \hfill thanks to Strassen, we can use only 7.
  \end{block}
}
\subsection{Multiplication algorithms and complexity}
\frame{
  \frametitle{Recall Strassen method}

  Strassen's method trades one multiplication with many pre- and post-
  linear combinations, it does not assume commutativity and it can be
  used recursively.

  \[
  \left\{
    \begin{array}{lcl}
      P_1&=&(A_{21}+A_{22})B_{11}\\
      P_2&=&A_{11}(B_{12}-B_{22})\\
      P_3&=&(A_{12}-A_{22})(B_{21}+B_{22})\\
      P_4&=&(A_{11}+A_{12})B_{22}\\
      P_5&=&A_{22}(B_{21}-B_{11})\\
      P_6&=&(A_{21}-A_{11})(B_{11}+B_{12})\\
      P_7&=&\alert{(A_{11}+A_{22})(B_{11}+B_{22})}\\
    \end{array}
    \right.
  \left\{
    \begin{array}{lcl}
      C_{11}&=&P_7-P_4+P_5+P_3\\
      C_{12}&=&P_2+P_4\\
      C_{21}&=&P_1+P_5\\
      C_{22}&=&P_7+P_2-P_1+P_6\\
    \end{array}
  \right.
  \]
}
\frame{
  \frametitle{Strassen-like $2\times2$ matrix multiplication algorithm}
  \begin{block}{Number of operations, for the product of $2\times2$ matrices}
    \begin{tabular}{l:rrr}
      \bf Method & \bf additions & \bf multiplications & \grigio{\em complexity}
      \\\hdashline
      Na\"ive & 4 & 8 & \grigio{$d^3$}\\
      Strassen's & 18 & 7& \grigio{$7d^{\log_27}$}\\
      Winograd's & \bf 15 & \bf 7& \grigio{$6d^{\log_27}$}\\
    \end{tabular}
  \end{block}
  Winograd variant {\bf is} optimal for $2\times2$ multiplication.

  That's why research on $2\times2$ matrix product basically stopped
  \grigio{(except some works on scheduling)},
  the focus moved on bigger matrices.
}
\subsection{The new proposed sequence}
\frame{
  \frametitle{The search for a new sequence}
  \begin{alertblock}{What about matrix squaring?}
    \begin{tabular}{l:rrr}
      \bf Squaring method & \bf additions & \bf multiplications & \bf squaring
      \\\hdashline
      Na\"ive & 4 & 6 & 2\\
      Strassen's & 13 & 6& 1\\
      Winograd's & 15 & 6& 1\\
    \end{tabular}
  \end{alertblock}

  Winograd's variant {\bf is not} optimal for  $2\times2$ squaring.

  That's why we started the search for a new sequence.

  The sequence was searched for $2\times2$ matrices in \GF, as a
  sequence of additions and multiplications only, then lifted to $\ZZ$.

  We can not use commutativity.

  We are {\bf not} trying to reduce the big-O complexity.

}
\frame[label=newseq,squeeze]{
  \frametitle{The new sequence for $C=AB$}
  \framesubtitle{Symmetry!\hspace{80mm}%this \hspace followed by \hfill is a nonsense...
    \hfill\hyperlink{wino}{\beamergotobutton{look at Winograd's}}}
  \begin{exampleblock}{}
  \vspace*{-4mm}
  \[
  A\!=\!\begin{pmatrix}\!A_{11}&\!\!A_{12}\\\!A_{21}&\!\!A_{22}\end{pmatrix}\!
  \left\{\!\!
  \begin{array}{l@{}c@{}l}
    S_1&=&A_{22}+A_{12}\\
    S_2&=&A_{22}-A_{21}\\
    S_3&=&S_2+A_{12}\\
    S_4&=&S_3-A_{11}\\
  \end{array}
  \right.
  \ \bluco{
  B\!=\!\begin{pmatrix}\!B_{11}&\!\!B_{12}\\\!B_{21}&\!\!B_{22}\end{pmatrix}\!
  \left\{\!\!
  \begin{array}{l@{}c@{}l}
    T_1&=&B_{22}+B_{12}\\
    T_2&=&B_{22}-B_{21}\\
    T_3&=&T_2+B_{12}\\
    T_4&=&T_3-B_{11}\\
  \end{array}
  \right.}
  \]
  \end{exampleblock}

  \begin{block}{}
  \vspace*{-4mm}
  \[
  \left\{
  \begin{array}{lcl}
    P_1&=&\bluco{S_1T_1}\\
    P_2&=&\bluco{S_2T_2}\\
    P_3&=&\bluco{S_3T_3}\\
    P_4&=&\bluco{A_{11}B_{11}}\\
    P_5&=&A_{12}B_{21}\\
    P_6&=&S_4B_{12}\\
    P_7&=&A_{21}T_4\\
  \end{array}
  \right.\quad
  \left\{
  \begin{array}{lcl}
    U_1&=&P_3+P_5\\
    U_2&=&P_1-U_1\\
    U_3&=&U_1-P_2\\
    C_{11}&=&P_4+P_5\\
    C_{12}&=&U_3-P_6\\
    C_{21}&=&U_2-P_7\\
    C_{22}&=&P_2+U_2\\
  \end{array}
  \right.
  \leadsto C=\begin{pmatrix}C_{11}&C_{12}\\C_{21}&C_{22}\end{pmatrix}
  \]
  \end{block}
}
\subsection{Strassen-like squaring}
\frame[label=Strassen-algo]{
  \frametitle{What's new in the new sequence}
  The new sequence is:
  \begin{itemize}
  \item equivalent to Winograd's variant for plain product;
  \item symmetric;
  \item optimal for squaring;
    \onslide<2>{
    \begin{itemize}
    \item number of multiplications and squarings is minimal (7),
    \item number of multiplications not being squarings is minimal (3),
    \item because of symmetry pre-computations on the operand is halved.
    \end{itemize}
    }
  \end{itemize}
  \begin{alertblock}{}
    \begin{tabular}{@{}l:rrr@{}l@{}}
      {\bf Squaring method}&{\bf additions}&{\bf multiplications}&{\bf squaring}
      \\\hdashline
      Na\"ive & 4 & 6 & 2\\
      Strassen's & 13 & 6& 1\\
      Winograd's & 15 & 6& 1\\
      New sequence &{\bf 11}&
      \onslide<2>{$($}{\bf 3}&
      \onslide<2>{$+\qquad$}{\bf 4}&
      \onslide<2>{$)=7$}\\
    \end{tabular}
  \end{alertblock}
}
\frame{
  \frametitle{The new sequence for $C=A^2$}
  \begin{exampleblock}{}
  \[
  A=\begin{pmatrix}A_{11}&A_{12}\\A_{21}&A_{22}\end{pmatrix}
  \left\{
  \begin{array}{l@{}c@{}l}
    S_1&=&A_{22}+A_{12}\\
    S_2&=&A_{22}-A_{21}\\
    S_3&=&S_2+A_{12}\\
    S_4&=&S_3-A_{11}\\
  \end{array}
  \right.
  \]
  \end{exampleblock}

  \begin{block}{}
  \vspace*{-4mm}
  \[
  \left\{
  \begin{array}{lcl}
    P_1&=&S_1S_1\\
    P_2&=&S_2S_2\\
    P_3&=&S_3S_3\\
    P_4&=&A_{11}A_{11}\\
    P_5&=&\alert{A_{12}}\bluco{A_{21}}\\
    P_6&=&\evide{S_4}\alert{A_{12}}\\
    P_7&=&\bluco{A_{21}}\evide{S_4}\\
  \end{array}
  \right.\quad
  \left\{
  \begin{array}{lcl}
    U_1&=&P_3+P_5\\
    U_2&=&P_1-U_1\\
    U_3&=&U_1-P_2\\
    C_{11}&=&P_4+P_5\\
    C_{12}&=&U_3-P_6\\
    C_{21}&=&U_2-P_7\\
    C_{22}&=&P_2+U_2\\
  \end{array}
  \right.
  \leadsto C=\begin{pmatrix}C_{11}&C_{12}\\C_{21}&C_{22}\end{pmatrix}
  \]
  \end{block}
}
\frame{
  \frametitle{The three products\ldots}

  Thanks to symmetry, when dealing with the three products, we can
  keep on using a half the pre-computation on operands, and this is
  true for any recursion level.

  \begin{block}{}
  \[
  \left\{
  \begin{array}{lcl}
    P_5&=&\alert{A_{12}}\bluco{A_{21}}\\
    P_6&=&\evide{S_4}\alert{A_{12}}\\
    P_7&=&\bluco{A_{21}}\evide{S_4}\\
  \end{array}
  \right.
  \]
  \end{block}

  \grigio{Matrix multiplication is not commutative, but the sequence
    is symmetric}
}
\section{Chain product and power computation}
\subsection{Intermediate results}
\frame{
  \frametitle{Reduce linear operations for chain products}

  When one needs to compute $M^3$ or $M_1M_2M_3$, one usually need
  some intermediate results: $M^2M$, $(M_1M_2)M_3$.
  \pause
  \begin{block}{}
  \vspace*{-4mm}
  \[
  \begin{pmatrix}M_{11}&M_{12}\\M_{21}&M_{22}\end{pmatrix}
  \left\{
  \begin{array}{lcl}
    S_1&\leadsto&P_1\\
    S_2&\leadsto&P_2\\
    S_3&\leadsto&P_3\\
    S_4&\leadsto&P_4\\
    M_{11}&\leadsto&P_5\\
    M_{12}&\leadsto&P_6\\
    M_{21}&\leadsto&P_7\\
  \end{array}
  \onslide<2>{
  \right\}
  \begin{pmatrix}\widetilde{M}_{11}&\widetilde{M}_{12}\\\widetilde{M}_{21}&\alert{\widetilde{M}_{22}}\end{pmatrix}
  \left\{
  }
  \begin{array}{lcl}
    \widetilde{S}_1&\leadsto&\widetilde{P}_1\\
    \widetilde{S}_2&\leadsto&\widetilde{P}_2\\
    \widetilde{S}_3&\leadsto&\widetilde{P}_3\\
    \widetilde{S}_4&\leadsto&\widetilde{P}_4\\
    \widetilde{M}_{11}&\leadsto&\widetilde{P}_5\\
    \widetilde{M}_{12}&\leadsto&\widetilde{P}_6\\
    \widetilde{M}_{21}&\leadsto&\widetilde{P}_7\\
  \end{array}
  \right.
  \]
  \end{block}
  \onslide<3>{If we don't need the intermediate value, we should skip it.}
}
\subsection{Operation collapsing}
\frame{
  \frametitle{How to skip the unneeded values}
  The linear post- and pre- computation can collapse.
  \begin{block}{}
  \vspace*{-4mm}
  \[
  \left\{\begin{array}{l@{\,}r@{\,}l}
      \widetilde{M}_{11}&=&P_4+P_5\\
      \widetilde{M}_{12}&=&P_3-P_2-P_6+P_5\\
      \widetilde{S}_2&=&P_2+P_7\\
      \widetilde{S}_1&=&P_1-P_6\\\cdashline{1-3}
      \\[-2.8mm]
      \widetilde{S}_3&=&\widetilde{S}_2+\widetilde{M}_{12}\\
      \widetilde{M}_{21}&=&\widetilde{S}_1-\widetilde{S}_3\\
      \widetilde{S}_4&=&\widetilde{S}_3-\widetilde{M}_{11}\\
    \end{array}
  \right.\!\!\!\!\!
  \onslide<2>{
  \begin{array}{l}
    \left.
      \begin{array}{l}\\ \\ \\ \\
      \end{array}
    \right\} \mathrm{Depending\ on\ products}\\ \\[-2mm]
    \left.
      \begin{array}{l}\\ \\ \\
      \end{array}
    \right\} \mathrm{Depending\ on\ other\ values}
  \end{array}
  }
  \]
  \vspace*{-4mm}
  \end{block}
  Before we had $7+4=11$ operations, now we have 9.

  \onslide<2>{Moreover we can group operations \ldots
  }
}
\subsection{Intermediate representation}
\frame{
  \frametitle{How to save linear operations}
  \framesubtitle{with no more memory needs}
  Before we had an unneeded value\onslide<2>{, now we have none.}

  \begin{block}{}
  \vspace*{-4mm}
  \[
  \begin{pmatrix}M_{11}&M_{12}\\M_{21}&M_{22}\end{pmatrix}
  \left\{
  \begin{array}{lcl}
    S_1&\leadsto&P_1\\
    S_2&\leadsto&P_2\\
    S_3&\leadsto&P_3\\
    S_4&\leadsto&P_4\\
    M_{11}&\leadsto&P_5\\
    M_{12}&\leadsto&P_6\\
    M_{21}&\leadsto&P_7\\
  \end{array}
  \right\}
  \only<1>{
  \begin{pmatrix}\widetilde{M}_{11}&\widetilde{M}_{12}\\\widetilde{M}_{21}&\alert{\widetilde{M}_{22}}\end{pmatrix}\!
  }
  \only<2>{
  \begin{pmatrix}\widetilde{M}_{11}&\widetilde{M}_{12}\\\evide{\widetilde{S}_{2}}&\evide{\widetilde{S}_{1}}\end{pmatrix}
  }
  \left\{
  \begin{array}{lcl}
    \widetilde{S}_1&\leadsto&\widetilde{P}_1\\
    \widetilde{S}_2&\leadsto&\widetilde{P}_2\\
    \widetilde{S}_3&\leadsto&\widetilde{P}_3\\
    \widetilde{S}_4&\leadsto&\widetilde{P}_4\\
    \widetilde{M}_{11}&\leadsto&\widetilde{P}_5\\
    \widetilde{M}_{12}&\leadsto&\widetilde{P}_6\\
    \widetilde{M}_{21}&\leadsto&\widetilde{P}_7\\
  \end{array}
  \right.
  \]
  \end{block}
  \onslide<2>{
    We save 2 operations by replacing the sequences.

    Because of symmetry of the method we do not care of computation order:
    $(M_1M_2)M_3$ or $M_1(M_2M_3)$.
  }
}
\frame{
  \frametitle{Intermediate and standard representation are linked}

  The intermediate representation is obtained from the standard one
  with a simple linear function.
  \begin{exampleblock}{}
  \vspace*{-4mm}
  \[
  \begin{array}{l@{}c@{}c@{}l}
    \psi&\left(
    \begin{pmatrix}
      A_{11}&A_{12}\\
      A_{21}&A_{22}
    \end{pmatrix}
    \right)&=&
    \begin{pmatrix}
      A_{11}&A_{12}\\
      A_{22}-A_{21}\ &\ A_{22}+A_{12}
    \end{pmatrix}\\[4mm]
    \psi^{-1}&\left(
    \begin{pmatrix}
      A_{11}&A_{12}\\
      S_2&S_1
    \end{pmatrix}
    \right)&=&
    \begin{pmatrix}
      A_{11}&A_{12}\\
      {\bf (S_1\!-\!A_{12})}-S_2\ &\ {\bf (S_1\!-\!A_{12})}
    \end{pmatrix}
  \end{array}
  \]
  \end{exampleblock}
  \begin{block}{This representation is optimal}
    \begin{itemize}
    \item it uses as much memory as standard one;
    \item the number of linear operation for Strassen-like
      multiplications is minimal.
    \end{itemize}
  \end{block}
  It's linear: it can be used for general polynomial computations too.
}
\section{Conclusions}
\subsection{Timings}
\frame{
  \frametitle{Matrix-Matrix Multiplication}
  \framesubtitle{Time ratio with respect to na\"ive multiplication ($2\times2$)}
  \vspace*{-5mm}
  \begin{center}
    \leavevmode
    \hspace*{-10mm}\includegraphics[scale=0.9]{mat1}
  \end{center}
}
\frame{
  \frametitle{Matrix Squaring}
  \framesubtitle{Time ratio with respect to na\"ive squaring ($2\times2$)}
  \vspace*{-4mm}
  \begin{center}
    \leavevmode
    \hspace*{-9mm}\includegraphics[scale=0.8]{mat2}
  \end{center}
}
\subsection{Implementations}
\frame{
  \frametitle{Current implementations of the new sequence}
  \begin{enumerate}
  \item M4RI: for big matrices in \GF\ \grigio{(early 2009)};
  \item GMP: for $2\times2$ matrices, \grigio{(used in HGCD code)};
  \item {\tt fastmm} library: matrices with float entries \grigio{(licence problems)};
  \end{enumerate}
  None of them implement chain product nor any trick for powers,
  nevertheless they give some small but measurable improvement with
  respect to previous Strassen-Winograd implementations.

  \grigio{(There are others good side-effects of symmetry)}
}
\subsection{Final considerations}
\frame{
  \frametitle{Conclusions}

  A new Strassen-like sequence was proposed. It is:
  \begin{itemize}
  \item symmetric;
  \item optimal for plain product (not new);
  \item optimal for squaring;
  \item optimal for chain products.
  \end{itemize}

  Software implementation is as easy as Winograd's variant.

  \bluco{Consider implementing it if you need a variant of Strassen.}

}
\frame{
  \frametitle{That's all !}
\begin{center}
  Thank you very much for your kind attention

  \vspace{12mm}
  \alert{\Large Questions?}

  \vspace{22mm}
  \footnotesize \grigio{Presentation will be available on the web:
    \href{http://bodrato.it/papers/\#ISSAC2010}{http://bodrato.it/papers/\#ISSAC2010},\\
    released under a \href{http://creativecommons.org/licenses/by-nc-sa/3.0/}{CreativeCommons BY-NC-SA licence. \includegraphics[width=1cm]{cc.png}}\\
\
\\
    \href{http://marco.bodrato.it/papers/Bodrato2010-StrassenLikeMatrixMultiplicationForSquares.pdf}{Full paper too is available on web.}}
\end{center}
}

\appendix
\part{Appendices}
\frame[label=appendices]{\tableofcontents
\hfill\hyperlink{indice}{\beamerreturnbutton{back to index}}
}

\section{Some more details}
\subsection{Commutative matrix squaring}
\frame[label=commutativesquaring]{
  \frametitle{Matrix $2\times2$ squaring, exploiting commutativity}

  \begin{block}{The simple formula for $2\times2$ matrices}
    $$
    \begin{pmatrix}
      a&b\\c&d
    \end{pmatrix}^2=
    \begin{pmatrix}
      a^2+\evide{bc}&b\textcolor{blue}{(a+d)}\\
      c\textcolor{blue}{(a+d)}&d^2+\evide{bc}
    \end{pmatrix}
    $$
  \end{block}
  It can be generalised obtaining:
  \[
  d \ \mathrm{squares,}\,
  \alert{d^3}\!-d^2\!-\binom{d}{2} \ \mathrm{products,}\, 
  \alert{d^3}\!-d^2\!-\binom{d}{2} \ \mathrm{additions,}
  \]
  but it is fast only for $2\times2$ or $3\times3$ matrices.
}
\subsection{Winograd's variant}
\frame[label=wino]{
  \frametitle{Winograd's variant}
  \framesubtitle{No symmetry\ldots\hspace{70mm}%this \hspace followed by \hfill is a nonsense...
    \hfill\hyperlink{newseq}{\beamerreturnbutton{back to new sequence}}}
  \begin{exampleblock}{}
  \vspace*{-4mm}
  \[
  A\!=\!\begin{pmatrix}\!A_{11}&\!\!A_{12}\\\!A_{21}&\!\!A_{22}\end{pmatrix}\!
  \left\{\!\!
  \begin{array}{l@{}c@{}l}
    S_1&=&A_{21}+A_{22}\\
    S_2&=&S_1-A_{11}\\
    S_3&=&A_{11}-A_{21}\\
    S_4&=&A_{12}-S_2\\
  \end{array}
  \right.
  \ 
  B\!=\!\begin{pmatrix}\!B_{11}&\!\!B_{12}\\\!B_{21}&\!\!B_{22}\end{pmatrix}\!
  \left\{\!\!
  \begin{array}{l@{}c@{}l}
    T_1&=&B_{12}-B_{11}\\
    T_2&=&B_{22}-T_1\\
    T_3&=&B_{22}-B_{12}\\
    T_4&=&B_{21}-T_2\\
  \end{array}
  \right.
  \]
  \end{exampleblock}

  \begin{block}{}
  \vspace*{-4mm}
  \[
  \left\{
  \begin{array}{lcl}
    P_1&=&\bluco{A_{11}B_{11}}\\
    P_2&=&A_{12}B_{21}\\
    P_3&=&S_1T_1\\
    P_4&=&S_2T_2\\
    P_5&=&S_3T_3\\
    P_6&=&S_4B_{22}\\
    P_7&=&A_{22}T_4
  \end{array}
  \right.\quad
  \left\{
  \begin{array}{lcl}
    U_1&=&P_1+P_4\\
    U_2&=&U_1+P_5\\
    U_3&=&U_1+P_3\\
    C_{11}&=&P_2+P_1\\
    C_{12}&=&U_3+P_6\\
    C_{21}&=&U_2+P_7\\
    C_{22}&=&U_3+P_5\\
  \end{array}
  \right.
  \leadsto C=\begin{pmatrix}C_{11}&C_{12}\\C_{21}&C_{22}\end{pmatrix}
  \]
  \end{block}
}
\end {document}

% LocalWords:  Strassen Strassen's Winograd's squarings
