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


This theorem requires a proof.
In particular: It remains to be demonstrated that this does in fact calculate $\mathbf C = \begin {pmatrix} a_{11} b_{11} + a_{12} b_{21} & a_{11} b_{21} + a_{12} b_{22} \\ a_{21} b_{11} + a_{22} b_{21} & a_{21} b_{21} + a_{22} b_{22} \end {pmatrix}$
You can help $\mathsf{Pr} \infty \mathsf{fWiki}$ by crafting such a proof.
To discuss this page in more detail, feel free to use the talk page.
When this work has been completed, you may remove this instance of {{ProofWanted}} from the code.
If you would welcome a second opinion as to whether your work is correct, add a call to {{Proofread}} the page.



Sources

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