Mo logo [home] [lexicon] [problems] [tests] [courses] [auxiliaries] [notes] [staff] german flag
Mathematics-Online course: Linear Algebra - Matrices - Matrix Operations

Strassen's Algorithm

[previous page] [next page] [table of contents][page overview]
Calculating the product $ C=AB$ of two $ 2\times2$-matrices $ A$, $ B$ in the usual way we need $ 8$ multiplications. Surprisingly, Strassen proved that $ 7$ multiplications are sufficient [V. Strassen: Gaussian elimination is not optimal, Numer. Math. 13 (1969). 357-361]. After calculating the products

\begin{displaymath} \begin{array}{rcl} p_1 &=& (a_{1,2}-a_{2,2})(b_{2,1}+b_{2... ...-b_{1,1}) \\ p_7 &=& (a_{2,1}+a_{2,2})b_{1,1} \end{array} \end{displaymath}

we obtain the entries of product matrix $ C$ by forming the sums

\begin{displaymath} \begin{array}{rcccl} c_{1,1} &=& a_{1,1}b_{1,1}+a_{1,2... ...}b_{1,2}+a_{2,2}b_{2,2} &=& p_2-p_3+p_5-p_7. \end{array} \end{displaymath}

When we apply this construction to square matrices of dimension $ n=2^k$ recursively by decomposing the matrices into appropriate blocks, the number of multiplications reduces from $ n^3$ to $ O(n^{\log_2 7})$. This result could even be improved to $ O(n^{2.376\ldots})$ [D. Coppersmith, S. Winograd: Matrix Multiplication via arithmetic progressions, J. Symb. Comp. 9 (1990), 251-280]. It is conjectured that even $ O(n^2)$ is possible. The optimal exponent is yet unknown.

Today, this result is of no practical importance for matrices of real or complex numbers because calculations are usually carried out by computers multiplying almost as fast as adding. Therefore it does not make sence to replace 8 multiplications and 4 additions by 7 multiplications and 18 additions.

(Authors: Burkhardt/Höllig/Hörner)
  automatically generated 4/21/2005