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
Manuel is a cross-country runner for his school’s team. He jogged along the perimeter of a rectangular field at his school. The track is a rectangle that has a length that is 3 tim

Describe the Types of triangles ? Triangles can be classified according to the lengths of the sides or the measures of the angles. 1. Naming triangles by sides An

Give a Definition of Perimeter and Area? Perimeter is the distance around a flat (2-dimensional) shape. Area is the amount of space taken up by a flat (2-dimensional) shape. is


Factoring Out a Common Monomial Factor? Say you have a polynomial, like 3x 4 y - 9x 3 y + 12x 2 y2 z and you want to factor it. Your first step is always to look for t


Determine the equation of the tangent line to r = 3 + 8 sinθ at θ = Π/6. Solution We'll first need the subsequent derivative. dr/dθ = 8 cosθ The formula for the deriv

Tests for an Ideal Index Number 1. Factor Reversal Test Factor Reversal Test indicates that when the price index is multiplied along with a quantity index that is factors

Illustration of Rank Correlation Coefficient In a beauty competition two assessors were asked to rank the 10 contestants by using the professional assessment skills. The resul

The base of a right cylinder is the circle in the xy -plane with centre O and radius 3 units. A wedge is obtained by cutting this cylinder with the plane through the y -axis in