# 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.

219 questions
583 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,...
32 views

### Artificially improving the spectral power of a low frequency signal

First of all, I have to state upfront that I am not sure if this question is valid. Essentially, my question pertains to the frequency of a time series with measurement data. I obtained the ...
128 views

### Optimized convolution by FFT / complex multiplication / IFFT

I have some optimization questions about real time partioned convolution by multiplication in the frequency domain. Now my process looks as follows: Initialization: a symmetric FIR impulse response ...
844 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 ...
171 views

45 views

### Use of FFT with a different definition of multiplication operator

FFT enables us to perform multiplication of polynomials in O(nlogn), where "multiplication" is the standard multiplication over the complex numbers. Is there a general procedure to extend this use of ...
59 views

### What does the imaginary part of a set of polar coordinates represent before and after funning an FFT?

My colleague and I are trying to learn stuff that is way above our pay grade. We are curious about the nature of the FFT. We realize that we will most likely not understand the inner workings of the ...
80 views

### Is $fft^{-1}(fft(x)\times fft(y))$ integer?

I have some troubles with the following question: Let ($x_0, x_1, ..., x_{N-1}$) and ($y_0, y_1, ..., y_{N-1}$) be two sequences of integers from the set {$0,1,...,9$}. Let ($p_0, p_1, ..., p_{N-1}$) ...
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 ...
128 views

### Why does the Discrete Fourier Transform and the Fast Fourier Transform give different results?

I have a function $$f(t) = \begin{cases} a(1-a|t|) &\text{if } |t|<\dfrac{1}{a} \\[6pt] 0 &\text{if } |t|>\dfrac{1}{a} \end{cases}$$ Here is what the function looks like for $a=2$: ...
321 views

### How to Prove the Fourier Transform of Vertical Line Mathematically?

I've tried to do Fourier transform in Matlab of vertical line. Basically, I make matrix A having size 100x100 and give the value 1s in certain number of coloumn vector, whereas the others is 0s. Here ...
226 views

### Optimization for getting amplitude of FFT results for real signals

I need to compute amplitude of FFT result for real signals, which means that I don't need the precise result of FFT or phase information of the result. So I think I don't need to implement the ...
62 views

### Vector valued polynomial composition; Computational complexity

Let $$P:\mathbb{R}^n\to\mathbb{R}^n$$ be a vector valued polynomial. What is the computational complexity of the composition of two such polynomial? Can the Fast Fourier Transform be employed on ...
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 ...
142 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 ...
561 views

### Why, traditionally, does FFT use complex numbers as a wrapper for magnitude and phase?

I've read questions like this one, this one, and this one which ask why we use complex numbers instead of real numbers, and that's one half of the question, but the other half, which I've never seen ...
431 views

### NTT for fast multiplication of polynomials over a finite field, and the connection to polynomial evaluation

Trying to code NTT and INTT in order to have faster polynomial multiplication. That has been extremely mind boggling for me. The polynomials are over a finite field $GF(q)$. I've already coded some ...
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 ...
573 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) ...
90 views

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 = ... 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}. ... 1answer 120 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 ... 1answer 95 views ### Why do we need real numbers for fast convolution on rational numbers? The superficial answer is "because of the convolution theorem, and converting phasors to cartesian form, and the FFT and O(n \log n)," but I want a deeper answer. Is there proof that this is the ... 0answers 74 views ### Analysis of a linear increase in standard divination. What might cause a linear increase in floating point error? Background: We are doing mathematical transformations on large matrices of inline fraunhofer holography data (the nature of this isn't really important, but if you are curious, essentially it is a ... 1answer 550 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 ... 0answers 167 views ### Chossing a prime for fft of size 2^n I have a p degree polynomial where p is prime, I want to find the value of this polynomial at all points from 1 to p-1,to make the fft on this polynomial easier I padded it with zeroes up to ... 0answers 124 views ### FFT butterfly diagram I got confused in the FFT butterfly diagram. Can someone please help me understand it? If I have the vector x = (-3, -2, -1, 0, 1, 2, 3, 4), and I want to apply FFT to it using the Butterfly ... 0answers 31 views ### How to evaluate chirp transform in O(nlgn) time? [duplicate] The question says to evaluate chirp transform in O(nlgn) time using the equation in the hint. But I'm unable to get any idea on how to prove the chirp transform from it. Any help is appreciated. 2answers 460 views ### Fourier series Coefficients and wolframalpha 1) Please can my answers be checked, including my final Fourier series. 2) Is it possible to use Wolframalpha to check my answers? If so, how will I go about doing this? Deduce the Fourier series ... 0answers 199 views ### How to evaluate an integral using FFT when the integrand is sensitive to discretization points? I am looking to find the following function using a FFT method: $$g(x)=\frac{1}{2\pi} \int_{-m\pi}^{m\pi} \psi(u) \mathrm{e}^{iux}du$$ I start by discretizing  x \in [... 0answers 45 views ### How to calculate the integral of a fourier trasfom I have to calculate this integral : \int_{-\infty}^{+\infty} \hat G(\omega)e^{i\frac{\pi}{2}\omega}d\omega (\hat G(\omega) is the Fourier trasform) with: G:x\in \Bbb{R}\to \begin{cases} g(x), ... 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 ... 1answer 54 views ### Calculating integral value of Fourier series Given fourier series:$$\mathrm{S}\left(x\right) = {3 \over \pi}\sum_{n = 0}^{\infty} {\sin\left(\left[2n + 1\right]x\right) \over 2n + 1}\,,\qquad \left\langle -\pi,\pi\right\rangle $$Evaluate: ... 0answers 55 views ### Is my formula for DFT correct? I'm doing "Digital Image" online course. I tried to solve the following question x(n_1,n_2) is defined as x(n_1,n_2)=(−1)^{(n_1+n_2)} when 0≤n_1, n_2≤2 and zero elsewhere. Denote by X(k_1,k_2)... 1answer 1k views ### Multiplication of polynomials in their point value form I've never really understood how point-value multiplication of polynomials work, so I was wondering if somebody could talk me through it with an example. Say if I was given the following two ... 0answers 99 views ### Doesn't the recursive Fast Fourier Transform violate f(-x) =/= f(x) for odd functions? When you recursively split into Y_{even} and Y_{odd}, from the second recursion onwards don't these sets have their even-ness and odd-ness violated? I.e., assume you are running the FFT algorithm ... 0answers 111 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 ... 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 ... 0answers 745 views ### Fast fourier transform in sliding window of a signal I would like to detect the change of the frequency content through a real signal using sliding window as shown in following figure. Fixed size sliding window on a signal However, applying fourier ... 0answers 61 views ### How to compute the ifft of a vector? In the following post Concrete polynomial implementation it is said that the final step before obtaining the product of two polynomials is to compute the ifft of a vector. How to compute the ifft of ... 1answer 109 views ### Discrepancy in Discrete Fourier Transform Algorithm Formula? I'm having a bit of trouble with a small part of the following formula (taken from this page):$$F_k=\sum_{n=0}^{N-1}f(x_n)e^{-(2\pi i)k\frac{n}{N}}\tag{1}$$This formula is supposed to represent ... 0answers 227 views ### 2D Fourier Differentiation in Matlab I am working in Matlab to compute partial derivatives and a Laplacian using Fourier Transforms. I prefer to take spectral derivatives, since it corresponds to multiplication by a wave number, however, ... 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>0u(x,0)=f(x),-\infty<x<\infty$$u and u_x vanish as$$ \lvert ...
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 ...