Question #4 (15 points) In class, we discussed a divide-and-conquer algorithm for matrix multiplication that involved...

• Let X and Y be nxn matrices 211 212 ... in 221 222 .. in X = 3 31 32 . Tin nl xn2 .. Inn .

We want to compute Z = XY - Zij = EX=1 Xik. Ykj • Naive method uses →na.n= O(n) operations • Divide-and-conquer solution: SA BUJE FUS (A. E+B.G) (A. F+BH) 2= C D G H = (CE+D.G) (C.F+DH) - The above naturally leads to divide-and-conquer solution: * Divide X and Y into 8 sub-matrices A, B, C, and D. * Do 8 matrix multiplications recursively.

* Compute z by combining results (doing 4 matrix additions). - Lets assume n = 2€ for some constant c and let A, B, C and D be n/2 x n/2 matrices * Running time of algorithm is T(n) = 8T(n/2) + (na) = T(n) = (na)

Strassen observed the following: SA B E F S 2=CD) (GH) where (S1 + S2 - S4 +) (S&+S4) (54 +55) (S2 + S3 + S5 - S-) ) S2 = (B-D). (G + H) (A + D) (E+H) (A-C).(E +F) (A + B). H A. (F - H) D.G - E) (C+D).

E S5 = = = S - Lets test that S6 + S7 is really C.E+D.G S6 + S = D.G - E) + C + D = DG - DE + CE + DE = DG + CE E

(n) This leads to a divide-and-conquer algorithm with running time T(n) = 7T (n/2) + - We only need to perform 7 multiplications recursively. - Division/Combination can still be performed in e(na) time. Lets solve the recurrence using the iteration method T(n) = 7T(n/2) + n2 +7(716) +63) = n²+(5)n? +71(1) = n²+()n? +72(71 )+2) + = x + x + y + z^T = n2+ (z)n? +(7)2n +(3) Br?.... + (5) lossn-1m2 + plos na 2 (23*n° + plop na = nº. 01 (37)log.n-1) + zbogin = np.

Obywaten) + plon = 12.0(7") + plosn e(7log")

- Now we have the following: zlogn = 710872 (7log, n) (1/log, 2) = n(1/log, 2) log27 = = n log22 plog 7 - Or in general: glogkn = nlogk a So the solution is T(n) = O(nlog 7) = O(n2.8...)