Polynomials and the Fast Fourier Transform (FFT)

1 Polynomials and the fast Fourier Transform (FFT). Algorithm Design and Analysis (Week 7). 1. Battle Plan Polynomials Algorithms to add, multiply and evaluate Polynomials Coefficient and point-value representation Fourier Transform Discrete Fourier Transform (DFT) and inverse DFT to translate between polynomial representations A Short Digression on Complex Roots of Unity . fast Fourier Transform (FFT) is a divide-and-conquer algorithm based on properties of complex roots of unity 2. Polynomials A polynomial in the variable is a representation of a function = 1 1 + + 2 2 + 1 + 0. 1 . as a formal sum = =0 . We call the values 0 , 1, , 1 the coefficients of the polynomial is said to have degree if its highest nonzero coefficient is . Any integer strictly greater than the degree of a polynomial is a degree-bound of that polynomial 3. Examples = 3 2 1. ( ) has degree 3. ( ) has degree-bounds 4, 5, 6, or all values > degree ( ) has coefficients ( 1, 2, 0, 1). = 3 + 2 + 1. ( ) has degree 3. ( ) has degree bounds 4, 5, 6, or all values > degree ( ) has coefficients (1, 0, 1, 1).

2 4. Coefficient Representation A coefficient representation of a polynomial = 1 . =0 of degree-bound is a vector of coefficients = 0 , 1 , , 1 . More examples = 6 3 + 7 2 10 + 9 (9, 10, 7, 6). = 2 3 + 4 5 ( 5, 4, 0, 2). The operation of evaluating the polynomial ( ) at point 0 consists of computing the value of 0 . Evaluation takes time ( ) using Horner's rule ( 0 ) = 0 + 0 ( 1 + 0 ( 2 + + 0 2 + 0 1 )). 5. Adding Polynomials Adding two Polynomials represented by the coefficient vectors = ( 0 , 1 , , 1 ) and = ( 0 , 1 , , 1 ) takes time ( ). Sum is the coefficient vector = ( 0 , 1 , , 1 ), where = + for = 0,1, , 1. Example = 6 3 + 7 2 10 + 9 (9, 10, 7, 6). = 2 3 + 4 5 ( 5, 4, 0, 2). 3 2. ( ) = 4 + 7 6 + 4 (4, 6,7,4). 6. Multiplying Polynomials For polynomial multiplication, if ( ) and ( ) are Polynomials of degree-bound n, we say their product ( ) is a polynomial of degree-bound 2 1. Example 6 3 + 7 2 10 + 9. 2 3 + 4 5. 30 3 2. 35 + 50 45. 24 4 + 28 3 40 2 + 36 . 12 6 14 5 + 20 4 18 3.

3 12 6 14 5 + 44 4 20 3 75 2 + 86 45. 7. Multiplying Polynomials Multiplication of two degree-bound n Polynomials ( ) and ( ) takes time 2 , since each coefficient in vector must be multiplied by each coefficient in vector . Another way to express the product C(x) is 2 1 . =0 , where = =0 . The resulting coefficient vector = ( 0 , 1 , 2 1 ). is also called the convolution of the input vectors . and , denoted as = . 8. Point-Value Representation A point-value representation of a polynomial ( ). of degree-bound is a set of point-value pairs 0 , 0 , 1 , 1 , , 1 , 1. such that all of the are distinct and = ( ). for = 0, 1, , 1. Example = 3 2 + 1. 0, 1, 2, 3. * 0, 1 , 1, 0 , 2, 5 , 3, 22 +. ( ) 1, 0, 5, 22. Using Horner's method, -point evaluation takes time ( 2 ). 9. Point-Value Representation The inverse of evaluation is called interpolation determines coefficient form of polynomial from point- value representation For any set * 0 , 0 , 1 , 1 , , 1 , 1 + of point- value pairs such that all the values are distinct, there is a unique polynomial ( ) of degree-bound such that = ( ) for = 0, 1, , 1.

4 Lagrange's formula 1. ( ). = . =0 k( ). Using Lagrange's formula, interpolation takes time ( 2 ). 10. Example Using Lagrange's formula, we interpolate the point- value representation 0, 1 , 1, 0 , 2, 5 , 3, 22 . 1 ( 2)( 3) 3 6 2 +11 6 3 +6 2 11 +6. 1 (0 1)(0 2)(0 3) = =. 6 6. ( 0)( 2)( 3). 0 (1 0)(1 2)(1 3) = 0. ( 0)( 1)( 3) 3 4 2 +3 15 3 +60 2 45 . 5 (2 0)(2 1)(2 3) = 5 =. 2 6. ( 0)( 1)( 2) 3 3 2 +2 22 3 66 2 +44 . 22 (3 0)(3 1)(3 2) = 22 =. 6 6. 1. 6 3 + 0 2 12 + 6. 6. 3 2 + 1. 11. Adding Polynomials In point-value form, addition = + ( ) is given by = + ( ) for any point . : 0 , 0 , 1 , 1 , , 1 , 1. : 0 , 0 , 1 , 1 , , 1 , 1.. : * 0 , 0 + 0 , 1 , 1 + 1 , , 1 , 1 + 1.. +. and are evaluated for the same points. The time to add two Polynomials of degree-bound . in point-value form is ( ). 12. Example We add = + ( ) in point-value form = 3 2 + 1. = 3 + 2 + 1. = (0, 1, 2, 3). : 0, 1 , 1, 0 , 2, 5 , 3, 22. : * 0, 1 , 1, 3 , 2, 13 , 3, 37 +. : * 0, 2 , 1, 3 , 2, 18 , 3, 59 +. 13. Multiplying Polynomials In point-value form, multiplication = ( ).

5 Is given by = ( ) for any point . Problem: if and are of degree-bound , then is of degree-bound 2 . Need to start with extended point-value forms for and consisting of 2 point-value pairs each. : 0 , 0 , 1 , 1 , , 2 1 , 2 1. : 0 , 0 , 1 , 1 , , 2 1 , 2 1.. : * 0 , 0 0 , 1 , 1 1 , , 2 1 , 2 1 2 1.. +. The time to multiply two Polynomials of degree- bound in point-value form is ( ). 14. Example We multiply = ( ) in point-value form = 3 2 + 1. = 3 + 2 + 1. = ( 3, 2, 1, 0, 1, 2, 3) We need 7 coefficients! : 3, 17 , 2, 3 , 1,1 , 0, 1 , 1, 0 , 2, 5 , 3, 22. : * 3, 20 , 2, 3 , 1, 2 , 0, 1 , 1, 3 , 2, 13 , 3, 37 +. : * 3,340 , 2,9 , 1,2 , 0, 1 , 1, 0 , 2, 65 , 3, 814 +. 15. The Road So Far 0 , 1 , , 1 Ordinary multiplication Coefficient Time ( 2 ). 0 , 1 , , 1. 0 , 1 , , 1 representations Evaluation Interpolation Time ( 2 ) Time ( 2 ). 0 , 0 0. 1 , 1 Pointwise multiplication 1 Point-value Time ( ) representations 2 1 , ( 2 1 ) ( 2 1 ). Can we do better? Using fast Fourier Transform (FFT) and its inverse, we can do evaluation and interpolation in time ( log ).

6 The product of two Polynomials of degree-bound can be computed in time ( log ), with both the input and output in coefficient form. 16. Fourier Transform Fourier Transforms originate from signal processing Transform signal from time domain to frequency domain Amplitude Weight Time Frequency Input signal is a function mapping time to amplitude Output is a weighted sum of phase-shifted sinusoids of varying frequencies 17. fast Multiplication of Polynomials Using complex roots of unity Evaluation by taking the Discrete Fourier Transform (DFT). of a coefficient vector Interpolation by taking the inverse DFT of point-value pairs, yielding a coefficient vector fast Fourier Transform (FFT) can perform DFT and inverse DFT in time ( log ). Algorithm 1. Add higher-order zero coefficients to ( ) and ( ). 2. Evaluate ( ) and ( ) using FFT for 2 points 3. Pointwise multiplication of point-value forms 4. Interpolate ( ) using FFT to compute inverse DFT. 18. Complex Roots of Unity A complex th root of unity (1) is a complex number such that = 1.

7 There are exactly complex th root of unity 2 . for = 0, 1, , 1. where = cos + sin( ). Here represents an angle in radians. 2 . Using = cos 2 + sin(2 ), we can . check that it is a root 2 . = 2 = cos(2 ) + sin(2 ) = 1. 1 0. 19. Examples The complex 4th roots of unity are 1, 1, , . where 1 = . The complex 8th roots of unity are all of the above, plus four more 1 1 1 1 . + , , + , and . 2 2 2 2 2 2 2 2. For example 2. 1 1 2 2. + = + + = . 2 2 2 2 2. 20. Principal th Root of Unity The value 2 . = . is called the principal th root of unity. All of the other complex th roots of unity are powers of . The complex th roots of unity, 0 , 1 , , 1 , form a group under multiplication that has the same structure as ( , +) modulo . = 0 = 1 implies + + mod . = = . 1 = 1. 21. Visualizing 8 Complex 8th Roots of Unity imaginary 82 = .. 1 1 . 83 = + 18 = +. 2 2 2 2. 84 = 1 80 = 88 = 1. 1 1 real 1 1 . 85 = 87 = . 2 2 2 2.. 86 = . 22. Cancellation Lemma For any integers 0, 0, and > 0, . = . Proof 2 2 .. = = =.

8 For any even integer > 0, 2 = 2 = 1. 6. Example 24 = 4. 6 6. = 2 24 = . 6 2 2 . 24 = 24 4 = 4. 23. Halving Lemma If > 0 is even, then the squares of the complex th roots of unity are the 2 complex 2th roots of unity. Proof 2. By the cancellation lemma, we have = 2 for any nonnegative integer . If we square all of the complex th roots of unity, then each 2th root of unity is obtained exactly twice + 2 2. 2. = 2 + = 2 = 2 = . + . Thus, and 2. have the same square 24. Summation Lemma For any integer 1 and nonzero integer not 1 . divisible by , =0 = 0. Proof 1 1. Geometric series =0 = 1. 1. 1 1 1 1. =0 = 1 = 1 = 1 =0.. Requiring that not be divisible by ensures that the denominator is not 0, since = 1 only when k is divisible by . 25. Discrete Fourier Transform (DFT). Evaluate a polynomial ( ) of degree-bound at the complex th roots of unity, 0 , 1 , 2 , , 1 . assume that is a power of 2. assume is given in coefficient form = ( 0 , 1 , , 1 ). We define the results , for = 0, 1, , 1, by 1.

9 = = =0 . The vector = ( 0 , 1 , , 1 ) is the Discrete Fourier Transform (DFT) of the coefficient vector = 0 , 1 , , 1 , denoted as = DFT ( ). 26. fast Fourier Transform (FFT). fast Fourier Transform (FFT) takes advantage of the special properties of the complex roots of unity to compute DFT (a) in time ( log ). Divide-and-conquer strategy define two new Polynomials of degree-bound 2, using even-index and odd-index coefficients of ( ) separately . 0 = 0 + 2 + 4 2 + + 2 2 1.. 1 = 1 + 3 + 5 2 + + 1 2 1. = 0 2 + 1 ( 2 ). 27. fast Fourier Transform (FFT). The problem of evaluating ( ) at 0 , 1 , , 1. reduces to 1. evaluating the degree-bound 2 Polynomials 0 ( ). and 1 ( ) at the points 0 2 , 1 2 , , 1 2. 2. combining the results by = 0 2 + 1 ( 2 ). Why bother? The list 0 2 , 1 2 , , 1 2 does not contain . distinct values, but 2 complex 2th roots of unity Polynomials 0 and 1 are recursively evaluated at the complex th roots of unity 2 2. Subproblems have exactly the same form as the original problem, but are half the size 28.

10 Example = 0 + 1 + 2 2 + 3 3 of degree-bound 4. 40 = 1 = 0 + 1 + 2 + 3. 41 = = + 1 2 3 . 42 = 1 = 0 1 + 2 3. 43 = = 0 1 + 2 + 3 . Using = 0 2 + 1 2. = 0 + 2 2 + 1 + 3 2. 40 = 1 = 0 + 2 + 1( 1 + 3 ). 41 = = 0 2 + ( 1 3 ). 42 = 1 = 0 + 2 1 1 + 3. 43 = = 0 2 ( 1 3 ). 29. Recursive FFT Algorithm RECURSIVE-FFT . 1 , - is a power of 2. 2 if = 1. 3 then return basis of recursion 2 . 4 is principal th root of unity 5 1. 6 0 ( 0 , 2 , , 2 ). 7 1 ( 1 , 3 , , 1 ). 0. 8 0 RECURSIVE-FFT 0 = 0 2 = 0 ( 2 ). 1. 9 1 RECURSIVE-FFT 1 = 1 2 = 1 ( 2 ). 10 for 0 to 2 1. 0 1. 11 do + . 0 1 + 2. 12 +( 2) since = . 13 compute iteratively 14 return . 30. Why Does It Work? For 0 , 1 , 2 1 (line 11). 0 1. = + . 0. = 2 + 1 2 . = . For 2 , 2+1 , , 1 (line 12). + 2 = 0 1. + 2 + 2. = 0 + 1 since = . + . 0. = 2 + 2. 1 2 . + . 0. = 2 + + 2. 1 2 + . since 2 + = 2 . + 2. = . 31. Input Vector Tree of RECURSIVEFFT( ). ( 0 , 1 , 2 , 3 , 4 , 5 , 6 , 7 ). ( 0 , 2 , 4 , 6 ) ( 1 , 3 , 5 , 7 ). ( 0 , 4 ) ( 2 , 6 ) ( 1 , 5 ) ( 3 , 7 ).