Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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.

12
votes
3answers
4k views

How does FFT work?

For five years I tried to understand how Fourier transform works. Read a lot of articles, but nobody could explain it in simple terms. Two weeks ago I stumbled upon the video about a 100 years old ...
4
votes
2answers
169 views

Application of the FFT

A discrete Fourier transformation of N-th order is the map $F:\mathbb{C}^N\to\mathbb{C}^N$ given by $$w=Fz\qquad w_k=\frac{1}{\sqrt{N}}\sum_{j=0}^{N-1}\zeta_N^{jk}z_j,$$ where $\zeta_N=e^{-\frac{2\pi ...
4
votes
2answers
2k views

Solve Poisson Equation Using FFT

I am trying to solve Poisson equation using FFT. The issue appears at wavenumber $k = 0$ when I want to get inverse Laplacian which means division by zero. We have ${\nabla ^2}\phi = f$ Taking ...
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 ...
4
votes
2answers
532 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)^...
3
votes
2answers
68 views

Value Proposition of Fourier Analysis?

I am a software engineer trying to wrap his head around Fast Fourier Transform (FFT). Specifically, I need to implement it as part of some software I am writing. Now I can handle the implementation of ...
3
votes
1answer
88 views

Omitting twiddle factors in Cooley–Tukey FFT algorithm

The discrete Fourier transform $$ X_k = \sum_{m=0}^{n-1} x_m e^{-2\pi ikm/n} $$ can be computed via Cooley–Tukey FFT algorithm The key of the algorithm is the butterfly transform, given by $$ X_k = ...
3
votes
1answer
567 views

Multivariate Polynomial Multiplication using Fast Fourier Transform (FFT)

I am trying to find the coefficients of multiplications of 2 $N$-variate polynomials using $N$-dimensional fast Fourier transform (FFT) on MATLAB. My approach so far is as follows: Based on this post,...
3
votes
1answer
48 views

Get an approximate factorization for a number $n$

For a given number $n$, I am interested in the closest number that can be written as a product of a given set of prime factors. More precisely, I am interested in a solution of the following problem ...
3
votes
0answers
50 views

Translation of the work of Gauss where the fast Fourier transform algorithm first appeared

As far as I know, the fast Fourier transform algorithm first appeared in 1805 in "Theoria interpolationis methodo nova tractata", by Carl Friedrich Gauss. This work is available in Latin, which, to ...
3
votes
0answers
2k views

How to implement NTT( Number theoretic transform) [closed]

I am having tough time while implementing NTT. After reading lot of tutorials on FFT and NTT from http://www.apfloat.org/ntt.html, http://codeforces.com/blog/entry/43499 and some others, I have ...
3
votes
0answers
37 views

Does the fast Fourier transform have equivalents in other transforms?

I've seen the Mellin transform described as the "multiplicative" analogue to the Laplace transform, as well as the Fourier transform when $x\to\log y$. Would a discrete Mellin transform be able to ...
3
votes
1answer
119 views

How to compute $p(x)=\prod_{k=0}^{n-1}(x-z_k)$ using the FFT with complexity of O(nlog^2 n)?

I've a question and in its last step I'm required to find the above product (I need the coefficients of the result of that product as my final answer). It seems that FFT can be used to compute it. I ...
3
votes
0answers
108 views

How to decompose a 2d shape into sin and cosin modes?

Assume that you have a circle with radius $r_0$, then you keep adding cosine modes as below: $r=r_0+a_1\cos(1\theta)+a_2\cos(2\theta)+a_3\cos(3\theta)+a_4\cos(4\theta)+~...$ if you plot this as ...
2
votes
2answers
92 views

What area's of mathematics are needed to make a basic understanding of the FFT algorithm ?

I know FFT is used in signal processing ( at last check), the Lucas-Lehmer Test and probably many other things. But what is the Fast Fourier Transform and what area's of math will help me understand ...
2
votes
1answer
828 views

How does the phase plot of Fourier transform of sine wave look like?

I found that transform of Sin(t) look like THIS If its amplitude look like THIS How does its phase look like? I have found one question on stack which is similar to my question but does not ...
2
votes
1answer
44 views

Indexing of Discrete Fourier Transforms

I was looking at the Discrete Fourier Tranform section in these notes and I'm very confused about how the transform is being indexed. There, a list of the form $f(x_n)$ is given where $x_n$ takes on ...
2
votes
2answers
504 views

The best textbook on Fourier Transformation for beginners

I am absolutely new to Fourier Transformations. I have a bit of background in Trigonometry. Which text book would you recommend to learn Fourier transforms from the very basics?
2
votes
1answer
25 views

Could families of “Airys” and “Bairys” of integer “frequencies” be useful?

A very famous family of functions are the complex exponentials and in the case of real valued functions, the sin and cos functions. They are related by the famous Euler formulas: $$\exp(i\phi) = \cos(...
2
votes
4answers
69 views

Intuition of fft over time to frequency

I understand how FFT (DFT) works. It acts as a change of basis. However, while many websites describe fft as a method that convert time domain stuff to frequency domain stuff, I still do not know why ...
2
votes
1answer
111 views

How to get the frequency of a time-domain signal with limited sample length?

Let's say there is a signal who only has one peak in its power spectrum. I would like to know the frequency at which the peak is (the magnitude of power is not important to me). But I only have very ...
2
votes
1answer
75 views

Is it possible to solve the following PDE without using Fourier transform?

Solve the following non-homogenous heat equation:$$ \frac{\partial u}{\partial t} = a^2 \frac{\partial ^2 u}{\partial x^2} + \epsilon \sin(k_0x)$$ on the domain $-\infty \lt x \lt \infty $, with ...
2
votes
1answer
1k views

Relation between Discrete Fourier Transform and Fourier Series

I was given a task to obtain a Fourier Series approximation from the DFT (Discrete Fourier Transorm), more exactly fft function from MATLAB. I know that a Fourier Series has the form $\frac{a_0}{2}+\...
2
votes
1answer
78 views

Find the fourier series representation of a function

Consider the function $f(x) = \begin{cases} \frac{\pi}{2}+x & & x \in (-\pi, 0] \\ \frac{\pi}{2}-x & & x \in (0, \pi]\\ \end{cases}$ extended 2$\pi$ periodically to $\mathbb{R}$. ...
2
votes
1answer
540 views

Compute Fourier coefficients of spline fit to data

Suppose you have data $$\{(x_i, -1^{i+1})\}_{1\dots N}, \quad x_1=0<x_i<x_{i+1}<x_N=2\pi \ \forall i \in\{2,\dots N-1\} $$ In other words, we have a sequence of $y=\pm1$ values at distinct ...
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. ...
2
votes
0answers
41 views

DFT is not a sampling of FT?

From wikipedia: The discrete Fourier transform (DFT) converts a finite sequence of equally-spaced samples of a function into a same-length sequence of equally-spaced samples of the discrete-time ...
2
votes
0answers
42 views

Any Efficient Multiplication with a Primitive Root over Prime Field?

Description: to multiply the "complex unit" $w^{N/4}$ over a prime field, i.e., $w^N \equiv 1 \bmod (\,p)$ (suppose $p, N$ do provide such primitive root). I am implementing the radix-4 Number ...
2
votes
1answer
67 views

How to minimize sum of matrix-convolutions?

Given $A$, what should be B so that $\lVert I \circledast A - I \circledast B \rVert _2$ is minimal for any $I$? $I \in \mathbb{R}^{20x20}, A \in \mathbb{R}^{5x5}, B \in \mathbb{R}^{3x3}. $ Note ...
2
votes
0answers
29 views

Increasing frequency resolution of FFT on a windowed sample of a signal

Okay, this gets a bit technical, let me explain the background. In doing loudspeaker measurements for its direct sound in normal rooms that have reflections, what we do is measure the whole impulse ...
2
votes
1answer
222 views

Efficient matrix-vector multiplication for “partial” Hadamard matrices

I've recently been working on an algorithm for bilinear systems in the form $y = (Lw) \odot (Rx)$, where $\odot$ denotes the elementwise product between two matrices of compatible sizes. In the above, ...
2
votes
0answers
101 views

Discrete versions of the Fourier Slice-Projection Theorem

I understand the continuous version of the Fourier Slice-Projection theorem, which says that given a (nice enough) function $f:\mathbb{R}^3\to\mathbb{C}$ the following operations give the same result: ...
2
votes
0answers
203 views

Unable to solve nonlinear equation using scipy.optimize.fsolve

I am using scipy.optimize.fsolve to solve a nonlinear equation in Fourier pseudospectral space but it does not work. It gives the same output as the input u0, which is a trivial solution. The equation ...
2
votes
0answers
95 views

How to solve least square quadratic problem using FFT

Let A, B, C and D be some matrix and x be a vector, I want to solve the following optimization problem: $$ \min_x \| Ax -B\|^2_2 + \| Cx-D\|^2_2 $$ my solution: $$ J = \| Ax -B\|^2_2 + \| Cx-D\|^2_2 ...
2
votes
0answers
138 views

Period-based Fast Fourier transform

I have a list of events times $t_n$ in which I would like to find repeating patterns in the temporal density (how many events per second). And finally plot how likely it is to find a pattern of period ...
2
votes
0answers
559 views

Fourier Series: Music from a Piano vs Keyboard [closed]

So, I've been working on a project to compare the Fourier Series of a Piano versus that of a Keyboard. I've computed the FFT on MATLAB using this code: dt = 1/fs t = (1:length(data))*dt X=fft(data) ...
2
votes
0answers
93 views

Does NTT have an upper bound?

I'm working with NTT (Number theoretic transform) to reduce the complexity of a polynomial multiplication. For this, I'm using $P = 2^{64}-2^{32}+1$ to generate the primitive root $\omega_N$ needed by ...
2
votes
0answers
708 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
1answer
2k views

Find the solution of the Dirichlet problem in the half-plane y>0.

Find the solution of the Dirichlet problem in the half-plane $y>0$. $${u_y}_y +{u_x}_x=0, -\infty<x<\infty,y>0$$ $$u(x,0)=f(x),-\infty<x<\infty$$ $u$ and $u_x$ vanish as $$ \lvert ...
1
vote
3answers
776 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
947 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
1answer
28 views

Question about the FFT version of the gradient of a function.

We know that for a sufficiently smooth function $f:\mathbb{R}^{3}\to\mathbb{R}$, its Fourier Transform $\hat{f}(\mathbf{k}) \colon= \mathcal{F}\{f\}$ should satisfy (using integration by parts): $$\...
1
vote
1answer
21 views

Can FFT be used to cluster sound waves based on their similarity?

I am new to this so apologies if the question appears trivial. Say we have n sound files and we want to cluster them to identify which ones are more similar. I ...
1
vote
1answer
39 views

Coordinates of a vector FFT

I was reading a paper about DFT, at the end he got the relations $Y=\frac{1}{\sqrt N}W_n \cdot y$ and $y=\frac{1}{\sqrt N}W_n \cdot Y$, where $y$ is a vector and $Y$ is the coordinates of that vector ...
1
vote
1answer
14 views

Why is the dot product of two columns $j$ and $k$ in FFT equal to $1+w^{j-k} + \dots + w^{(n-1)(j-k)}$?

The matrix is of the following form: $\begin{pmatrix} 1 & 1 & \cdots & 1 & 1 \\ 1 & w & \cdots & w ^{n-2} & w^{n-1} \\ \vdots & \vdots & \ddots & \vdots &...
1
vote
1answer
73 views

How to interpret the results of a Discrete Fourier Transform

I'm trying to understand the Discrete Fourier Transform so that I can understand the Fast Fourier Transform so that I can write a program to calculate it. I know that there are existing libraries that ...
1
vote
1answer
298 views

Parseval identity in FFT

I was recreating in Matlab a certain function using FFT. In particular I was interesting in knowing how modes are sufficient to approximate quite well my function. To do that, I calculate the norm ...
1
vote
1answer
99 views

Approximate Factorization of a Natural Number

I'm implementing the Cooley-Tukey algorithm for computing Discrete Fourier transforms. It so happens that it breaks down a problem of size $n = pq$ into $p$ chunks of size $q$. Given that factoring ...
1
vote
3answers
51 views

What is $\sin(\frac{\pi}{2}-\frac{n\pi}{2})$ equal to?

I'm having huge trouble with figuring out fourier series as soon as I'm not dealing with a really simple function. I found a solution to my problem (fourier series for $|cos(x)|$, I'm troubled by the ...
1
vote
1answer
30 views

Why this time-frequency representation of a pure sine function with Stockwell Transform is different in the boundary?

This time-frequency decomposition was made with Stockwell Transform to a pure sine function and graphed with matlab. But as you can see in the boundary of the image the pattern is different. I need to ...