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
What is the objective of lipids metabolism ? After studying this unit, you will be able to: 1. explain how fatty acids are oxidized for the production of energy, 2. describe


On your geometry test you have two triangles: ?ABC and ?MNO. You are told that ?A ? ? M and that ?B ? ? N. Which statement is also true?

The value of y that minimizes the sum of the two distances from (3,5) to (1,y) and from (1,y) to (4,9) can be written as a/b where a and b are coprime positive integers. Find a+b.


Which general famously stated 'I shall return'? A. Bull Halsey B. George Patton C. Douglas MacArthur D. Omar Bradley

how many pendulum swings will it take to walk across the classroom

Iran is trying to decide whether it should pursue its nuclear weapons program, and its decision will be affected in large measure by what it expects the United States to do. Your a

The null hypothesis It is the hypothesis being tested, the belief of a specific characteristic for illustration, US Bureau of Standards may walk to a sugar making company along

what is break even point and how can it helps managers to make decisions?