Strassen Formulas

The usual number of scalar operations (i.e., the total number of additions and multiplications) required to perform matrix multiplication is

(1)

(i.e., multiplications and additions). However, Strassen (1969) discovered how to multiply two matrices in

(2)

scalar operations, where is the logarithm to base 2, which is less than for . For a power of two (), the two parts of (2) can be written

			(3)
			(4)
			(5)
			(6)
			(7)
			(8)
			(9)
			(10)
			(11)
			(12)

so (◇) becomes

(13)

Two matrices can therefore be multiplied

(14)

(15)

with only

(16)

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

			(17)
			(18)
			(19)
			(20)
			(21)
			(22)
			(23)

Then the matrix product is given using the remaining eight additions as

			(24)
			(25)
			(26)
			(27)

(Strassen 1969, Press et al. 1989).

Matrix inversion of a matrix to yield can also be done in fewer operations than expected using the formulas

			(28)
			(29)
			(30)
			(31)
			(32)
			(33)
			(34)
			(35)
			(36)
			(37)
			(38)

(Strassen 1969, Press et al. 1989). The leading exponent for Strassen's algorithm for a power of 2 is . 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.

Unfortunately, Strassen's algorithm is not numerically well-behaved. It is only weakly stable, i.e., the computed result satisfies the inequality

(39)

where is the unit roundoff error, while the corresponding strong stability inequality (obtained by replacing matrix norms with absolute values of the matrix elements) does not hold.

Wolfram Web Resources