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.

3
votes
1answer
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,...
0
votes
1answer
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 ...
1
vote
0answers
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 ...
2
votes
1answer
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 ...
4
votes
2answers
171 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 ...
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 ...
0
votes
1answer
97 views

Fourier transform of area between four circles

Four similar circles (radius-$R$) are packed in a simple square structure. Let's denote the area between these circles as $S$ - red area in attached image.. Now, let's think about a function $f$ ...
0
votes
0answers
92 views

How to express mathematically the frequency image?

I have the following frequency square image N x N How to express this frequency image in mathematical formulation? Thanks
0
votes
0answers
486 views

Plotting Fourier transform of integral function on Matlab

I want to plot the Fourier transform of $$f(t)=\int_{0}^{t}\exp\left(-\frac{1}{1-s^{2}}\right)\,ds,\qquad\text{if }|s|<1,\text{ otherwise }0$$ ...
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}+\...
0
votes
0answers
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 ...
0
votes
0answers
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 ...
-1
votes
1answer
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}$) ...
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 ...
1
vote
1answer
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$: ...
0
votes
0answers
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 ...
0
votes
0answers
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 ...
1
vote
0answers
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 ...
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 ...
2
votes
0answers
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 ...
0
votes
0answers
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 ...
0
votes
1answer
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 ...
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 ...
2
votes
0answers
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) ...
3
votes
1answer
90 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 = ...
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}$. ...
3
votes
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 ...
0
votes
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 ...
0
votes
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 ...
2
votes
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 ...
0
votes
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 ...
0
votes
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 ...
0
votes
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.
0
votes
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 ...
0
votes
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: \begin{equation} g(x)=\frac{1}{2\pi} \int_{-m\pi}^{m\pi} \psi(u) \mathrm{e}^{iux}du \end{equation} I start by discretizing $ x \in [...
0
votes
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), ...
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 ...
0
votes
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: ...
0
votes
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)...
1
vote
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 ...
0
votes
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 ...
3
votes
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 ...
5
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 ...
0
votes
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 ...
1
vote
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 ...
1
vote
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 ...
1
vote
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, ...
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 ...
2
votes
0answers
94 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 ...
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 ...