Exercises 28.2-6

(a + bi)(c + di) = (ac – bd) + (ad + bc)i. Let A = (a+b)(c+d), B = ac, C = bd. (a+bi)(c+di) = (B-C) + (A – B – C)i.

Exercises 28.2-5

We can divide kn * n matrix into k n * n matrix, also divide n * kn matrix into k n * n matrix. Then we use the Strassen’s algorithm to multiply these 2k matrix to get the final result. The time complexity is .

Exercises 28.2-4

=2.79512849, =2.79512269, =2.79514739, = 2.80735492. The second method is best and all three methods are better than Strassen’s algorithm.

Exercises 28.2-3

Divide the matrix into 9 parts and use new multiply method to get the result recursively. The resulting algorithm can run in , if < , then the algorithm can run in time .

Exercises 28.2-2

Enlarge the matrix such that n is power of 2 and the adding entriesa are zero.

Exercises 28.2-1