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.

2 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). 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.

3 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.

4 12 6 14 5 + 20 4 18 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.

5 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. 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.

6 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.

7 = 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 = ( ). 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.

8 = 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 ). The product of two Polynomials of degree-bound can be computed in time ( log ), with both the input and output in coefficient form.

9 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 ( ).

10 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. 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.