Introduction to Computational Linear Algebra

26 Introduction to Computational Linear Algebra

1. Prove that this leads correctly to the product C = AB.

2. Prove that the number of flops C

1

(n) when the Strassen reduction is

applied is

C

1

(n) = 2(7m

3

) + 18m

2

=

7

8

(2n

3

) +

9

2

n

2

.

Compare it to the regular complexity C

0

(n) = 2n

3

of the matrix multi-

plication and determine the minimum n such that C

1

(n) < C

0

(n).

3. Let us assume that n = 2

k

m, and that k Strassen reductions are recur-

sively applied by the procedure described by the algorithm 1.6. Justify

the algorithm.

Algorithm 1.6 Strassen’s Algorithm

function C = strassen(A,B,k)

%

% C = strassen(A,B,k)

%

% Matrix multiplication by Strassen’s reduction C=A*B

% Recursive ...