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
x ?8x ?16x ? 0, x?0? ? 0, x?0? ? 2

During 2008 the average number of beds required per day at St Hallam's hospital was 1800.  During the first 50 days of 2008 the average daily requirement for beds was 1830, with a

log8-log3


If the area of a small size pizza is 78.5 in 2 , what size pizza box would required for the small pizza? (Note: Pizza boxes are calculated according to the length of one side.)

1. Show that there do not exist integers x and y for which 110x + 315y = 12. 2. If a and b are odd integers, prove that a 2 +b 2 is divisible by 2 but is NOT divisible by 4. H

Q. Explain Binomial Distribution? Ans. The binomial distribution occurs when you are considering the probability function of a binomial experiment. Binomial Experiment



E1) Try and see the order in which different children fills numbers in the grid above. My claim is that all of them would fill in the ones, the fives and the tens first. Test my hy