1
vote
1answer
47 views

Find coefficients of polynomial that has zeros at certain points

Given a list of values z0, z1, ..., zn-1 (possibly with repetitions), show how to find the coefficients of a polynomial P(x) of degree-bound n + 1 that has zeros only at z0, z1, ..., zn-1 (possibly ...
0
votes
0answers
101 views

Bluestein Algorithm for Fast Fourier Transform

Can anyone demonstrate the full algorithm of Fast Fourier Transform? Because from Wikipeida and other internet sources, I saw that there are different ways of padding. So can anyone tell me when the ...
2
votes
0answers
72 views

A question on algorithm complexity

It is well-known that the evaluating the Discrete Fourier Transform definition directly has a complexity $O(N^{2})$ for a signal with bandwidth $N$. How to see or show that the fast Fourier transform ...
1
vote
1answer
115 views

In-place inverse of DFT?

I'm trying to understand (by implementing) the Cooley Tukey algorithm for an array $[x_0, \dotsc, x_{2^N-1}]$ of real valued data. Since the input data is real valued, the spectrum will have ...
2
votes
1answer
126 views

Cooley-Tukey FFT with arbitrary radices

The radix-2 FFT using Cooley-Tukey utilises two interleaved transforms of length $N/2$, and you can see near the bottom of that section that we can find the second half of the original transform by ...