Strassen Algorithm/Examples

Examples of Use of the Strassen Algorithm

Let $\mathbf A$ and $\mathbf B$ be square matrices of order $2$:

$\ds \mathbf A$

$=$

$\ds \begin {pmatrix} a_{11} & a_{12} \\ a_{21} & a_{22} \end {pmatrix}$

$\ds \mathbf B$

$=$

$\ds \begin {pmatrix} b_{11} & b_{12} \\ b_{21} & b_{22} \end {pmatrix}$

Let $\mathbf C = \mathbf {A B}$.

Then:

$C = \begin {pmatrix} p_1 + p_4 - p_5 + p_7 & p_3 + p_5 \\ p_2 + p_4 & p_1 + p_3 - p_2 + p_6 \end {pmatrix}$

where:

$\ds p_1$

$=$

$\ds \paren {a_{11} + a_{22} } \paren {b_{11} + b_{22} }$

$\ds p_2$

$=$

$\ds \paren {a_{21} + a_{22} } b_{11}$

$\ds p_3$

$=$

$\ds a_{11} \paren {b_{12} - b_{22} }$

$\ds p_4$

$=$

$\ds a_{22} \paren {b_{21} - b_{11} }$

$\ds p_5$

$=$

$\ds \paren {a_{11} + a_{12} } b_{22}$

$\ds p_6$

$=$

$\ds \paren {a_{21} - a_{11} } \paren {b_{11} + b_{12} }$

$\ds p_7$

$=$

$\ds \paren {a_{12} - a_{22} } \paren {b_{21} + b_{22} }$

It is seen that the Strassen algorithm uses only $7$ multiplication operations as opposed to the usual $8$.