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
In a certain class, one half of the male students and two thirds of the female students speak French. If there are three fourths as many girls as boys in the class. What fraction o

Q. What is Combination Formula? Ans. The difference between combinations and permutations is that permutations take ordering into consideration, whereas combinations do no

Solve following  x - x  e 5 x + 2   = 0 . Solution : The primary step is to factor an x out of both terms. DO NOT DIVIDE AN x FROM BOTH TERMS!!!! Note as well that it i

The probability that a certain region in mexico will be hit by a hurricane in any given year is .06. What is the probability that the region will be hit by at least one hurricane i

bananas are on sale for 3 pounds for $2. At that price how many pounds can you buy for $22

I need expert who can solve 10 set of PDE with constant of integration.

Area between Curves In this section we will be finding the area between two curves. There are in fact two cases that we are going to be looking at. In the first case we des

What is Angles? An angle is made up of two rays with a common endpoint, which is called the vertex. The sides of the angle are rays. An angle is denoted by "θ". When two li

20% of the total quantity of oil is 40 litres find the total quantity of oil in litres