Question

Let X be a kn × n matrix and Y by an n × kn matrix, for some integer k. (a) Describe an algorithm that computes the product XY using Strassen's algorithm as a subroutine, i.e., use it as a black-box without modi- fying it. Only describe your algorithm in words; pseudo-code is not required. Justify your answer, i.e., argue that your algorithrn does compute XY correctly. Establish its running time.

Answer 1

a)

Consider X as matrices and B as $[B_1,B_2,B_3,...,B_k]^T$

Now multiplication would be among these N matrices and each n*n small matrix can be multiplied using Strassen's algorithm.

result would be [A1*B1 + A2*B2 + A3*B3 .... Ak*Bk]

So K matrix multiplication and sum of k matrices.

Time for Strassen's =

So multiplying k such algorithm = $mathcal{O}(kn^{2.8})$

Now summation will take

summation will take $mathcal{O}(kn^{2})$

So total time = $mathcal{O}(kn^{2.8})$