Strassen Algorithm/Examples/Order 2

From ProofWiki
Jump to navigation Jump to search

Example 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$.


Proof

By definition of matrix multiplication:

$\mathbf {A B} = \begin {pmatrix} a_{11} b_{11} + a_{12} b_{21} & a_{11} b_{12} + a_{12} b_{22} \\ a_{21} b_{11} + a_{22} b_{21} & a_{21} b_{12} + a_{22} b_{22} \end {pmatrix}$


Hence to show that $\mathbf C = \mathbf {A B}$, we need to show that:

\(\text {(1)}: \quad\) \(\ds p_1 + p_4 - p_5 + p_7\) \(=\) \(\ds a_{11} b_{11} + a_{12} b_{21}\)
\(\text {(2)}: \quad\) \(\ds p_3 + p_5\) \(=\) \(\ds a_{11} b_{12} + a_{12} b_{22}\)
\(\text {(3)}: \quad\) \(\ds p_2 + p_4\) \(=\) \(\ds a_{21} b_{11} + a_{22} b_{21}\)
\(\text {(4)}: \quad\) \(\ds p_1 + p_3 - p_2 + p_6\) \(=\) \(\ds a_{21} b_{12} + a_{22} b_{22}\)


So:

\(\text {(1)}: \quad\) \(\ds p_1 + p_4 - p_5 + p_7\) \(=\) \(\ds \paren {a_{11} + a_{22} } \paren {b_{11} + b_{22} } + a_{22} \paren {b_{21} - b_{11} } - \paren {a_{11} + a_{12} } b_{22} + \paren {a_{12} - a_{22} } \paren {b_{21} + b_{22} }\)
\(\ds \) \(=\) \(\ds a_{11} b_{11} + a_{11} b_{22} + a_{22} b_{11} + a_{22} b_{22} + a_{22} b_{21} - a_{22} b_{11} - a_{11} b_{22} - a_{12} b_{22} + a_{12} b_{21} + a_{12} b_{22} - a_{22} b_{21} - a_{22} b_{22}\)
\(\ds \) \(=\) \(\ds a_{11} b_{11} + a_{12} b_{21}\)


\(\text {(2)}: \quad\) \(\ds p_3 + p_5\) \(=\) \(\ds a_{11} \paren {b_{12} - b_{22} } + \paren {a_{11} + a_{12} } b_{22}\)
\(\ds \) \(=\) \(\ds a_{11} b_{12} - a_{11} b_{22} + a_{11} b_{22} + a_{12} b_{22}\)
\(\ds \) \(=\) \(\ds a_{11} b_{12} + a_{12} b_{22}\)


\(\text {(3)}: \quad\) \(\ds p_2 + p_4\) \(=\) \(\ds \paren {a_{21} + a_{22} } b_{11} + a_{22} \paren {b_{21} - b_{11} }\)
\(\ds \) \(=\) \(\ds a_{21} b_{11} + a_{22} b_{11} + a_{22} b_{21} - a_{22} b_{11}\)
\(\ds \) \(=\) \(\ds a_{21} b_{11} + a_{22} b_{21}\)


\(\text {(4)}: \quad\) \(\ds p_1 + p_3 - p_2 + p_6\) \(=\) \(\ds \paren {a_{11} + a_{22} } \paren {b_{11} + b_{22} } + a_{11} \paren {b_{12} - b_{22} } - \paren {a_{21} + a_{22} } b_{11} + \paren {a_{21} - a_{11} } \paren {b_{11} + b_{12} }\)
\(\ds \) \(=\) \(\ds a_{11} b_{11} + a_{11} b_{22} + a_{22} b_{11} + a_{22} b_{22} + a_{11} b_{12} - a_{11} b_{22} - a_{21} b_{11} - a_{22} b_{11} + a_{21} b_{11} + a_{21} b_{12} - a_{11} b_{11} - a_{11} b_{12}\)
\(\ds \) \(=\) \(\ds a_{22} b_{22} + a_{21} b_{12}\)

Hence the result.

$\blacksquare$


Sources

Retrieved from "https://proofwiki.org/w/index.php?title=Strassen_Algorithm/Examples/Order_2&oldid=721173"