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

multiplications and

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

for

. For

a power of two (

), 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.

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