算法设计(分治法-大整数、矩阵相乘)_48286.ppt

2007-2008-01《Design and Analysis of Algorithms》SCUEC Review of last class The difference between quick sort and merge sort Goals of the Lecture At the end of this lecture, you should Understand the algorithm based on DAC for solving large integers’ multiplication and its analysis Master the Strassen’s matrix multiplication algorithm and its analysis Know how to solve the triomino puzzle Multiplication of Large Integers The grade-school algorithm: a1 a2 … an b1 b2 … bn (d10) d11d12 … d1n (d20) d21d22 … d2n … … … … … … … (dn0) dn1dn2 … dnn Standard Algorithm based on DAC Improved Algorithm based on DAC Multiplication of Matrices Time complexity: T(n) = n3 + (n3 – n2) Standard Algorithm Based on Divide and Conquer Technique (I) Suppose we want to multiply matrices A and B, both of size n?n, and n = 2k, we can use divide and conquer technique to solve it. Standard Algorithm Based on Divide and Conquer Technique (II) So the result consists of computing C as defined by the following equation: Analysis of the algorithm Number of multiplications and additions T(n) = 8T(n/2) + 4(n/2)2 if n=2 T(1) = 1 Strassen’s Matrix Mutiplication Uses a set of seven formulas to multiply two 2?2 matrices The formulas do not rely on elements being commutative under multiplication, so the elements can be 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 Strassen’s Formulas (I) First we calculate a set of temporary values: m1 = (A1,1 + A2,2) * (B1,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) Strassen’s Formulas (II) Can you write out the strassen’s algorithm? (description) Algorithm analysis These formulas require 7 multiplications and 18 additions to multiply two 2 ? 2 matrices Standard vs DAC vs Strasse