Fft algorithm, Mathematics

(a) Using interpolation, give a polynomial f ∈ F11[x] of degree at most 3 satisfying f(0) = 2; f(2) = 3; f(3) = 1; f(7) = 6

(b) What are all the polynomials in F11[x] which satisfy f(0) = 2, f(2) = 3, f(3) = 1, f(7) = 6?

(2) Hand in your completed worksheets from labs \Fast Multiplication" and \Fast Multiplication II". Hand it in to me by saving the worksheet to a le (after making sure all the cells you want are evaluated) and then emailing it to me.

(3) Let F be a eld and a(x) ∈ F[x] be a polynomial of degree n - 1 = 3k - 1.

(a) Show that a(x) can be decomposed into

a(x) = b(x3 ) + x . c(x3) + x2. d(x3);

where b(x), c(x) and d(x) are polynomials in F[x] of degree at most n/3 - 1 = 3k - 1 - 1.

(b) Show that if ω ∈ F is a primitive nth root of unity, then a(x) can be evaluated at all the powers of ! by recursively evaluating b(x), c(x) and d(x) at the powers of ω3.

(c) Put all of this together into an algorithm similar to FFT for evaluating a(x) at the powers of ω.

(d) What are the number of additions and number of multiplications in F that this algorithm does on input size n?

(e) The set S = {1, ω, ω2n -1} has some special properties that make this "3-ary" FFT (and the "binary" FFT from class) work. What properties does a set S need to be used in this way (or in the original FFT algorithm)? Can you fi nd any other sets that have these properties?


Posted Date: 2/26/2013 12:53:47 AM | Location : United States

Related Discussions:- Fft algorithm, Assignment Help, Ask Question on Fft algorithm, Get Answer, Expert's Help, Fft algorithm Discussions

Write discussion on Fft algorithm
Your posts are moderated
Related Questions
can someone help me with a statistics quiz?

Solve for x: 4 log x = log (15 x 2 + 16) Solution:              x 4 - 15 x 2 - 16 = 0                (x 2 + 1)(x 2 - 16) = 0                x = ± 4   But log x is

Case 1: Suppose we have two terms 8ab and 4ab. On dividing the first by the second we have 8ab/4ab = 2 or 4ab/8ab = (1/2) depending on whether we consider either 8ab or 4ab as the

Properties of t distribution 1. The t distribution ranges from - ∞ to ∞ first as does the general distribution 2. The t distribution as the standard general distribution is

Regression line drawn as Y=C+1075x, when x was 2, and y was 239, given that y intercept was 11. calculate the residual

Subtraction - Vector arithmetic Computationally, subtraction is very similar.  Given the vectors a → = (a 1 , a 2 , a 3 ) and b → = (b 1 , b 2 , b 3 ) the difference of the t

I need help with my calculus

Interpretations of derivatives. Example:   Find out the equation of the tangent line to                                       x 2 + y 2   =9 at the point (2, √5 ) .

Assume that Y 1 (t) and Y 2 (t) are two solutions to (1) and y 1 (t) and y 2 (t) are a fundamental set of solutions to the associated homogeneous differential equation (2) so, Y