Definition:Strassen Algorithm/Motivation

Definition

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.

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

• 1998: David Nelson: The Penguin Dictionary of Mathematics (2nd ed.) ... (previous) ... (next): Strassen's method
• 2008: David Nelson: The Penguin Dictionary of Mathematics (4th ed.) ... (previous) ... (next): Strassen's method