算法設計(分治法-大整數(shù)矩陣相乘)

1、2022-2-1822007-2008-01Design and Analysis of AlgorithmsSCUEC Design and Analysis of Algorithm SCUECReview of last classbThe difference between quick sort and merge sort Divide step Combine step Stable or not In place or not Time efficiencybThe basic idea of quick sort algorithmDivide and Conquer(III

2、)Chapter 4l Application to numerical problemn Large integers multiplicationn Matrices multiplicationl Application to combinatorial problemn Triomino puzzle2022-2-1842007-2008-01Design and Analysis of AlgorithmsSCUEC Design and Analysis of Algorithm SCUECGoals of the LecturebAt the end of this lectur

3、e, you should Understand the algorithm based on DAC for solving large integers multiplication and its analysis Master the Strassens matrix multiplication algorithm and its analysis Know how to solve the triomino puzzle2022-2-1852007-2008-01Design and Analysis of AlgorithmsSCUEC Design and Analysis o

4、f Algorithm SCUECMultiplication of Large Integers The grade-school algorithm:a1 a2 an b1 b2 bn (d10) d11d12 d1n (d20) d21d22 d2n (dn0) dn1dn2 dnnConsider the problem of multiplying two (large) n-digit integers represented by arrays of their digits such as:A = 12345678901357986429 B = 876543212848209

5、12836Efficiency: n2 one-digit multiplications. too inefficient!2022-2-1862007-2008-01Design and Analysis of AlgorithmsSCUEC Design and Analysis of Algorithm SCUECStandard Algorithm based on DACA = B = Where: A = A1*10n/2 + A2 B = B1*10n/2 + B2 A B = A1 B110n +(A1 B2+A2 B1) 10n/2+A2 B2A1B1B2A2bSuppos

6、e the n-digits of the two integers is a power of 2, i.e. n = 2k, then we can divide them as follows:b Efficiency: T(n) = 4T(n/2), T(1) = 1 Solution: T(n) = n2 bA small example: A = 2135 and B = 4014 no improvement!2022-2-1872007-2008-01Design and Analysis of AlgorithmsSCUEC Design and Analysis of Al

7、gorithm SCUECImproved Algorithm based on DACbIn order to improve the time complexity, the numbers of multiplication must be decreased.bTwo solutions: A B = A1 B110n +(A1+A2)+(B1+ B2) - A1 B1 - A2 B2) 10n/2+A2 B2 A B = A1 B110n +(A1 - A2)+(B2 B1) + A1 B1+A2 B2) 10n/2+A2 B2b Efficiency: T(n) = 3T(n/2)

8、, T(1) = 1 Solution: T(n) = nlog3 bigger improvement!A B = A1 B110n +(A1 B2+A2 B1) 10n/2+A2 B22022-2-1882007-2008-01Design and Analysis of AlgorithmsSCUEC Design and Analysis of Algorithm SCUECvoid MATRIX_MULTIPLY(float An, float Bn, float Cn) for (int i = 0; in; i+) for (int j = 0; jn; j+) Cii = Ai

9、0 * B0j;for (k = 1; k=2 T(1) = 1bIn fact, the recursive version requires n3 multiplications and n3 n2 additions, so it is not more efficient than the standard one. On the contrary, it is cost more in terms of both time and space brought by recursion.bT(n) = n3 + (n3 - n2)2022-2-18122007-2008-01Desig

10、n and Analysis of AlgorithmsSCUEC Design and Analysis of Algorithm SCUECStrassens Matrix MutiplicationbUses a set of seven formulas to multiply two 22 matricesbThe formulas do not rely on elements being commutative under multiplication, so the elements can be matrices bIt can be applied recursively,

11、 in other words, two 4 4 matrices can be multiplied by treating each as a 2 2 matrix of 2 2 matrices2022-2-18132007-2008-01Design and Analysis of AlgorithmsSCUEC Design and Analysis of Algorithm SCUECStrassens Formulas (I)bFirst we calculate a set of temporary values:m1 = (A1,1 + A2,2) * (B1,1 + B2,

12、2)m2 = (A2,1 + A2,2) * B1,1m3 = A1,1 * (B1,2 - B2,2)m4 = A2,2 * (B2,1 - B1,1)m5 = (A1,1 + A1,2) * B2,2m6 = (A2,1 - A1,1) * (B1,1 + B1,2)m7 = (A1,2 - A2,2) * (B2,1 + B2,2)111211121112212221222122, , =AABBCCAHCAABBCC2022-2-18142007-2008-01Design and Analysis of AlgorithmsSCUEC Design and Analysis of A

13、lgorithm SCUECStrassens Formulas (II)bCan you write out the strassens algorithm? (description)1111122111121222111221112221211222222122A BA BA BA BCCCA BA BA BA BCCbThe result is then calculated by:C1,1 = m1 + m4 - m5 + m7 C2,1 = m2 + m4C1,2 = m3 + m5C2,2 = m1 + m3 - m2 + m62022-2-18152007-2008-01Des

14、ign and Analysis of AlgorithmsSCUEC Design and Analysis of Algorithm SCUECAlgorithm analysisbThese formulas require 7 multiplications and 18 additions to multiply two 2 2 matricesbThe real savings occur when this is applied recursively and we do approximately n2.81 multiplications and 6n2.81-6n2 add

15、itionsbThough not used in practice, Strassens method is important because it was the first algorithm that is faster than O(n3) T(n) = 7T(n/2) + 18(n/2)2 if n =2 T(1) = 1 T(n) = nlog7 + 6nlog7 6n22022-2-18162007-2008-01Design and Analysis of AlgorithmsSCUEC Design and Analysis of Algorithm SCUECStand

16、ard vs DAC vs Strassen6n2.81-6n2n2.81Strassens algorithmn3Standard algorithm based on DACn3-n2n3Standard algorithmAdditionsMultiplicationsn3-n2DACs Application to Combinatorial Problemn Triomino puzzle2022-2-18182007-2008-01Design and Analysis of AlgorithmsSCUEC Design and Analysis of Algorithm SCUE

17、CbProblem description A triomino is an L-shaped tile formed by three adjacent squares of a chess board. The problem is to cover any 2k2k chessboard with one missing square (any where on the board) with triominos. Triominos should cover all the squares except the missing one with no overlaps.Triomino

18、 Puzzle (Chess board cover)2022-2-18192007-2008-01Design and Analysis of AlgorithmsSCUEC Design and Analysis of Algorithm SCUECAlgorithm Based on Divide and Conquer TechniquebIdea Divide the 2k2k grid into four 2k-12k-1 subgrids (see figure(a). Suppose the missing square is in the NW subgrid. Remove

19、 the squares closest to the center of the grid from the other three subgrids. The three removed squares in the NE, SW, SE subgrids can be tiled with a single triomino (see figure(b).2022-2-18202007-2008-01Design and Analysis of AlgorithmsSCUEC Design and Analysis of Algorithm SCUECAlgorithm analysis

20、bLet T(k) denotes the time needed to cover any 2k2k chessboard, From the dividing strategy, we can get the time recurrence relation as follows:bThe above recurrence relation works out to:bThe triomino tiles needed to cover any 2k2k chessboard are (4k-1)/3. So the algorithm is optimal(1)0( )4 (1)(1)0

21、OkT kT kOk( )(4 )kT kOThe End2022-2-18222007-2008-01Design and Analysis of AlgorithmsSCUEC Design and Analysis of Algorithm SCUECAssignmentsbReading assignment: Textbook page 149-154bExercise: No 2,6,7 of exercises 4.5(p148)2022-2-18232007-2008-01Design and Analysis of AlgorithmsSCUEC Design and Ana

22、lysis of Algorithm SCUECStrassens algorithm (I)void STRASSEN(int n, float An, float Bn, float Cn) float A11nn, A12nn, A21nn, A22nn; float B11nn, B12nn, B21nn, B22nn; float C11nn, C12nn, C21nn, C22nn; float m1nn, m2nn,m3nn, m4nn, m5nn, m6nn,m7nn; float AAnn, BBnn, MM1nn,MM2nn; int i, j; if (n=2) / mu

23、ltiplied by standard algorithm directly MATRIX_MULTIPLY(A, B, C); 2022-2-18242007-2008-01Design and Analysis of AlgorithmsSCUEC Design and Analysis of Algorithm SCUECelse / (1) divide matrix A and B into four blocks for (i=0; in/2; i+) for (j=0; jn/2; j+) A11ij = Aij; A12ij = Aij+n/2; A21ij = Ai+n/2

24、j; A22ij = Ai+n/2j+n/2; B11ij = Bij; B12ij = Bij+n/2; B21ij = Bi+n/2j; B22ij = Bi+n/2j+n/2; Strassens algorithm (II) / (2) calculate m1, m2, ., m7 recursively MATRIX_ADD(n/2, A11, A22, AA); MATRIX_ADD(n/2, B11, B22, BB); STRASSEN(n/2, AA, BB, m1); / m1=(A11+A22)*(B11+B22) MATRIX_ADD(n/2, A21, A22, A

25、A); STRASSEN(n/2, AA, B11, m2); / m2=(A21+A22)*B11 MATRIX_SUB(n/2, B12, B22, BB); STRASSEN(n/2, A11, BB, m3); / m3=A11*(B12-B22) MATRIX_SUB(n/2, B21, B11, BB); STRASSEN(n/2, A22, BB, m4); / m4=A22*(B21-B11) MATRIX_ADD(n/2, A11,A12, AA); STRASSEN(n/2, AA, B22, m5); / m5=(A11+A12)*B22 MATRIX_SUB(n/2,

26、A21, A11, AA); MATRIX_ADD(n/2, B11, B12, BB); STRASSEN(n/2, AA, BB, m6); / m6=(A21-A11)*(B11+B12) MATRIX_SUB(n/2, A12, A22, AA); MATRIX_ADD(n/2, B21, B22, BB); STRASSEN(n/2, AA, BB, m7); / m7=(A12-A22)*(B21+B22) / (3) calculate C11, C12, C21, C22 MATRIX_ADD(n/2, m1, m4, MM1); MATRIX_SUB(n/2, m5, m7,

27、 MM2); MATRIX_SUB(n/2, MM1, MM2, C11); /C11 = m1 + m4 - m5 + m7 MATRIX_ADD(n/2, m3, m5, C12); /C12 = m3 + m5 MATRIX_ADD(n/2, m2, m4, C21); /C21 = m2 + m4 MATRIX_ADD(n/2, m1, m3, MM1); MATRIX_SUB(n/2, m2, m6, MM2); MATRIX_SUB(n/2, MM1, MM2, C22); /C22 = m1 + m3 - m2 + m6 / (4) combine C11, C12, C21,

28、C22 into C for (i=0; in/2; i+) for (j=0; jn/2; j+) Cij = C11ij; Cij+n/2 = C12ij; Ci+n/2j = C21ij; Ci+n/2j+n/2 = C22ij; / else finishedvoid chessBoard(int tr, int tc, int dr, int dc, int size) if (size = 1) return; t+; / number of L-shaped tile s = size/2; / partition chess board / cover the left-top sub chess board if (dr