Question

I already solved part A and I just need help with part B

1. Matrix Multiplication The product of two n xn matrices X and Y is a third n x n matrix 2 = XY, with entries 2 - 21; = xixYk x k=1 There are n’ entries to compute, each one at a cost of O(n). The formula implies an algorithm with O(nº) running time. For a long time this was widely believed to be the best running time possible. This has been proved wrong by a more efficient algorithm, based on divide-and-conquer. (a) (5 points) A Divide-and-Conquer Algorithm Matrix multiplication can be divided into subproblems in a straightforward way, because it can be performed blockwise. Write the matrices X and Y using blocks, submatrices of size n/2 x n/2. [AB] EF] [c D G H Now, the product of the two matrices can be written using these blocks. A B E F1 LAE+BG AF+BH Z = [ CD] CE+DG CF+DH We will use this decomposition to design a divide-and-conquer algorithm. In each step, the algorithm makes eight recursive calls to instances half the size. In order to combine the solutions to the subproblems, four matrix additions are made at a cost of O(n?). Formulate and solve the recurrence relation for the running time of the algorithm. G H (b) (5 points) Optimization Using a very clever optimization, the matrix multiplication based on the block de- composition can be solved with only seven multiplications, rather than eight. Formulate and solve the recurrence relation for the running time of the optimized algorithm. Is the new algorithm asymptotically faster?

Answer 1

The naive approach solves the matrix multiplication problem in O(n³) time. In order to improve the time complexity(make a smaller number of multiplications) we have Strassen Algorithm. For the matrix given below, it will

have 7 multiplications instead of 8.

ΓΑ Β] [E F] с D G H Blo

The seven multiplications for the given matrix will be:

p1= A*(F-H) ----- 1

p2= (A+B)*H ----- 2

p3= (C+D)*E -----3

p4= D*(G-E) ----4

p5= (A+D)*(E+H)----5

p6= (B-D)*(G+H)----6

P7= (A-C)* (E+F)

SOLVE THE VALUES INSIDE BRACKET FIRST THEN MULTIPLY.

ΓΑ Β] [E F] с D G H Blo
=  $\begin{bmatrix} p5+p4-p2+p6 &\hspace3 p1+p2\\ p3+p4& p1+p5-p3-p7 \end{bmatrix}$

So overall it will take 7 multiplications. The function will be called recursively to perform these 7 multiplications, to instances half the size.

The recurrence relation for performing Strassen Algorithm is:

T(n)= 7T(n/2) + O(n²),

which when solved using the Master's theorem is O(N^Log7) which is approximately O(N^2.8074). This time complexity O(N^2.8074), is asymptotically better/faster than O(n³) because of the lesser number of multiplications.

Though it's time complexity is less, it is not used much because of the complexity in solving this(by hand), and the recursion employed in Strassen Algorithm takes extra space.