Definition:Strassen Algorithm

From ProofWiki
Jump to navigation Jump to search

Definition

The Strassen algorithm is a method for evaluating the product of two square matrices of order $n$.



This article is complete as far as it goes, but it could do with expansion.
In particular: give the full algorithm
You can help $\mathsf{Pr} \infty \mathsf{fWiki}$ by adding this information.
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 {{Expand}} from the code.
If you would welcome a second opinion as to whether your work is correct, add a call to {{Proofread}} the page.


Motivation

The number of operations required when using the Strassen algorithm is proportional to $n^{\lg 7}$, where $\lg$ denotes the binary logarithm $\log_2$

The conventional technique to calculate the matrix product takes $2 n^3$ operations.

As $\lg 7 \approx 2.81$ and $2^3 = 3$, for sufficiently large $n$ the Strassen algorithm has a lower algorithmic complexity.


Also known as

The Strassen algorithm is also known as Strassen's method.


Examples

Order $2$ Matrices

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


Also see

  • Results about the Strassen algorithm can be found here.


Source of Name

This entry was named for Volker Strassen‎.


Historical Note

The Strassen algorithm was designed by Volker Strassen‎ in $1969$.


Sources

Retrieved from "https://proofwiki.org/w/index.php?title=Definition:Strassen_Algorithm&oldid=659172"