Questions tagged [fast-fourier-transform]

Use this tag for questions related to the fast Fourier transform, an algorithm that samples a signal over a period of time (or space) and divides it into its frequency components.

1
vote
3answers
801 views

What is the Permutation Matrix in FFT DFT Factorization?

Given: $$F_N = \frac{1}{\sqrt{N}} \begin{bmatrix} 1&1&1&1&\cdots &1 \\ 1&\omega&\omega^2&\omega^3&\cdots&\omega^{N-1} \\ 1&\omega^2&\omega^4&\omega^...
1
vote
1answer
41 views

Obtain Fourier Coefficients from Discrete Fourier Transform

The Fast Fourier Transform $y[k]$ of length $N$ of the length-$N$ sequence $x[n]$ is defined as: $$y[k] = \sum_{n=0}^{N-1}e^{-2\pi i \frac{k n}{N}}x[n].$$ I want to know how are the $y[k]$ related ...
0
votes
0answers
171 views

Does the ring in this Fast Fourier Transform image of a hexagonally close packed structure have significance?

I have a picture of a hexagonally close-packed lattice and I took the FFT of the image using ImageJ. Below are the results. I expected the FFT to also be a lattice with reciprocal lattice spacing, I ...
1
vote
1answer
981 views

Complexity of FFT algorithms (Cooley-Tukey, Bluestein, Prime-factor)

I need to be able to explain the complexity of three Fast Fourier Transform algorithms: Cooley-Tukey's, Bluestein's and Prime-factor algorithm. Unfortunatelly, I'm a little lost in the process. ...
1
vote
0answers
59 views

Sampling and the Discrete Fourier Transform

Suppose $f:\mathbb{R}\rightarrow\mathbb{C}$. We'd like to take the Fourier Transform of this function, defined as $$F(s) = \int_{-\infty}^\infty f(x)e^{-i \, 2\pi \, s \, x}dx.$$ However, a computer ...
0
votes
1answer
55 views

derive solution of possion equation ; electrodynamics problem

Hi I had posted the same post 2 days ago but I am posting it again because of my bad handwriting. I apologize to the man who wanted to read my post. I am not familiar with the tool which is used in ...
0
votes
0answers
475 views

Why FFT algorithm (Cooley-Tukey) takes O(nlogn)?

I was wondering how this algorithm can be formally interpreted with an upper bound n*log(n). There's some formal proof for this? I would appreciate if somebody can help me. Thank you.
0
votes
0answers
27 views

Can any integral of this form be written as a sum of convolutions?

Does the second equality always hold? $$ I(x) \equiv \int dy F(y,x-y) = \sum_{i=1}^{N}\int dy f_i(y)g_i(x-y) $$ Motivation: The first integral is not obviously a convolution that I could calculate ...
1
vote
0answers
37 views

Why is there periodicity in the output of Richard Voss' fractional Brownian motion?

I am trying to figure out why the output of fractional Brownian motion (fBm) as described by Richard Voss (Random fractal forgeries. In: Fundamental Algorithms for Computer Graphics, R. A. Earnshaw (...
0
votes
1answer
220 views

What's the formulation of N-point radix-N for NTT

We can write the formulation for the buttlerfly function applied in FFT as \begin{align*}y_0 &= x_0 + x_1,\\ y_1 &= x_0 - x_1. \end{align*} As seen here. For FFT (Fast Fourier Transform) we ...
0
votes
0answers
350 views

Worked out FFT example per Hand

Can anyone please show me the worked out example of FFT. Suppose for the signal x = (1/2, 1/4, 0, 1/4 , 1/2, 1/4, 0, 1/4). What I think I know: First I need to do the bit reversing, I get x = (1/...
1
vote
0answers
279 views

analyze convolution in spatial domain against multiplication in frequency domain

Lets say I have a image of $NxN$ and a separable filter that I want to apply on it. there are 2 ways to do that: 1. By convolution in spatial domain. 2. By multiplication in frequency domain. I need ...
2
votes
0answers
721 views

Solving a simple Schrodinger equation with Fast Fourier Transforms

While trying to solve a stochastic Gross-Piaevskii equation I have found a problem that can be tracked down to something buggy occuring in the simplest Schrodinger equation possible: $\partial_t \psi ...
1
vote
0answers
99 views

Can downsampling create energy at the Nyquist frequency?

I am a bit surprised by the following and would like to share it with you. I expect I am mistaken somewhere and will be happy to be corrected. I have searched StackExchange not only in Mathematics ...
4
votes
3answers
557 views

Negacyclic FFT multiplication

I am using an FFT to multiply polynomials. Because I want the program to be as fast as possible I am leaving away the zero padding. For example, if we want to calculate: $(58 + 37x + 238x^2 + 155x^3)^...
1
vote
1answer
43 views

Find a polynomial in $\mathbb{Z}_{41}$

Find a $7^\text{th}$ degree polynomial $p(x)$ in $\mathbb{Z}_{41}[x]$, so that $$ p(14^i) = i\pmod{41}\ \forall i = 0,1,\ldots,7. $$ Hint: $3$ is the $8^\text{th}$ primitive root of unity and $3 \...
2
votes
0answers
649 views

Inverse of a Toeplitz matrix with FFT-based methods

I have a covariance matrix $Q$ and need to find $Q^{-1}$. Here, $Q$ is a Toeplitz matrix. I want to calculate the inverse of the matrix with FFT-based methods rather than the conventional ones like ...
4
votes
1answer
67 views

Can't extract odd function with FFT

I can't correctly extract spectrum from data points of odd function (e.g. $\cos\left(\frac23\pi x\right)$, $16$-points vector $[1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1]$), instead of one function I get a ...
2
votes
1answer
1k views

Recursive FFT java implementation [closed]

Given below is my java program for FFT. For the input {0,2,3,-1} its returns a false output in complex point representation. ...