info prev up next book cdrom email home

Strassen Formulas

The usual number of scalar operations (i.e., the total number of additions and multiplications) required to perform $n\times n$ Matrix Multiplication is

\begin{displaymath}
M(n)=2n^3-n^2
\end{displaymath} (1)

(i.e., $n^3$ multiplications and $n^3-n^2$ additions). However, Strassen (1969) discovered how to multiply two Matrices in
\begin{displaymath}
S(n)=7\cdot 7^{\lg n}-6\cdot 4^{\lg n}
\end{displaymath} (2)

scalar operations, where $\lg $ is the Logarithm to base 2, which is less than $M(n)$ for $n>654$. For $n$ a power of two ($n=2^k$), the two parts of (2) can be written
$\displaystyle 7\cdot 7^{\lg n}$ $\textstyle =$ $\displaystyle 7\cdot 7^{\lg 2^k}=7\cdot 7^k=7\cdot 2^{k\lg 7}=7(2^k)^{\lg 7}=7n^{\lg 7}$  
      (3)
$\displaystyle 6\cdot 4^{\lg n}$ $\textstyle =$ $\displaystyle 6\cdot 4^{\lg 2^k}=6\cdot 4^{k\lg 2}=6\cdot 4^k=6(2^k)^2=6n^2,$  
      (4)

so (2) becomes
\begin{displaymath}
S(2^k)=7n^{\lg 7}-6n^2.
\end{displaymath} (5)


Two $2\times 2$ matrices can therefore be multiplied

\begin{displaymath}
{\hbox{\sf C}}={\hbox{\sf A}}{\hbox{\sf B}}
\end{displaymath} (6)


\begin{displaymath}
\left[{\matrix{c_{11} & c_{12}\cr c_{21} & c_{22}\cr}}\right...
... \left[{\matrix{b_{11} & b_{12}\cr b_{21} & b_{22}\cr}}\right]
\end{displaymath} (7)

with only
\begin{displaymath}
S(2)=7\cdot 2^{\lg 7}-6\cdot 2^2=49-24=25
\end{displaymath} (8)

scalar operations (as it turns out, seven of them are multiplications and 18 are additions). Define the seven products (involving a total of 10 additions) as
$\displaystyle Q_1$ $\textstyle \equiv$ $\displaystyle (a_{11}+a_{22})(b_{11}+b_{22})$ (9)
$\displaystyle Q_2$ $\textstyle \equiv$ $\displaystyle (a_{21}+a_{22})b_{11}$ (10)
$\displaystyle Q_3$ $\textstyle \equiv$ $\displaystyle a_{11}(b_{12}-b_{22})$ (11)
$\displaystyle Q_4$ $\textstyle \equiv$ $\displaystyle a_{22}(-b_{11}+b_{21})$ (12)
$\displaystyle Q_5$ $\textstyle \equiv$ $\displaystyle (a_{11}+a_{12})b_{22}$ (13)
$\displaystyle Q_6$ $\textstyle \equiv$ $\displaystyle (-a_{11}+a_{12})(b_{11}+b_{12})$ (14)
$\displaystyle Q_7$ $\textstyle \equiv$ $\displaystyle (a_{12}-a_{22})(b_{21}+b_{22}).$ (15)

Then the matrix product is given using the remaining eight additions as
$\displaystyle c_{11}$ $\textstyle =$ $\displaystyle Q_1+Q_4-Q_5+Q_7$ (16)
$\displaystyle c_{21}$ $\textstyle =$ $\displaystyle Q_2+Q_4$ (17)
$\displaystyle c_{12}$ $\textstyle =$ $\displaystyle Q_3+Q_5$ (18)
$\displaystyle c_{22}$ $\textstyle =$ $\displaystyle Q_1+Q_3-Q_2+Q_6$ (19)

(Strassen 1969, Press et al. 1989).


Matrix inversion of a $2\times 2$ matrix ${\hbox{\sf A}}$ to yield ${\hbox{\sf C}}={\hbox{\sf A}}^{-1}$ can also be done in fewer operations than expected using the formulas

$\displaystyle R_1$ $\textstyle \equiv$ $\displaystyle {a_{11}}^{-1}$ (20)
$\displaystyle R_2$ $\textstyle \equiv$ $\displaystyle a_{21} R_1$ (21)
$\displaystyle R_3$ $\textstyle \equiv$ $\displaystyle R_1 a_{12}$ (22)
$\displaystyle R_4$ $\textstyle \equiv$ $\displaystyle a_{21}R_3$ (23)
$\displaystyle R_5$ $\textstyle \equiv$ $\displaystyle R_4-a_{22}$ (24)
$\displaystyle R_6$ $\textstyle \equiv$ $\displaystyle {R_5}^{-1}$ (25)
$\displaystyle c_{12}$ $\textstyle =$ $\displaystyle R_3R_6$ (26)
$\displaystyle c_{21}$ $\textstyle =$ $\displaystyle R_6R_2$ (27)
$\displaystyle R_7$ $\textstyle =$ $\displaystyle R_3 c_{21}$ (28)
$\displaystyle c_{11}$ $\textstyle =$ $\displaystyle R_1-R_7$ (29)
$\displaystyle c_{22}$ $\textstyle =$ $\displaystyle -R_6$ (30)

(Strassen 1969, Press et al. 1989). The leading exponent for Strassen's algorithm for a Power of 2 is $\lg 7\approx
2.808$. The best leading exponent currently known is 2.376 (Coppersmith and Winograd 1990). It has been shown that the exponent must be at least 2.

See also Complex Multiplication, Karatsuba Multiplication


References

Coppersmith, D. and Winograd, S. ``Matrix Multiplication via Arithmetic Programming.'' J. Symb. Comput. 9, 251-280, 1990.

Pan, V. How to Multiply Matrices Faster. New York: Springer-Verlag, 1982.

Press, W. H.; Flannery, B. P.; Teukolsky, S. A.; and Vetterling, W. T. ``Is Matrix Inversion an $N^3$ Process?'' §2.11 in Numerical Recipes in FORTRAN: The Art of Scientific Computing, 2nd ed. Cambridge, England: Cambridge University Press, pp. 95-98, 1989.

Strassen, V. ``Gaussian Elimination is Not Optimal.'' Numerische Mathematik 13, 354-356, 1969.



info prev up next book cdrom email home

© 1996-9 Eric W. Weisstein
1999-05-26