Questions tagged [fourier-transform]

For questions about Fourier transforms, how they are used, and implementation details.

Filter by
Sorted by
Tagged with
10 votes
5 answers
3k views

Fourier pseudo-spectral method and numerical dissipation

Performing a direct numerical simulation of isotropic turbulence with Fourier pseudo-spectral method (Orzag & Patterson, PRL, 1972) using FFT. For a background of the method, which is widely used ...
  • 419
7 votes
2 answers
10k views

Least Squares and Fourier Series

I have a little bit of problem figuring out the relation between Fourier series and Least Squares. As far as I understand, LS is a way of minimizing the quadratic error between a measured value $y_i$ ...
  • 1,019
6 votes
3 answers
2k views

Computing numeric derivative via FFT - SciPy

I wrote the following code to compute the approximate derivative of a function using FFT: ...
6 votes
2 answers
3k views

Fourier Transform of function in Spherical Harmonics

I have a function $f(r,\theta,\phi)$ which I am expressing in terms of spherical harmonics $$ f(r,\theta,\phi) = \sum_{l=0}^{\infty} \sum_{m=-l}^{l} g_{l,m}(r) d_{l,m}(\theta,\phi) $$ where $d_{l,m}$...
  • 2,109
6 votes
2 answers
16k views

C++ libraries for Fast Fourier Transform in high precision

I am looking for a C++ library for Fast Fourier Transform (FFT) in high precision (e.g., using high precision real data types similar to mpfr_t in MPFR or ...
5 votes
0 answers
124 views

Discrete sine and cosine transform for mixed derivatives

Using sine and cosine transforms to solve Poisson's equation with Dirichlet boundary conditions seem quite standard nowadays (see, e.g., here or Table 2 in this paper). In the case of Poisson's ...
  • 71
5 votes
1 answer
851 views

Help with Fourier beam propagation method

I am working on implementing the Fourier beam propagation method in C++. I am really more of a programmer than a physicist but I think I have a good understanding of what I am trying to do. Here is ...
  • 173
4 votes
3 answers
487 views

Why not use the convolution theorem for explicit timestepping?

Consider the advection equation \begin{equation} \frac{\partial C}{\partial t} + u\frac{\partial C}{\partial x} + v\frac{\partial C}{\partial y} = 0 \end{equation} I want to do a forward time, center ...
  • 141
4 votes
1 answer
751 views

How to use matlab command 'fft' to solve Ax=b arising from Poisson equation?

I want to ask a question about fast solver to the Poisson equation with Homogenous boundary conditions as follows: $$-\Delta u = f.$$ After centered difference using $n+2$ equidistance points in all ...
  • 971
4 votes
1 answer
177 views

How to define a dimensionless Objective function for determining how peaked a curve is?

I have attached 2 plots for FFT spectra. One is considered good and one is bad. The good one is classified on the basis of how closely spaced the frequencies and the bad is based on how multiple ...
4 votes
2 answers
406 views

How to calculate efficiently and accurately the Fourier transform of a radial function in Fortran

As my question states, I want to calculate the Fourier transform $F(q)$ of a radial function $f(r)$ (defined on $[0,\infty)$ and which decays like an exponential $\exp(-Ar+b)$ at large $r$) as ...
  • 175
4 votes
1 answer
179 views

Computation of triple nested loops as a convolution product?

I'm trying to compute efficiently the following \begin{equation} A_j = \sum_{l'=1}^{\infty}\sum_{k= 0}^{K-1} L_{l'}T_ke^{2\pi i \frac{k}{K}j}\epsilon_{l',k} \end{equation} for $j = 0,1, \ldots, K-2,K-...
4 votes
1 answer
183 views

Differences between Discrete Fourier Transform and Continuous Fourier Transform?

I am trying to visualize the time dependence of a free particle given an initial wave-function using Python and I just wanted to know if I could use the in built FFT implementation from NumPy to find ...
4 votes
1 answer
688 views

Two approaches to solving diffusion equation in Fourier space

I want to numerically solve the diffusion equation $\partial_t u = D \partial_x^2 u$ in Fourier space, and can think of multiple ways to do it. Setup Option 1 Differentiating $u$ twice in Fourier ...
  • 265
3 votes
2 answers
2k views

Fourier transform by FFT : by using cubic splines to interpolate between data points, do we change the frequency content of the Fourier transform?

I have a data file with some points equally spaced. These represent some function. I have to calculate the Fourier transform of this set of points. The thing is, I'm tempted to take a cubic spline of ...
  • 175
3 votes
2 answers
136 views

DFT of $g(\omega) \exp(i C \omega^2)$. How to do it ,if uniform sampling requires too much memory?

I have a following problem : I want to transform a function $g(\omega) \exp(i C \omega^2)$. $g(\omega)$ is real and limited. It changes slowly compered to $\exp(i C \omega^2)$. I have a black box that ...
  • 31
3 votes
1 answer
280 views

precision loss in non-trigonometric, periodic functions using FFTW and NaNs after marching forward in time (Fortran)

I have developed a pseudospectral solver of the Navier-Stokes equations using FFTW. I tested my formulation of right hand sides (RHS) of the NS equations against standard trigonometric functions (...
3 votes
2 answers
509 views

Chebyshev differentiation via FFT with a domain [a,b]

I want to ask something about Chebyshev differentiation via FFT, which can be used to obtain with spectral accuracy the derivative of a smooth function. See for instance this code in python, which ...
  • 33
3 votes
1 answer
800 views

FFT on non-orthogonal lattice ( for computing convolutions and solving PDEs )

I saw many examples of application of FFT for computation of convolutions and solving PDEs ( like Poisson equation ). It is very strightforward and efficient if I work with rectangular (orthogonal) ...
3 votes
1 answer
220 views

Problem implementing convolutions exactly with the FFT

I'm trying to perform convolutions as defined mathematically $f \star g (\tau)= \int_{\mathcal{R}}f(t-\tau)g(t) dt$ in a numerical simulation. Hence, my signal is a sampling of points $f(x_i)$. I ...
3 votes
1 answer
67 views

Hankel transform with high accuracy

Short version I'm computing the zero-order Hankel transform of a function $f(r)$, $$F(k) = \int_0^\infty f(r)J_0(kr)r\,\mathrm{d}r$$ I know $f(r_n)$ at selected $r_n$ but it is impractical to compute ...
  • 3,323
3 votes
1 answer
837 views

FFT convolution vs direct convolution

Recently I tried to compare results for 1D direct convolution and convolution via FFT. I expected to get absolutely the same result, however I faced with a problem that results are different, ...
3 votes
1 answer
125 views

Does DCT diagonalize the FD discretisation of the Laplacian with Neumann boundary conditions?

If one has the Poisson problem (assume $\int_{\Omega} f = 0$ and $\int_{\Omega} u = 0$): \begin{alignat}{3} \Delta u(x) &= f(x), &\quad&x\in\Omega \\ \partial_nu(x) &= 0, &\quad&...
3 votes
1 answer
959 views

My calculated laser pulse duration is too large. Where am I wrong?

I am currently writing a small Python script to estimate the pulse duration from the optical spectrum. At the end, the idea is to observe the effects of the spectral phase on the pulse duration and ...
  • 31
3 votes
1 answer
42 views

Bounds condition for IFT to obtain a $1/f$ time-series

I am coding a function to obtain a randomized time-series from a given $\frac{1}{f}$ law. The randomization is obtained by introducing a random phase in the function. I experience a problem in the ...
  • 61
3 votes
1 answer
184 views

Calculating the Convolution Using DFT (FFT)

I have the following convolution as part of a numerical simulation. $$T(r)=\int \mathrm{d}^3r_2\, p(r_2)f(r_2)\alpha(r-r_2)\, .$$ My problem is that the analytical expressions for $f$ and $p$ do ...
  • 131
3 votes
1 answer
2k views

Fast(er) computation of dot product of two convolutions?

Let $a,b,c,d\in\mathbb{R}^n$. Is it possible to compute $$\langle a*b,c*d\rangle$$ faster than 6 FFTs? I can do it with 6 FFTs by doing normal convolutions, 3 FFTs each. In my application I know $b, ...
3 votes
1 answer
346 views

MPI support for discrete Fourier transform (DFT) in Python

I am looking for a discrete Fourier transform (DFT) library that can be run with MPI on Python. Usually, in other languages (C, Fortran) FFTW is used. There's a Python wrapper for FFTW called pyFFTW, ...
  • 215
3 votes
1 answer
194 views

How to get Fourier transform of Fisher-Kolmogorov?

How can I use Fourier Transform to solve Fisher-Kolmogorov Equation in 1D? \begin{equation} u_t(x,t) = u_{xx}(t) + u(1-u) \end{equation} \begin{equation} u(0,x) = \phi(x) \end{equation} with ...
  • 289
3 votes
0 answers
41 views

3D Cooley-Tukey FFT

To compute the $N$-point DFT $$ X[k] = \sum_{n=0}^{N-1} x[n] W_N^{kn} $$ where $N = N_1 N_2$, we can write the indices as $n = N_2 n_1 + n_2$ and $k = k_1 + N_1 k_2$, (effectively packing the data ...
  • 31
3 votes
0 answers
363 views

How to obtain values in physical space for a given spectrum?

My question falls under purview of turbulent flows. I want to add an initial perturbation, for which I have a given energy spectrum (say$ E(k)=ak^4e^{-bk^2} $). The steps involved in getting these ...
  • 83
2 votes
1 answer
942 views

Numerically computing the advection equation

I am trying to write a program to compute the advection equation. $$u_t +u_x = 0$$ I use the spectral method for the spatial derivative $u_x$ and the leapfrog method for the time derivative $u_t$. ...
2 votes
1 answer
545 views

How do I avoid divide-by-zero when solving the Poisson equation with Fourier transforms?

I wanted to try to implement part of the method in the following article using Fourier transforms. http://www.shodor.org/media/content/jocse/student_submissions/nocito2010/nocito2010_pdf Right now I ...
  • 173
2 votes
1 answer
165 views

Why do problems arise in FFT for smaller value of df in Python?

...
2 votes
1 answer
725 views

Calculating high-order derivatives using FFT in Matlab

I'm trying to calculate the derivative of a function using FFT in Matlab. I've coded the following function to calculate it: ...
2 votes
1 answer
122 views

Fourier spectral method for coordinate transformed heat equation

As the title said, I want to solve a coordinate transformed heat equation using fourier spectral method. In particular, I am interested in transforming an uniform grid into an adaptive non-uniform ...
  • 109
2 votes
1 answer
516 views

Incorporating a potential barrier in a wave-packet simulation (Fourier Transform method)

I'm trying to simulate the scattering of a wave-packet at a potential barrier in Python. I'm using a Fourier Transform method (not sure if its the same as the Split-Step method), where I apply Fourier ...
2 votes
1 answer
72 views

FFT of "implicitly" uniform data

I am trying to take a Fourier transform of a density field estimated from mock galaxy survey catalogs. Basically, you start with a list of galaxy positions, then you bin these positions over some ...
  • 133
2 votes
1 answer
43 views

Padding length and error analysis of discrete convolution by FFT

The standard algorithm for discrete convolution of two vectors $x\in \mathbb{R}^{n}$ and $y \in \mathbb{R}^{m}$ is (in essence) a FFT of the two input vectors, multiplication of the two elementwise, ...
  • 2,031
2 votes
1 answer
165 views

Approximating improper integral with FFT

In d'Halluin et al. (2005) (http://imajna.oxfordjournals.org/content/25/1/87.short) the authors claim that the correlation integral $$ I(x) = \int_{-\infty}^{\infty} V(x+y) f(y) dy $$ can be ...
  • 21
2 votes
0 answers
18 views

Normalising DFTs Correctly

I have been playing around with convolutions in scipy's signal package: ...
2 votes
0 answers
30 views

Palmprint Identification - Why do we align the images before we use the Fourier Transform?

I am currently reading the paper PALMPRINT IDENTIFICATION BY FOURIER TRANSFORM by WENXIN LI, DAVID ZHANG and ZHUOQUN XU about identifying persons based on an image of their palm, one version of the ...
  • 121
2 votes
0 answers
99 views

Fusing callbacks with FFTs: an open-source GPU FFT implementation?

I'm using cuFFT to do some 2D FFTs on matrices of size 2048x2048 or larger. The FFTs are preceded and followed by various scaling operations. These scaling operations are memory-bound, so they take ...
  • 3,131
2 votes
0 answers
236 views

Solving a 3D (almost radial) convolution with FFT

I have a 3D integral that is almost a radial convolution of the form $$ \int d^{3}k'h(\mathbf{k'})g(|\mathbf{k-k'}|) $$ and I am looking for a fast and efficient algorithm (e.g. FFT) to solve it ...
  • 21
2 votes
3 answers
223 views

Amplitude at a given frequency in a wide band signal

Could anyone suggest the most computationally efficient method for finding amplitude at a given frequency having a noisy wide band signal. To be more specific about a task. I have some physical ...
  • 121
2 votes
0 answers
45 views

Constructing 2 fold oversampled cosine basis in MATLAB

So I'm trying to construct a 2 fold oversampled cosine basis in MATLAB. I know how to construct the basis as a square matrix using the following command: ...
  • 21
2 votes
0 answers
827 views

Fast Forward Laplace transform

There are examples for fast numerical inversion of the Laplace transforms. For example here: http://www.mathworks.com/matlabcentral/fileexchange/32824-numerical-inversion-of-laplace-transforms-in-...
  • 121
1 vote
3 answers
310 views

Fast way to compute integral of type $\int dx f(x) \cos(n \pi x)$ in SciPy

I have an integral of the form $$ I(n) = \int_0^1 dx f(x) \cos(n \pi x) , $$ where $n$ is an integer. In other words, I calculate the cosine Fourier coefficients of function $f$, which is real and ...
  • 207