Questions on the computational aspects of Fourier analysis, including the various applications of the fast Fourier transform (FFT).

learn more… | top users | synonyms

0
votes
1answer
65 views

How do I solve Laplace's equation in 2D using spectral methods?

I want to solve the 2D Laplace's equation: $$ \frac{\partial^2 T}{\partial x^2 } + \frac{\partial^2 T}{\partial y^2 } = 0 $$ with boundary conditions: T(x=0)=T(x=1)=T(y=1)=0 and T(y=0)=1 on a ...
3
votes
0answers
20 views

Finding errors in frequency from a Fast Fourier Transform from Gaussian fitting

I took a FFT of sound in a box generated by a frequency sweep over a range of frequencies, and have an array of frequencies and their corresponding FFT amplitudes. According to models for the ...
3
votes
1answer
57 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 ...
1
vote
0answers
57 views

Numerically computing Viscous Burger

I am trying to solve the Viscous Burgers equation using the spectral method. $$u_t+uu_x = Du_{xx}$$ where $D$ is a constant (chosen to be zero) and with the initial condition $$u(x,0) = ...
3
votes
1answer
83 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$. ...
0
votes
0answers
15 views

Computing modes with fourier beam propagation

For my final optics projects I have spent the last few weeks implementing the beam proportionate method with Fourier split steps. This now works really well. Now I am trying to compute the modes of ...
3
votes
0answers
56 views

Does there exist a Fourier transform algorithm for perturbed data?

Assuming I have a length-$n$ real vector $x$ and have already computed its Fourier transform $\hat x$ (in time $O(n\log n)$), I would like to compute the Fourier transform of $y = x + \delta x$, where ...
5
votes
1answer
215 views

Does this Algorithm (probably Fourier like) Exist for 2D Shapes? [closed]

Update: Someone changed the title to this post to a possible answer ("Fourier decomposition of parametric shapes") but I changed it to a different title as that makes it clear what I was asking. As I ...
1
vote
2answers
70 views

Fourier techniques and periodic boundary conditions

Could somebody explain to me why periodic boundary conditions are automatically satisfied if you solve your problem assuming a Fourier series? So, if we assume a Fourier series for our solution, we ...
7
votes
1answer
128 views

Solving a simple Schroedinger 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 ...
0
votes
0answers
38 views

Approximation by sin waves using Fast Fourier Transform

I'm trying to approximate a timeseries by sin waves.I've written a program on python with scipy. But the program yields the wrong result. Please tell me what may be wrong in the code or in my math ...
4
votes
1answer
84 views

Computing Fourier representation of space dependent advection operator via FFT

Consider the following equation on the circle: $$\dfrac{\partial p(x,t)}{\partial t} = a(x)\dfrac{\partial p(x,t)}{\partial x} \equiv L(p) \enspace ,$$ where $L$ is the operator acting on $p(x,t)$. ...
3
votes
0answers
42 views

Broadening spectral data by using FFT's

I obtain numerical discrete data of the form $$ S_{raw}(\omega) = \sum_{j}w_{j} \delta(\omega-\omega_{j}) $$ to compare the result with experimental data the delta peaks need to be broadened ...
2
votes
1answer
108 views

Bounded Input Boundaed Output stability for heat equation. Proof or Counter example?

I am interested in proving or obtaining a counterexample to the following conjecture. Let $\Omega\in \mathbb{R}^d$ be a bounded open domain. Let $u_d\in H^{1/2}(\partial\Omega) \times \mathbb{R}^+$. ...
7
votes
2answers
165 views

Enforcing non-negative constraint in fourier-spectral method

I have a PDE optimization problem, and a scalar field (which I am optimizing over) is supposed to be nonnegative everywhere in the domain. Since I am working in Fourier space for solving this problem ...
0
votes
0answers
45 views

using chebyshev spectral differentiation via FFT

does anyone have any experience of using chebyshev spectral differentiation via FFT to solve an equation of the form u_xx=f where f is a known function and x is a grid between -1 and 1. I know how to ...
4
votes
1answer
121 views

Complete (an incomplete) explanation of the phenomenon of “aliasing”, when using Fourier series to approximate functions?

Consider the approximation of a function by a truncated (finite) Fourier series, using complex notation: \begin{equation} f(x) \approx F_M(x) = \sum_{\alpha = -M}^{M} \hat{f}_{\alpha}e^{-i\alpha x} ...
5
votes
3answers
184 views

Variable viscosity Stokes equation

One very efficient way to solve Stokes equation with periodic boundary conditions \begin{equation} -\eta \nabla^{2} \bf{v} + \nabla p = f \\ \nabla \cdot \bf{v} = 0 \end{equation} is using the ...
3
votes
1answer
137 views

Approximate $h$ in $F(\theta)=\sin \theta \int_{-L}^{+L}h(z)e^{-ikz\cos \theta} \,dz$

Consider $$F(\theta)=\sin \theta \int_{-L}^{+L}h(z)e^{-ikz\cos \theta} \,dz$$ $$|z|\le L$$ $$0 \le \theta \le \pi$$ By having knowledge of $F(\theta)$, how can one approximate $h(z)$? In addition, I ...
4
votes
1answer
69 views

Zero-k mode in Pseudo-spectral solution of Stokes Flow

I'm trying to solve a Stokes flow problem with a pseudo-spectral method in periodic boundary conditions. The equations of interest are $-\nabla^2 \bf{v} + \nabla p = \bf{f} \\ \nabla \cdot \bf{v} = ...
8
votes
2answers
562 views

Quick and simple discrete 2D Helmholtz-Hodge Decomposition using FFTs?

For a silly screen saver I'm trying to develop, I'd like to randomly generate a divergence-free 2D array of 2D vectors, and then use it to generate a line integral convolution plot. I've heard$^1$ ...
0
votes
1answer
190 views

Scaling factor of the inverse Fourier Transform (for convolution purposes)

I have a certain 2-D function. More properly, I have not the function itself, but the matrices $[X,Y,Z]$, where $X,Y$ are $1\times n$, and $Z$ is $n \times n$. Now, I want to calculate a a new ...
1
vote
1answer
179 views

3D Poisson equation, Fourier and Chebyshev

I am currently trying to solve the 3D Poisson equation with a Chebyshev discretisation in the $z$ direction (from -1 to 1) and Fourier in the $x$ and $y$ (from $-\pi$ to $\pi$) I have taken the code ...
1
vote
1answer
61 views

How can DFT of a two dimensional array be found using program for one dimensional DFT in C?

I have the program four1.c from Numerical Recipes in C to calculate the Discrete Fourier Transform (DFT) of a one dimensional array. I want to calculate the DFT of ...
5
votes
1answer
115 views

What spline functions are used in Section 13.9 of “Numerical Recipes in C”?

I asked a similar question on MathSE but with more added fluff, but didn't really get any straight answers, so I figured I'd ask here. Computing Fourier coefficients of a function using the FFT is ...
1
vote
1answer
96 views

How to do Fast Fourier transform (FFT) for singular functions?

I want to do a 3-dimensional FFT on this function $\frac{\cos (x) \cos (y) \cos (z)-\sin (x) \sin (y) \sin (z)}{\left((1.0001+\sin (y)+\cos (z))^2+(0.0001+\cos (x)+\sin (z))^2+(0.0001+\sin (x)+\cos ...
2
votes
3answers
371 views

Solving Stokes flow with walls using Oseen tensor

Introduction I've developed a code to solve for generalised, incompressible 2D Stokes flow $\eta \nabla^2 \mathbf{v} - \nabla p + \mathbf{S} = 0$ $\nabla . \mathbf{v} = 0$ where $\mathbf{S}$ can ...
2
votes
2answers
81 views

Projection of vector field on to a gradient field

Say I have a vector field with non-zero curl, therefore the potential function depends on the path I choose to integrate. In this paper the authors proposed to project the vector field into a gradient ...
3
votes
2answers
1k 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
vote
2answers
600 views

Computing Kolmogorov/Energy spectrum for turbulent boundary layer

Previously, I have calculated energy spectrum for 3D DNS data obtained for isotropic turbulence which is equally spaced in all three directions and then to compute the energy spectrum, one performs ...
1
vote
0answers
222 views

Convolution of two radially symmetric functions for double logarithmic plot

Question: I have problems with sidelobes when computing the convolution of two radially symmetric functions. I wonder whether I should just switch from second order to fourth order and refine the ...
0
votes
2answers
208 views

Amplitude of discrete Fourier transform of Gaussian is incorrect

I am trying to understand why the amplitude of the FFT (computed with numpy) of a Gaussian differs from its analytic solution. The $\mathcal{F}\{e^{-\pi t^2}\} = e^{-\pi f^2}$. However if I calculate ...
11
votes
2answers
185 views

numerical integration in many variables

Let $\vec{x} = (x_1, x_2, \dots, x_n) \in [0,1]^n$ and $f(\vec{x}): [0,1]^n \to \mathbb{C}$ be a function in these variables. Is there a recursive scheme for this iterated integral? ...
3
votes
1answer
91 views

How can we compute statistics of the DFT of a random signal?

I would like to know how to compute the statistics of the discrete Fourier transform of a noise signal. To illustrate what I mean, I will first explain in detail a computation I have managed to do ...
2
votes
1answer
53 views

Algorithm to extract the decaying parts of complex exponentials

I have an oscillatory, decaying function that can be decomposed as $$\sum_k e^{iz_kt} $$where $z_k$ are complex. What I want is the imaginary parts of all of the $z_k$'s with some range of real ...
6
votes
2answers
714 views

How to compute the wavelet approximation of a function?

For the function $f(x)=x$, how to compute the wavelet approximation using Haar basis? I'm new to wavelet, I'm looking for a package which will do something like this ...
3
votes
0answers
131 views

Choosing good basis functions to approximate a Lipschitz function

Let $D = \left\{0, t_1, t_2, \ldots, t_n\right\} \times [0,1]$ and $$ f: D\to [0,1], $$ be a function of time and a one-dimensional space. There is no analytical formula for $f$, but $f(t_i, \cdot)$ ...
6
votes
1answer
296 views

When is discrete Fourier transform a good approximation to the continuous one?

I am looking for help in understanding the use of discrete Fourier transform as an approximation to continuous Fourier transforms. As an exercise, I considered a Gaussian $$f(x) = ...
1
vote
1answer
84 views

What to look for in a discrete fourier transform

I was attempting to do a discrete Fourier transform through a computer program on a list of numbers. Before doing that I decided to test it by running through a list of 1000 numbers which I created by ...
0
votes
0answers
45 views

Sine series using exponential based FFT

I have such a problem - I would need to expand a discrete function in a sine fourier series but I would like to use exponential based library for FFT (I will use CUDA to compute it). What have I to do ...
4
votes
1answer
169 views

Error bars for pair-correlation function

I have obtained some data from neutron diffraction for some material samples. The "rawest" form of the data is the structure function $S(Q)$. We can choose a variety of different Q-maxes when ...
5
votes
1answer
1k views

Solving linear systems by fft

I read in a paper and also at wiki that we can solve the system $$Ax=B$$ by Fast Fourier Transform, where $A$ is a circulant matrix. The solution is ...
4
votes
1answer
791 views

Von Newman stability analysis for 2D acoustic wave equation explicit

Von Newman stability analysis for acoustic wave equation explicit centered differences: 2nd order time and space (N 2)'th order: \begin{eqnarray} U_{jk}^{n+1} = \left( \frac{\Delta t V_{jk} ...
4
votes
1answer
485 views

Chebyshev spectral differentiation via FFT

I am using the Chebyshev spectral differentiation technique that is described concisely under "details" here. The idea is to take the initial data $v_0,v_1\,...,v_N$ and store it in union with itself ...
14
votes
1answer
948 views

Convergence rate of FFT Poisson solver

What is the theoretical convergence rate for an FFT Poison solver? I am solving a Poisson equation: $$\nabla^2 V_H(x, y, z) = -4\pi n(x, y, z)$$ with $$n(x, y, z) = {3\over\pi} ((x-1)^2 + (y-1)^2 + ...
2
votes
0answers
124 views

differences between all the FFTs? [closed]

Wikipedia lists a lot of FFT algorithms: Cooley–Tukey FFT algorithm, Prime-factor FFT algorithm, Bruun's FFT algorithm, Rader's FFT algorithm, and Bluestein's FFT algorithm What are the pros and ...
2
votes
1answer
1k views

Discrete 3D convolution of matrix valued functions

As stated in the title, I need to make a discrete 3D convolution of two matrix-valued functions. Or, actually, I need to convolve a matrix-valued function with a vector-valued function. That is, I ...
2
votes
0answers
85 views

Eigenmode constraints on a complex wave field

I'm studying the usual wave equation: $$ \frac{\partial^2 \psi}{\partial x^2} - \frac{1}{c^2} \frac{\partial^2 \psi}{\partial t^2} = 0$$ with complex field $\psi$, on a n-dimensional cube region of ...
3
votes
2answers
3k views

how can a 2-d fft be constructed to an equivalent matrix?

When I use the cvx matlab toolbox, I met a puzzled problem. The function of fft (or dct, wavelet, etc.) cannot be recognized by the type of 'cvx'. For the 1-d fft, it can be constructed to an ...
1
vote
1answer
141 views

How can I quantify the error of FFT-based poisson solvers?

I have an FFT code that solves a particular case of the steady Euler equations where a Poisson equation is solved, what is a good way to quantify the error? Is what I am doing ok? Since I do not have ...