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

learn more… | top users | synonyms

1
vote
1answer
44 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
83 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
63 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
2answers
102 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
1answer
49 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
142 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
116 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 ...
0
votes
0answers
79 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
45 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 ...
10
votes
2answers
164 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
80 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
51 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 ...
0
votes
0answers
70 views

Fourier differentiation matrix using global periodic function (fourdif.m) from Reddy's Matlab Suite

I use the fourier differentiation matrix in my stability problem in fluid mechanics in 2D. i.e. X and Y. Z is infinite. I use Chebyshev in Y. My fourier differentiation matrix is a circulant matrix. ...
6
votes
2answers
292 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 ...
2
votes
0answers
97 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
200 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
80 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
42 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
114 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 ...
4
votes
1answer
441 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
308 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} ...
3
votes
1answer
235 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
524 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
111 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 ...
1
vote
1answer
582 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
65 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
1k 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
109 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 ...
1
vote
1answer
209 views

Von Neumann Stability Analysis

I came across the following task recently: Use the von-Neumann stability analysis to investigate the stability of the discrete form of $\frac{\partial c}{\partial x} = \frac{\partial^2 c}{\partial ...
3
votes
1answer
274 views

How to do local FFT on huge 3D vector data cell mesh and visualize it spatially?

Simulation type: I'm running a simulation with the OOMMF micromagnetics package http://math.nist.gov/oommf/ where are magnet is represented by a mesh of 3 million cells, it gets excited by a ...
1
vote
1answer
100 views

Error analysis of WENO scheme

I have three questions regarding WENO schemes 1) How to actually compute the smoothness indicators $\beta_j$ for required order of polynomial? Any reference which explains the algorithm will be ...
3
votes
1answer
890 views

Order of MATLAB FFT frequencies

This wikibook states that the output of MATLAB's FFT corresponds with the wavenumbers ordered as: ...
1
vote
2answers
66 views

A function as a sum of serie of modified FFT coeff. of another function - multiplied by sum number

I solve such a problem. Lets have a function $Y=\sum_{k=-\infty}^\infty i\hat Y e^{ik\pi y}$ and then I have a function which is defined as $X=\sum_{k=-\infty}^\infty ik^2\hat Y e^{ik\pi y}$. I ...
4
votes
1answer
481 views

MPI-based Implementations of FFT

In a numerical computation, I am required to take a multi-dimensional FFT on a distributed-memory cluster. The data is currently distributed using a distributed array in PETSc (DMDA). I initial ...
8
votes
1answer
546 views

Fast (approximate) evaluation of Chebyshev polynomial

Is there a preferred way how to implement a fast (approximate) evaluation of the Chebyshev interpolation polynomial on uniform grid (given the function values at the Chebyshev nodes)? My problem is ...
8
votes
1answer
295 views

Fourier transform for Neumann boundary condition

I need to solve system of two coupled partial differential equations numerically. $\frac{\partial x_1}{\partial t} = c_1\nabla ^2 x_1 + f_1(x_1,x_2) \\$ $\frac{\partial x_2}{\partial t} = ...
2
votes
1answer
120 views

Numerically designing a periodic 1D curve that maximizes an integral area objective and satisfies value, derivative, and frequency constraints

I need to write MATLAB program (or use an existing one) to obtain Fourier series coefficients. Let's say the series is going to approximate a 1D curve. The boundary conditions are: value of the ...
7
votes
2answers
399 views

How many Fourier magnitudes do I have to calculate before an FFT becomes more efficient than a DFT?

I need to compute only a small number of low frequency Fourier components of a complex 2-dimensional array. I'll be computing the same Fourier components over and over again as the input array ...
8
votes
1answer
352 views

Which fourier series is needed to solve a 2D poisson problem with mixed boundary conditions using Fast Fourier Transform?

I have heard that a fast fourier transform can be used to solve the poisson problem when the boundary conditions are all one type... Sine series for dirichlet, cosine for neumann, and both for ...
10
votes
1answer
320 views

Library for Fourier transform on triangle lattice

I am looking for reasonably fast implementations of the discrete Fourier transform (DFT) on a 2D triangular or hexagonal lattice. I would appreciate pointers to such implementations (especially ones ...
11
votes
4answers
479 views

Scalability of Fast Fourier Transform (FFT)

To use the Fast Fourier Transform (FFT) on uniformly sampled data, e.g. in connection with PDE solvers, it is well known that the FFT is an $\mathcal{O}(n\log(n)$) algorithm. How well do the FFT scale ...
32
votes
4answers
5k views

How do I take the FFT of unevenly spaced data?

The Fast Fourier Transform algorithm computes a Fourier decomposition under the assumption that its input points are equally spaced in the time domain, $t_k = kT$. What if they're not? Is there ...