Fast Fourier Transform and Polynomial Multiplication Techniques
Explore efficient algorithms for multiplying polynomials and integers using Fast Fourier Transform, allowing for fast computations in polynomial operations. Understand the implications of converting coefficients into point-value representation and leveraging specific values for computational advantages.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
CMPT 405/705 Design & Analysis of Algorithms February 16, 2022
Motivation: We saw an algorithm that given 2 integers of length n A = an-1an-2 a1a0and B = bn-1bn-2 b1b0 computes their product in time O(n1.58) And then I said we could actually do it in time O(n polylog(n)) Today we ll see how to do it. Idea: Let s consider a more general problems: Multiplication of polynomials
Multiplication of polynomials : Given two polynomials by their coefficients P(x) = an-1xn-1 + an-2xn-2+ a1x + a0 Q(x) = bn-1xn-1 + bn-2xn-2+ b1x + b0 Example: P(x) = 2x + 1 Q(x) = 3x2- 5x + 2 R : = P*Q deg(R) =3 R(x) = (2*3)x3+ (3*1 2*5)x2+ (1*(-5) + 2*2)x + 2 = R(x) = 6x3 7x2 x + 2
Multiplication of polynomials : Given two polynomials by their coefficients P(x) = an-1xn-1 + an-2xn-2+ + a1x + a0 Q(x) = bn-1xn-1 + bn-2xn-2+ + b1x + b0 Compute R(x) = P(x)*Q(x) as a polynomial. That is compute the coefficients of the polynomial R. The polynomial R has degree < 2n-1, and so it has at most 2n coefficients Q: how can we use it to compute product of integers? A: Given two integers A = an-1an-2 a1a0and B = bn-1bn-2 b1b0 Define the polynomials: P(x) = an-1xn-1 + an-2xn-2+ + a1x + a0 Q(x) = bn-1xn-1 + bn-2xn-2+ + b1x + b0
Multiplication of polynomials : Q: how can we use polynomials to compute product of integers? A: Given two integers A = an-1an-2 a1a0and B = bn-1bn-2 b1b0 Define the polynomials: P(x) = an-1xn-1 + an-2xn-2+ + a1x + a0 Q(x) = bn-1xn-1 + bn-2xn-2+ + b1x + b0 Then A = P(10) B = Q(10) Let R = P*Q computed in O(n polylog(n)) time A*B = P(10)*Q(10) = R(10)
Example We want to find a poly P(x) of degree 2 Satisfying: P(1) = 2 P(5) = 0 P(7) = 3 Formula: P(x) = 2 * (x-5)(x-7) / (1-5)(1-7) + 0 * (x-1)(x-7) / (5-1)(5-7) + 3 * (x-1)(x-5) / (7-1)(7-5) Then P(1) = 2, P(5) = 0, P(7) = 3
Example I lied about the following: To convert coefficients into point-value representation: (1,P(1)), (2, P(2)), (3, P(3)) We will not use the values 0,1,2,3 n NO! We will use values 1, , 2, 3, n-1, ( , P( )), ( 2, P( 2)) where is the n th root of unity (in complex numbers) Why these specific value? Because for them we can multiply Matrix x vector in time O(n log(n)) + we can go back to the representation with coefficients.
FFT: For a vector of length n : (a0,a1, ,an-1) of reals, its Discrete Fourier Transform is the following vector: A(1= 0) = a0+ a1+ a2+ + an-1 A( 1) = a0+ a1 + a2 2+ + an-1 n-1 A( 2) = a0+ a1 2+ a2 4+ + an-1 2(n-1) A( n-1) = a0+ a1 n-1+ a2 2(n-1)+ + an-1 (n-1)(n-1) We convert a vector A of length n into another vector of length n. This vector is the evaluation of the corresponding polynomial in points 1, , 2 n-1
Back to multiplication of polynomials : Given two polynomials: P(x) = an-1xn-1 + an-2xn-2+ + a1x + a0 Q(x) = bn-1xn-1 + bn-2xn-2+ + b1x + b0 Compute R = P*Q a polynomial of degree <2n. 1. Think of P,Q as polynomials of degree 2n (with a bunch of zero coefficients) 2. Compute FFT of P: P( 0), P( 1), ,P( 2n-1) 3. Compute FFT of Q: Q( 0), Q( 1), ,Q( 2n-1) 4. Compute R( i) = P( i)*Q( i) for i=0 2n-1 5. Compute the coefficients of R using inverse-FFT
Questions? Comments?
