Matrix Multiplication and the Master Theorem

Design and Analysis of Algorithms Massachusetts Institute of Technology Profs. Erik Demaine, Srini Devadas and Nancy Lynch 6.046J/18.410J Recitation 1 Matrix Multiplication and the Master Theorem 1 Weighted interval scheduling Consider requests 1,. . . ,n. For request i, s(i) is the start time and f (i) is the finish time, s(i) < f (i). Two requests i and j are compatible if they don’t overlap, i.e., f (i) ≤ s(j) or f (j) ≤ s(i). Each requet i has a weight w(i). Goal: schedule the subset of compatible requests with maximum weight. 1.1 The n log n dynamic programming solution Sort requests in earliest finish time order. f (1) ≤ f (2) ≤ · · · ≤ f (n) Definition p(j) for interval j is the largest index i < j such that request i and j are compatible. Array M [0 . . . n] holds the optimal solution’s values. M [k] is the maximum weight if requests from 1 to k are considered. 1 M[0] = 0 2 for j = 1 to n M[j] = max(w(j) + M[p(j)], M[j - 1]) 3 Once we have M, the optimal solution can be derived by tracing it back in O(n) time. Sorting requests in earliest finish time takes O(n log n) time. And the whole algorithm takes O(n log n) time. 2 Strassen 2.1 Matrix Multiplication Take matrices A, B, multiply row i of A by column j of B to fill in entry i,j of resulting matrix, C. Running time is Θ(n3 ) on square matrices, where n is the dimension of each matrix. 2 Recitation 1: Matrix Multiplication and the Master Theorem 2.2 The Strassen Algorithm • powerful early application of Divide and Conquer • not the fastest matrix multiplication (though it was at time of discovery) – Don Coppersmith, Shmuel Winograd, Andrew Stothers, and Vassilevska Williams con­ tributed to the current fastest method. See http://en.wikipedia.org/wiki/ Coppersmith-Winograd_algorithm for details. 2.2.1 Steps • Make A, B each 2k x 2k by filling remaining rows/columns with 0: – Why can you do this? ∗ Each dimension increases by less than a factor of 2 ∗ Even with traditional Θ(n3 ) matrix multiplication, this makes the running time always increase by a factor of less than 8, not dependent on the magnitude of N, and constant factors are always ignored when discussing complexity. • Partition A, B, and C (elements unknown for C, but same dimensions) into 4 matrices of dimension 2k−1 each • We can see that the 4 submatrices of C can be found by standard matrix multiplications of A and B, using the submatrices as “elements” � � A1,1 A1,2 A= , A2,1 A2,2 � � B1,1 B1,2 B= , B2,1 B2,2 � C1,1 C1,2 C= C2,1 C2,2 � C1,1 = A1,1 B1,1 + A1,2 B2,1 C1,2 = A1,1 B1,2 + A1,2 B2,2 C2,1 = A2,1 B1,1 + A2,2 B2,1 C2,2 = A2,1 B1,2 + A2,2 B2,2 • Optimization is derived from the fact that matrix addition is much, much simpler than mul­ tiplication (Θ(n2 ) instead of Θ(n3 )) Recitation 1: Matrix Multiplication and the Master Theorem Thus, C1,1 C2,2 Define M1 M2 M3 M4 M5 M6 M7 = M1 + M4 − M5 + M7 C1,2 = M3 + M5 C2,1 = M2 + M4 = M1 − M2 + M3 + M6 = = = = = = = = = = = 3 (A1,1 + A2,2 )(B1,1 + B2,2 ) (A2,1 + A2,2 )B1,1 A1,1 (B1,2 − B2,2 ) A2,2 (B2,1 − B1,1 ) (A1,1 + A1,2 )B2,2 (A2,1 − A1,1 )(B1,1 + B1,2 ) (A1,2 − A2,2 )(B2,1 + B2,2 ) A1,1 B1,1 + A1,2 B2,1 A1,1 B1,2 + A1,2 B2,2 A2,1 B1,1 + A2,2 B2,1 A2,1 B1,2 + A2,2 B2,2 Proof of correctness follows from arithmetic. We can recursively calculate each of the above submatrices using equally-sized submatrices of A1,1 , etc., which is why we needed dimensions of 2n instead of merely even dimensions. When you have C, strip out rows/columns of 0s that correspond to the same parts of A and B. • Each recursive step takes 7 multiplications and 18 additions, instead of 8 multiplications • We can see that this would be less efficient than 8 multiplications for small matrices. For a 2-element matrix being broken into 4 1-element matrices, it’s over triple the work! Running time: T(n) = Θ(nlog2 (7) ) ≈ Θ(n2.8074 ) How do we get this value? (next up) 3 Master Theorem 3.1 General use General form of a recurrence: T (n) = aT (n/b) + f (n) • f (n) polynomially less than nlogb (a) : T (n) = Θ(nlogb (a) ) • f (n) is Θ(nlogb (a) logk (n)), where k ≥ 0: T (n) = Θ(f (n) log(n)) = Θ(nlogb (a) logk+1 (n)) • nlogb (a) polynomially less than f (n), and af (n/b) ≤ cf (n) for some constant c < 1 and all sufficiently large n: T (n) = Θ(f (n)) If nlogb (a) is greater, but not polynomially greater, than f (n), the Master Theorem cannot be used to determine a precise bound. (e.g. T (n) = 2T (n/2) + Θ(n/ log(n))) 4 Recitation 1: Matrix Multiplication and the Master Theorem 3.2 Strassen Runtime Now, think about Strassen’s algorithm. It performs 7 multiplications and 18 additions/subtractions each iteration. The addition is performed directly; the multiplications are done recursively using the Strassen Algorithm. In each recursive step, we divide the matrix into 4 parts; however, remember that we consider the running time in terms of the dimension of the matrix, not the total number of elements. Thus, the recurrence becomes T (n) = 7T (n/2) + 18Θ(n2 ) = 7T (n/2) + Θ(n2 ) We can then examine the Master Theorem: nlog2 (7)) is polynomially greater than n2 Thus, Θ(nlog2 (7) ) is the solution to the recurrence. 3.3 Median Finding m v Prove that T (n) = T ( n5 ) + T ( 710n + 6) + Θ(n) solves for T (n) = Θ(n). Proof: We use the substitution method (details can be found in the CLRS textbook) to solve the recurrence. We first guess the form of the answer to be O(n), and try to prove that T (n) ≤ dn for some m n vvalue of d.7nWe first assume that the bound holds for all positive m < n, and thus it holds for T ( 5 ) and T ( 10 + 6) if n is large enough. Substituting into the recurrence yields �n� 7n T (n) = T ( ) + T ( + 6) + cn (1) 5 10 n 7n ≤ d( + 1) + d( + 6) + cn (2) 5 10 9 = dn + 7d + cn (3) 10 ≤ dn (4) The last inequality holds if d > 10c when n is large enough. 3.4 Extra details Drawing a recursion tree using the recurrence T (n) = 4T (n/2) + Θ(n2 ) will show why the log factor is used if f(n) is not polynomially greater than nlogb (a) . Think of the total amount of work that must be done. Feel free to examine T (n) = 4T (n/2) + Θ(n2 log(n)) to see why the solution must be Θ(n2 log2 (n)) instead of just Θ(n2 log(n)).