Analysis of Algorithms : An Active Learning Approach

4.2 MATRIX MULTIPLICATION 115

■ 4.2.2 Strassen’s Matrix Multiplication
For Strassen’s algorithm, we will work with matrices that are square. In actual-
ity, Strassen’s algorithm is fast enough that expanding matrices to be square can
sometimes still result in enough improvement to offset the extra elements.
Strassen’s algorithm uses a set of seven formulas to multiply two 2  2
matrices. These formulas are quite unusual, and it is unfortunate that Strassen’s
original paper presenting this method gave no indication of how he arrived at
these formulas. What is notable is that these formulas and their use don’t rely
on the base elements being commutative under multiplication. This means that
each of the elements could be matrices and, therefore, this method can be
applied recursively. Strassen’s formulas are

The entries of R would then be calculated by

For two 2  2 matrices, we see that this algorithm does 7 multiplications
and 18 additions. This doesn't appear to be a saving because we trade 1 multi-
plication for 14 additions relative to the standard algorithms. A full analysis of
this would show that the number of multiplications done for two NN
matrices would be approximately N2.81 and the number of additions would be
about 6N2.81
6 N^2. For two 16  16 matrices, Strassen's algorithm would
save about 1677 multiplications at a cost of 9138 additions.
Putting together our three results gives the following chart (for ease of com-
parison, the results are all shown for two NN matrices):

Multiplications Additions

Standard algorithm

Winograd’s algorithm

Strassen’s algorithm

x 1 =()G 11 , +G 22 , *()H 11 , +H 22 ,

x 2 =()G 21 , +G 22 , *H 11 ,

x 3 =G 11 , *()H 12 , –H 22 ,

x 4 =G 22 , *()H 21 , –H 11 ,

x 5 =()G 11 , +G 12 , *H 22 ,

x 6 =()G 21 , –G 11 , *()H 11 , +H 12 ,

x 7 =()G 12 , –G 22 , *()H 21 , +H 22 ,

R 11 , =x 1 ++x 4 – x 5 x 7

R 21 , =x 2 +x 4

R 12 , = x 3 +x 5

R 22 , = x 1 ++x 3 – x 2 x 6

N^3 N^3 – N^2

N^3 + 2 N^2

------------------------ 2

3 N^3 + 4 N^2 – 4 N

----------------------------------------- 2 -

N2.81 6 N2.81– 6 N^2