Fast Fourier TransformJean Baptiste Joseph Fourier (1768-1830)2Fast Fourier TransformApplications.■ Perhaps single algorithmic discovery that has had the greatest practical impact in history.■ Optics, acoustics, quantum physics, telecommunications, systems theory, signal processing, speech recognition, data compression.■ Progress in these areas limited by lack of fast algorithms.History.■ Cooley-Tukey (1965) revolutionized all of these areas.■ Danielson-Lanczos (1942) efficient algorithm.■ Runge-König (1924) laid theoretical groundwork.■ Gauss (1805, 1866) describes similar algorithm.■ Importance not realized until advent of digital computers.3Polynomials: Coefficient RepresentationDegree n polynomial.Addition: O(n) ops.Evaluation: O(n) using Horner’s method.Multiplication (convolution): O(n2).112210)(−−++++=nnxaxaxaaxp L112210)(−−++++=nnxbxbxbbxq L1111100)()()()()(−−−++++++=+nnnxbaxbabaxqxp L))))(((()(12210LL−−+++++=nnaxaxaxaxaxp22110011000)()()()()()(−−−=−++∑++++=×nnnjkjkjkxbaxbaxbababaxqxp LL4Polynomials: Point-Value RepresentationDegree n polynomial.■ Uniquely specified by knowing p(x) at n different values of x.{})( where ,),(x,),,(x),,(x11-n1100kknxpyyyy =−Kxy = p(x)xjyj5Polynomials: Point-Value RepresentationDegree n polynomial.Addition: O(n).Multiplication: O(n), but need 2n points.Evaluation: O(n2) using Lagrange’s formula.{})( where ,),(x,),,(x),,(x11-n1100kknxpyyyy =−K{}),(x,),,(x),,(x111-n111000 −−+++nnzyzyzy K∑∏∏−=≠≠−−=10)()()(nkkjjkkjjkxxxxyxp{}),(x,,),(x),,(x12121-2n111000 −− nnzyzyzy K{})(z where ,),(x,),,(x),,(x11-n1100kknxqzzz =−K6Best of Both WorldsCan we get "fast" multiplication and evaluation?! Yes! Convert back and forth between two representations.coefficientRepresentationO(n2)MultiplicationO(n)Evaluationpoint-value O(n) O(n2)FFT O(n log n) O(n log n)1-n101-n10,,b,ba,,a,abKK2-2n10,,,cccK)(,),(),q(x)(,),(),p(x1-2n101-2n10xqxqxpxpKK)(,),(),r(x1-2n10xrxrKO(n)point-value multiplicationO(n2)coefficient multiplicationO(n log n)evaluationFFTinterpolationinverse FFTO(n log n)7Converting Between Representations: Naïve SolutionEvaluation (coefficient to point-value).■ Given a polynomial p(x) =a0+ a2x1+ . . . + an-1xn-1, choose n distinct points {x0, x1, . . . , xn-1 } and compute yk= p(xk), for each k using Horner’s method.■ O(n2).Interpolation (point-value to coefficient).■ Given n distinct points {x0, x1, . . . , xn-1 } and yk= p(xk), compute the coefficients {a0, a1, . . . , an-1 } by solving the following linear system of equations.■ Note Vandermonde matrix is invertible iff xkare distinct.■ O(n3).=−−−−−−−−−12101210112111222211211102001111nnnnnnnnnyyyyaaaaxxxxxxxxxxxxMMLMOMMMLLL8Fast Interpolation: Key IdeaKey idea: choose {x0, x1, . . . , xn-1 } to make computation easier!■ Set xk=xj?=−−−−−−−−12101210102111222211211102001111nnnnnnnnyyyyaaaaxxxxxxxxxxxxMMLMOMMMLLL9=−−−−−−−−−−−−−−12101210132132132132)5()5()5(51)17()17()17(171)5()5()5(51)17()17()17(171nnnnnnyyyyaaaaMMMLMMMMLMMLMMMMLMFast Interpolation: Key IdeaKey idea: choose {x0, x1, . . . , xn-1 } to make computation easier!■ Set xk=xj?■ Use negative numbers: set xk= -xj so that (xk)2= (xj)2.– set xk= -xn/2 + k– E = peven(x2) = a0+ a2172+ a4174 + a6176 + . . . + an-217n-2– O = x podd(x2) = a117 + a3173+ a5175 + a7177 + . . . + an-117n - 1– y0= E + O, yn/2= E - O10Fast Interpolation: Key IdeaKey idea: choose {x0, x1, . . . , xn-1 } to make computation easier!■ Set xk= xj?■ Use negative numbers: set xk= -xj so that (xk)2= (xj)2.– set xk= -xn/2 + k■ Use complex numbers: set xk= ωk where ω is nthroot of unity.– (xk)2= (-xn/2 + k )2– (xk)4= (-xn/4 + k )4– (xk)8= (-xn/8 + k )8=−−−−−−−−−− 13210)1)(1()1(3)1(21)1(3963)1(2642132113210111111111nnnnnnnnnnaaaaayyyyyMLMOMMMMLLLLMωωωωωωωωωωωωωωωω11Roots of UnityAn nthroot of unity is a complex number z such that zn= 1.■ ω = e 2π i / n= principal nthroot of unity.■ e i t = cos t + i sin t.■ i2 = -1.■ There are exactly n roots of unity: ωk, k = 0, 1, . . . , n-1.ω0= 1ω1ω2= iω3ω4= -1ω5ω6= -iω712Roots of Unity: PropertiesL1: Let ω be the principal nthroot of unity. If n > 0, then ωn/2= -1.■ Proof: ω = e 2π i / n ⇒ωn/2= e π i= -1. (Euler’s formula)L2: Let n > 0 be even, and let ω and ν be the principal nthand (n/2)throots of unity. Then (ωk )2= νk.■ Proof: (ωk )2= e (2k)2π i / n= e (k) 2π i / (n / 2) = νk .L3: Let n > 0 be even. Then, the squares of the n complex nthroots of unity are the n/2 complex (n/2)throots of unity.■ Proof: If we square all of the nthroots of unity, then each (n/2)throot is obtained exactly twice since:– L1 ⇒ωk + n / 2= - ωk– thus, (ωk + n / 2) 2= (ωk )2– L2 ⇒ both of these = νk– ωk + n / 2and ωk have the same square13Divide-and-ConquerGiven degree n polynomial p(x) = a0+ a1x1+ a2x2 + . . . + an-1xn-1.■ Assume n is a power of 2, and let ω be the principal nthroot of unity.■ Define even and odd polynomials:– peven(x) := a0+ a2x1+ a4x2 + a6x3 + . . . + an-2xn/2 - 1– podd(x) := a1+ a3x1+ a5x2 + a7x3 + . . . + an-1xn/2 - 1– p(x) = peven(x2) + x podd(x2)■ Reduces problem of– evaluating degree n polynomial p(x) at ω0, ω1, . . . , ωn-1to– evaluating two degree n/2 polynomials at: (ω0)2, (ω1)2, . . . , (ωn-1)2 .■ L3 ⇒ peven(x) and podd(x) only evaluated at n/2 complex (n/2)throots of unity.14FFT Algorithmif (n == 1) // n is a power of 2return a0ω ← e 2π i / n(e0,e1,e2,...,en/2-1) ← FFT(n/2, a0,a2,a4,...,an-2)(d0,d1,d2,...,dn/2-1) ← FFT(n/2, a1,a3,a5,...,an-1)for k = 0 to n/2 - 1yk ← ek+ ωkdkyk+n/2← ek- ωkdkreturn (y0,y1,y2,...,yn-1)FFT (n, a0, a1, a2, .