《算法课件全121301ADA08分治法大整数矩阵相乘》由会员分享，可在线阅读，更多相关《算法课件全121301ADA08分治法大整数矩阵相乘（28页珍藏版）》请在金锄头文库上搜索。
1、2019/6/21,2,2012-2013-01 Design and Analysis of Algorithm SCUN,Review of last class,The difference between quick sort and merge sort,Divide step Combine step Stable or not In place or not Time efficiency,Quick sort algorithm,Divide and Conquer (III),Chapter 4,Application to numerical problem Large i
2、ntegers multiplication Matrices multiplication,Application to combinatorial problem Tromino puzzle,2019/6/21,4,2012-2013-01 Design and Analysis of Algorithm SCUN,Goals of the Lecture,At the end of this lecture, you should Understand the algorithm based on DAC for solving large integers multiplicatio
3、n and its analysis Master the Strassens matrix multiplication algorithm and its analysis Understand the solution for tromino puzzle,2019/6/21,5,2012-2013-01 Design and Analysis of Algorithm SCUN,Multiplication of Large Integers,The grade-school algorithm: a1 a2 an b1 b2 bn (d10) d11d12 d1n (d20) d21
4、d22 d2n (dn0) dn1dn2 dnn,Consider the problem of multiplying two (large) n-digit integers represented by arrays of their digits such as: A = 12345678901357986429 B = 87654321284820912836,Efficiency: n2 one-digit multiplications., too inefficient!,2019/6/21,6,2012-2013-01 Design and Analysis of Algor
5、ithm SCUN,Standard Algorithm based on DAC,Suppose the n-digits of the two integers is a power of 2, i.e. n = 2k, then we can divide them as follows:,Efficiency: T(n) = 4T(n/2), T(1) = 1 Solution: T(n) = n2,A small example: A = 2135 and B = 4014, no improvement!,2019/6/21,7,2012-2013-01 Design and An
6、alysis of Algorithm SCUN,Improved Algorithm based on DAC,In order to improve the time complexity, the numbers of multiplication must be decreased.,Two solutions:,AB = A1B110n +(A1+A2)*(B1+ B2) - A1B1 - A2B2) 10n/2+A2B2,Efficiency: T(n) = 3T(n/2), T(1) = 1 Solution: T(n) = nlog3, bigger improvement!,
7、AB = A1B110n +(A1B2+A2B1) 10n/2+A2B2,AB = A1B110n +(A1 - A2)*(B2 B1) + A1B1+A2B2) 10n/2+A2B2,2019/6/21,8,2012-2013-01 Design and Analysis of Algorithm SCUN,void MATRIX_MULTIPLY(float An, float Bn, float Cn) for (int i = 0; in; i+) for (int j = 0; jn; j+) Cii = Ai0 * B0j; for (int k = 1; kn; k+) Cij
8、= Cij + Aik * Bkj; ,Multiplication of Matrices,Time complexity: T(n) = n3 + (n3 n2),This is a slight modification from the algorithm in the book(p64),Numbers of multiplication,Numbers of addition,Standard algorithm,2019/6/21,9,2012-2013-01 Design and Analysis of Algorithm SCUN,Standard Algorithm Bas
9、ed on Divide and Conquer Technique (I),Suppose we want to multiply matrices A and B, both of size nn, and n = 2k, we can use divide and conquer technique to solve it.,If n 2, then A, B and the result C can be partitioned into four matrices of dimensions n/2 n/2 each:,2019/6/21,10,2012-2013-01 Design
10、 and Analysis of Algorithm SCUN,Standard Algorithm Based on Divide and Conquer Technique (II),So the result consists of computing C as defined by the following equation:,Can you write out the algorithm description? Have a try after class!,2019/6/21,11,2012-2013-01 Design and Analysis of Algorithm SC
11、UN,Analysis of the algorithm,Number of multiplications and additions T(n) = 8T(n/2) + 4(n/2)2 if n=2 T(1) = 1,In 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
12、space brought by recursion.,T(n) = n3 + (n3 - n2),2019/6/21,12,2012-2013-01 Design and Analysis of Algorithm SCUN,Strassens Matrix Mutiplication,Uses a set of seven formulas to multiply two 22 matrices The formulas do not rely on elements being commutative under multiplication, so the elements can b
13、e matrices It can be applied recursively, in other words, two 4 4 matrices can be multiplied by treating each as a 2 2 matrix of 2 2 matrices,2019/6/21,13,2012-2013-01 Design and Analysis of Algorithm SCUN,Strassens Formulas (I),First we calculate a set of temporary values: m1 = (A1,1 + A2,2) * (B1,
14、1 + B2,2) m2 = (A2,1 + A2,2) * B1,1 m3 = A1,1 * (B1,2 - B2,2) m4 = A2,2 * (B2,1 - B1,1) m5 = (A1,1 + A1,2) * B2,2 m6 = (A2,1 - A1,1) * (B1,1 + B1,2) m7 = (A1,2 - A2,2) * (B2,1 + B2,2),2019/6/21,14,2012-2013-01 Design and Analysis of Algorithm SCUN,Strassens Formulas (II),Can you write out the strass
15、ens algorithm? (description),The result is then calculated by: C1,1 = m1 + m4 - m5 + m7 C2,1 = m2 + m4 C1,2 = m3 + m5 C2,2 = m1 + m3 - m2 + m6,2019/6/21,15,2012-2013-01 Design and Analysis of Algorithm SCUN,Algorithm analysis,These formulas require 7 multiplications and 18 additions to multiply two 2 2 matrices,The real savings occur when this is applied recursively and we do approximately n2.81 multiplications and 6n2.81-6n2 additions,Though 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) +
