RESULTS OF CHAPTER STUDY SUGGESTIONS 271
Preprocessed Coefficients
Standard Matrix Multiplication
Winograd’s Matrix Multiplication
Row factors: 4 40
Column factors: 18 14
Strassen’s Algorithm
x 1 = (G1,1 + G2,2)* (H1,1 + H2,2) = (1 + 8) * (6 + 2) = 9 * 8 = 72
x 2 = (G2,1 + G2,2)*H1,1 = (5 + 8) * 6 = 13 * 6 = 78
x 3 = G1,1* (H1,2H2,2) = 1 * (7 2) = 1 * 5 = 5
x 4 = G2,2* (H2,1H1,1) = 8 * (3 6) = 8 *3 = 24
x 5 = (G1,1 + G1,2)*H2,2 = (1 + 4) * 2 = 5 * 2 = 10
x 6 = (G2,1G1,1)* (H1,1 + H1,2) = (5 1) * (6 + 7) = 4 * 13 = 52
x 7 = (G1,2G2,2) (H2,1 + H2,2) = (4 8) (3 + 2) = (^4) 5 = 20
R1,1 = x 1 + x 4 x 5 + x 7 = 72 + 24 10 + 20 = 18
R2,1 = x 2 + x 4 = 78 + 24 = 54
R1,2 = x 3 + x 5 = 5 + 10 = 15
R2,2 = x 1 + x 3 x 2 + x 6 = 72 + 5 78 + 52 = 51
) x^7 8 x^6 3 x^5 2 x^4 4 x^3 00 x^2 05 x 07
x^7 8 x^6 3 x^5 2 x^4 5 x^3 40 x^2 15 x 10
x^3 40 x^2 20 x 03
x^3 08 x^2 03 x 02
x^4 5
[]()x^4 – (^5) ()x^3 – 8 x^2 ++ 3 x 2 +()x^3 – 40 x^2 ++ 20 x 3
x 08
) x (^3) 8 x (^2) 3 x 02 )
x^3 8 x^2 2 x 16
x^2 2
x 18
x^3 40 x^2 20 x 003
x 040
x^3 40 x^2 19 x 760
x^2 19
x 757
[]()x^4 – (^5) ()[]()x^2 + (^2) ()x– 8 +()x+ 18 +{}[]()x^2 + (^19) ()x– 40 +()x+ 757
14
58
67
32
(^1643) + (^1742) +
(^5683) + (^5782) + *
18 15
54 51
