Flow Lab

Syllabus / Module 10: Numerical Methods for PDEs

Lesson 10.12

Spectral Methods & the FFT

Representing solutions in Fourier modes; spectral differentiation; pseudo-spectral methods; aliasing and dealiasing.

Written byClaude Sonnet

🌊
Why this matters for simulation: Stam's 'FFT fluids' and turbulence research codes are spectral.

By the end of this lesson you can…

  • Differentiate periodic data by FFT (multiply by $ik$) and read finite differences as multipliers $i\sin(kh)/h$ and $i(8\sin kh - \sin 2kh)/6h$.
  • Explain spectral accuracy from the decay of Fourier coefficients and predict the rate $e^{-\sigma N/2}$ from the nearest complex singularity.
  • Evaluate a nonlinear term pseudo-spectrally, find where a product aliases, and derive the $2/3$ rule.
  • Solve $-\nabla^2 u = f$ on a periodic box with two FFTs and a division, and say what happens to the zero mode.
  • Say which boundary conditions keep the transform trick and which break it, and sketch Chebyshev points (from memory).
  • Name what spectral methods cannot do, and why that motivates finite elements.
On this page
·
  1. Differentiation by multiplication
  2. Spectral accuracy
  3. Pseudo-spectral nonlinear terms
  4. The FFT Poisson solver
  5. Beyond periodic: Chebyshev points (from memory)
  6. The exercise: a periodic Poisson solver
  7. Where spectral methods stop
  8. Concept checks
  9. Problems
  10. Key Takeaways

10.9 Multigrid ended on a loose thread. Its analysis wrote the error as a sum of sampled sine waves, the eigenvectors of the Poisson matrix, but used them only as a diagnostic. If a fast change of basis makes the matrix diagonal, we need no sweeps or grids: transform the right side, divide each coefficient by its eigenvalue, transform back. That is a spectral method, and the FFT (8.5 Convergence & the Gibbs Phenomenon) is why it costs only Nlog⁡NN\log N per direction. This lesson shows what the trick buys (errors that fall exponentially, not like a power of hh), what it costs (aliasing, periodic boundaries), and where it stops. 9.9 Infinite Domains & the Fourier Transform left the 2/32/3 rule “from memory”; here we derive it.

▶ Video Differentiating by multiplying coefficients by ik, a finite-difference stencil as a multiplier, the error against N on a log plot, a product that aliases, and a Poisson solve by two FFTscaptions only
Transcript
  1. Spectral methods differentiate by multiplication. Sample a periodic function, take the FFT, multiply the coefficient of wavenumber k by i k, and transform back. A finite-difference stencil does the same thing to a wave, but with a slightly wrong multiplier. The central difference replaces k by sine of k h over h; the fourth-order formula uses eight sine theta minus sine 2 theta, over 6. Expanding, the relative error is theta squared over 6 for FD2 and theta to the fourth over 30 for FD4. Spectral has no error at all below Nyquist. Turn that into a budget: for a 1 percent derivative error, FD2 needs 25.6 points per wavelength, FD4 needs 8.35, and a spectral method needs 2.
  2. Where does the spectral error come from? From the Fourier coefficients near Nyquist, so smoothness is the whole story. Take one over 2 plus cosine x. Its coefficients decay like a geometric series, set by the nearest complex singularity at pi plus or minus i sigma, where sigma is the natural log of 2 plus root 3, 1.317. Here is the maximum derivative error against N. FD2 and FD4 are straight lines on this log plot: the slopes are 1.99 and 3.97, a fixed factor of 4 or 16 for every doubling. The spectral error is different. Between N equal to 16 and 32 it falls from 1.40 times 10 to the minus 4 to 7.51 times 10 to the minus 9, about 19,000-fold, and then it hits rounding. To reach 10 to the minus 6, FD2 needs 4096 points, FD4 needs 192, and spectral needs 32.
  3. The nonlinear term is the catch. In Fourier space a product is a convolution, which costs N squared. The pseudo-spectral trick multiplies on the grid instead. The price is aliasing: a wavenumber m above Nyquist is indistinguishable from m minus N. If u holds wavenumbers up to K, then u squared holds wavenumbers up to 2K, and the lowest spot they can land on is N minus 2K. The band we keep stays clean exactly when N minus 2K exceeds K, that is, K below N over 3. Check it at N equal to 48, where the threshold is 16. For K up to 15 the error is round-off. At K equal to 16 it jumps to 1.2 times 10 to the minus 3, then 2.2 times 10 to the minus 2 at K equal to 20, and 9.7 times 10 to the minus 2 at K equal to 24. Zero the top third before each product and the aliases land on modes you discard anyway. The cost is 1.5 percent of the field's energy.
  4. Now the thread from multigrid. To solve minus the Laplacian of u equals f on a periodic box, take a 2D FFT of f, divide each coefficient by the symbol, and transform back. There are two honest symbols. The spectral one is k squared plus l squared. The five-point one is 4 minus 2 cosine k h minus 2 cosine l h, over h squared, which solves the five-point system exactly in one shot. At k and l equal to 0 the divisor vanishes: a solution exists only if the mean of f is 0, so drop it and set the mean of u to 0. Test on e to the sine x times cosine y. The spectral error is 1.2 times 10 to the minus 3 at N equal to 8, 8.1 times 10 to the minus 9 at 16, and rounding from 32. The five-point error is 0.213, 0.0496, 0.0122 and 0.00304, with ratios 4.06 and 4.01: second order. The cost is N squared log N for N squared unknowns, with no iteration at all.
  5. Spectral methods have honest limits. First, smoothness: for the absolute value of sine x cubed, whose third derivative jumps, all three methods collapse onto an order two line. The function, not the method, is the limit. Second, boundaries: periodic gives the FFT, zero edges give a sine transform, and mixed conditions destroy the trick. Chebyshev points, equally spaced in angle, bring the FFT back on an interval, though I am giving that from memory. Third, geometry: an airfoil is not a box, and one global basis means one resolution everywhere. Shocks, layers and awkward shapes are where fluids live. The tool that handles them is the weak form, an integral version of the equation tested against basis functions. Next, finite elements.

Differentiation by multiplication

Take a 2π2\pi-periodic function sampled at xj=2πj/Nx_j = 2\pi j/N, so h=2π/Nh = 2\pi/N. The FFT writes the samples as a sum of waves eikxje^{ikx_j} with integer kk from −N/2-N/2 to N/2N/2. A wave differentiates to ikik times itself, so the recipe of 9.9 Infinite Domains & the Fourier Transform follows: FFT, multiply the coefficient of wavenumber kk by ikik (the Nyquist entry k=N/2k = N/2 by 00), inverse FFT. As a matrix this is the dense operator D=F−1diag⁡(ik)FD = F^{-1}\operatorname{diag}(ik)F, never formed: the cost is Nlog⁡NN\log N, not N2N^2.

To compare it with finite differences, ask what each formula does to one wave eikxe^{ikx}. A central difference gives

eik(x+h)−eik(x−h)2h=i sin⁡khh eikx,\frac{e^{ik(x+h)} - e^{ik(x-h)}}{2h} = i\,\frac{\sin kh}{h}\,e^{ikx},

the exact multiplier ikik with kk replaced by keff=sin⁡(kh)/hk_{\rm eff} = \sin(kh)/h. The fourth-order formula (−fj+2+8fj+1−8fj−1+fj−2)/12h(-f_{j+2} + 8f_{j+1} - 8f_{j-1} + f_{j-2})/12h gives keffh=(8sin⁡kh−sin⁡2kh)/6k_{\rm eff}h = (8\sin kh - \sin 2kh)/6. Expanding in θ=kh\theta = kh gives sin⁡θ/θ=1−θ2/6+⋯\sin\theta/\theta = 1 - \theta^2/6 + \cdots and keffh/θ=1−θ4/30+⋯k_{\rm eff}h/\theta = 1 - \theta^4/30 + \cdots, so the relative error of the derivative of a wave is θ2/6\theta^2/6 for FD2 and θ4/30\theta^4/30 for FD4. The spectral formula has keff=kk_{\rm eff} = k for every wave the grid can hold below Nyquist, θ<π\theta \lt \pi. The sim’s second view plots these curves.

Turn the curves into a budget. The number of points per wavelength is 2π/θ2\pi/\theta. Solving 1−keffh/θ=0.011 - k_{\rm eff}h/\theta = 0.01 numerically gives θ=0.245\theta = 0.245 for FD2, so 25.625.6 points per wavelength, and θ=0.753\theta = 0.753 for FD4, so 8.358.35 points. At 0.1%0.1\% the figures are 81.181.1 and 15.015.0. Spectral differentiation needs 22 (the Nyquist limit): a factor of about 1313 fewer points per direction than FD2, and 44 fewer than FD4.

Worked example: a wave the grid cannot hold. On N=8N = 8 points, kk runs 0,1,2,3,4,−3,−2,−10, 1, 2, 3, 4, -3, -2, -1 with k=4k = 4 the Nyquist slot. Sample sin⁡5x\sin 5x. On the grid ei5xj=ei(5−8)xj=e−i3xje^{i5x_j} = e^{i(5-8)x_j} = e^{-i3x_j}, so the samples are exactly those of sin⁡(−3x)=−sin⁡3x\sin(-3x) = -\sin 3x. The FFT sees a wave of wavenumber −3-3, and the spectral derivative returns −3cos⁡3xj-3\cos 3x_j at the nodes: −3, 2.1213, 0, −2.1213, 3, …-3,\ 2.1213,\ 0,\ -2.1213,\ 3,\ \dots The true derivative 5cos⁡5xj5\cos 5x_j is 5, −3.5355, 0, 3.5355, −5, …5,\ -3.5355,\ 0,\ 3.5355,\ -5,\ \dots Nothing in the data distinguishes the two. This is aliasing (8.5 Convergence & the Gibbs Phenomenon), and it returns in products.

Spectral accuracy

Where does the spectral error come from, if not from a Taylor remainder? A smooth periodic function is f=∑ckeikxf = \sum c_k e^{ikx} with coefficients that shrink as kk grows. The grid keeps the modes ∣k∣<N/2\lvert k\rvert \lt N/2 and misreads the rest as slower waves (the aliasing above), so the error of the derivative is controlled by the size of the coefficients near k=N/2k = N/2, multiplied by kk because differentiation multiplies by ikik. Smoothness is the whole story. By the rule of 8.5 Convergence & the Gibbs Phenomenon, when f′′′f''' has a jump the coefficients fall like k−4k^{-4} and the derivative error like N−2N^{-2}. When ff is analytic in a strip around the real axis the coefficients fall geometrically.

Worked example: a function whose rate we can read off. Take f=1/(2+cos⁡x)f = 1/(2 + \cos x). Write r=2−3=0.2679r = 2 - \sqrt3 = 0.2679. The identity

12+cos⁡x=13(1+2∑k≥1(−r)kcos⁡kx)\frac{1}{2 + \cos x} = \frac{1}{\sqrt3}\Bigl(1 + 2\sum_{k\ge1}(-r)^k\cos kx\Bigr)

checks at x=0x = 0: the bracket is 1−2r/(1+r)=(1−r)/(1+r)1 - 2r/(1+r) = (1-r)/(1+r), and (1/3)(1−r)/(1+r)=1/3(1/\sqrt3)(1-r)/(1+r) = 1/3. So ∣ck∣∝rk=e−σk\lvert c_k\rvert \propto r^k = e^{-\sigma k} with σ=−ln⁡r=ln⁡(2+3)=1.317\sigma = -\ln r = \ln(2 + \sqrt3) = 1.317. That is the distance from the real axis to the complex zeros x=π±iσx = \pi \pm i\sigma of 2+cos⁡x2 + \cos x, since cos⁡(π+iσ)=−cosh⁡σ=−2\cos(\pi + i\sigma) = -\cosh\sigma = -2. The nearest singularity sets the rate, and the grid keeps modes to k=N/2k = N/2, so the error should behave like Ne−σN/2N e^{-\sigma N/2} (the factor NN is the derivative’s kk). For 1/(1.25+cos⁡x)1/(1.25 + \cos x), σ=ln⁡2=0.693\sigma = \ln 2 = 0.693: a closer pole, slower decay.

Maximum error over the nodes for the derivative of 1/(2+cos⁡x)1/(2+\cos x):

NN163264128256
FD24.20×10−24.20\times10^{-2}1.12×10−21.12\times10^{-2}2.85×10−32.85\times10^{-3}7.19×10−47.19\times10^{-4}1.80×10−41.80\times10^{-4}
FD41.19×10−21.19\times10^{-2}9.31×10−49.31\times10^{-4}6.70×10−56.70\times10^{-5}4.27×10−64.27\times10^{-6}2.68×10−72.68\times10^{-7}
spectral1.40×10−41.40\times10^{-4}7.51×10−97.51\times10^{-9}roundingroundingrounding

“Rounding” means about 10−1410^{-14}, whose digits depend on the implementation. FD2 and FD4 lose a fixed factor, 44 (log-log slope 1.991.99 between 6464 and 128128) and 1616 (slope 3.973.97), per doubling of NN. Between N=16N = 16 and 3232 the spectral error shrinks about 19,00019{,}000-fold. The smallest NN in the sim’s list (8,12,16,24,…,40968, 12, 16, 24, \dots, 4096) reaching 10−610^{-6}:

functionFD2FD4spectral
1/(2+cos⁡x)1/(2+\cos x)409640961921923232
1/(1.25+cos⁡x)1/(1.25+\cos x)none up to 409640967687686464

A least-squares fit of ln⁡(error)\ln(\text{error}) against NN over the entries where the spectral error lies between 10−1010^{-10} and 5×10−25\times10^{-2} gives e−ρNe^{-\rho N} with ρ=0.601\rho = 0.601 and 0.3220.322, against σ/2=0.659\sigma/2 = 0.659 and 0.3470.347. The rates sit a little below the prediction, plausibly because of the extra factor NN (my guess). Four or five points per fit: agreement to about 10%10\%.

◆ Interactive Derivative error against N for FD2, FD4 and the FFT, what each formula does to one wave, and the aliasing of a product

Loading simulation…

Try ∣sin⁡x∣3\lvert\sin x\rvert^3 in the sim. At N=64N = 64 the errors are 1.13×10−21.13\times10^{-2}, 1.77×10−31.77\times10^{-3} and 1.09×10−31.09\times10^{-3} for FD2, FD4 and spectral, and between N=64N = 64 and 128128 the log-log slopes are 1.981.98, 2.102.10 and 2.002.00: the three methods collapse onto an order-two line. The function, not the method, is the limit: its third derivative jumps at x=0x = 0 and π\pi.

Pseudo-spectral nonlinear terms

Take Burgers’ equation ut+u ux=νuxxu_t + u\,u_x = \nu u_{xx}. Derivatives and the diffusion are diagonal in Fourier space, so they are one multiplication each. The product u uxu\,u_x is not: in coefficient space it is a convolution, ∑mu^m ikn−mu^n−m\sum_m \hat u_m\, ik_{n-m}\hat u_{n-m}, which costs N2N^2. The pseudo-spectral idea avoids that. Differentiate in Fourier space, transform both factors back to the grid, multiply pointwise, and transform the product forward: Nlog⁡NN\log N per step.

The price is aliasing, and the cure is a rule you can derive in two lines. If uu contains wavenumbers up to KK, then u2u^2 contains wavenumbers up to 2K2K. On an NN-point grid, wavenumber mm above Nyquist is indistinguishable from m−Nm - N and shows up there. A product mode mm in the range K<m≤2KK \lt m \le 2K therefore lands at ∣m−N∣≥N−2K\lvert m - N\rvert \ge N - 2K. The retained band ∣k∣≤K\lvert k\rvert \le K is untouched exactly when that lowest landing spot lies above KK:

N−2K>K⟺K<N3.N - 2K \gt K \quad\Longleftrightarrow\quad K \lt \frac N3 .

This is the 2/32/3 rule: keep wavenumbers below N/3N/3 (two thirds of the way to Nyquist), zero the rest before each product, and the aliases land on modes you discard anyway.

Worked example by hand. Take N=12N = 12, so N/3=4N/3 = 4. First u=cos⁡4xu = \cos 4x: u2=12+12cos⁡8xu^2 = \tfrac12 + \tfrac12\cos 8x, and on the grid 8≡8−12=−48 \equiv 8 - 12 = -4, so the sampled square is 12+12cos⁡4x\tfrac12 + \tfrac12\cos 4x, a wave at k=4k = 4 that the true square does not contain. The FFT of the sampled u2u^2 has coefficient 0.250.25 at k=±4k = \pm4, where the exact value is 00. Now u=cos⁡3xu = \cos 3x, below N/3N/3: u2=12+12cos⁡6xu^2 = \tfrac12 + \tfrac12\cos 6x, and wavenumber 66 is the Nyquist slot, outside the retained band. The retained coefficients are exact.

The sim’s third view measures this on u=∑k=1Kcos⁡(kx)/ku = \sum_{k=1}^{K}\cos(kx)/k: the largest coefficient error in the band ∣k∣≤K\lvert k\rvert \le K, relative to the largest exact coefficient. At N=48N = 48 the threshold is 1616:

KK1215162024
error of u2u^2 on the grid4×10−164\times10^{-16}4×10−164\times10^{-16}1.2×10−31.2\times10^{-3}2.2×10−22.2\times10^{-2}9.7×10−29.7\times10^{-2}

Round-off up to K=15K = 15, then a jump at K=16=N/3K = 16 = N/3, as derived. With the rule on, the field is first cut to ∣k∣<16\lvert k\rvert \lt 16 and the product is exact in the retained band even for K=24K = 24, at the price of 1.5%1.5\% of the field’s energy. A cousin, from memory, pads to 3N/23N/2 points instead of discarding a third. A cubic term reaches 3K3K, which asks for K<N/4K \lt N/4 (Problem 2).

Diffusion, diagonal in Fourier space, can be advanced exactly by e−νk2Δte^{-\nu k^2\Delta t} per mode. Advection still has a step limit (10.5 Wave Equation Numerics & the CFL Condition). The spectral derivative has eigenvalues up to cπ/hc\pi/h, central differences only c/hc/h, and RK4’s stability region reaches 22=2.832\sqrt2 = 2.83 on the imaginary axis (computed from its polynomial). So Δt≤0.90 h/c\Delta t \le 0.90\,h/c here, about π\pi times shorter than the 2.83 h/c2.83\,h/c FD2 allows.

The FFT Poisson solver

Now the thread from the multigrid lesson. Solve −∇2u=f-\nabla^2 u = f on [0,2π)2[0, 2\pi)^2, periodic in both directions. A wave ei(kx+ly)e^{i(kx + ly)} has −∇2→k2+l2-\nabla^2 \to k^2 + l^2, so in coefficients the equation reads (k2+l2)u^kl=f^kl(k^2 + l^2)\hat u_{kl} = \hat f_{kl}. The solver is three steps: two-dimensional FFT of ff, divide by k2+l2k^2 + l^2, inverse FFT. The cost is O(N2log⁡N)O(N^2\log N) for N2N^2 unknowns, with no iteration, tolerance, smoother or grid hierarchy.

One snag. At k=l=0k = l = 0 the divisor is zero. This is the singularity 10.9 Multigrid met with Neumann walls: the constant is in the kernel (1.3 Linear Systems, Kernel & Column Space), so a solution exists only when the mean f^00\hat f_{00} is zero, and is then unique up to a constant. In code: drop the mean of ff and set u^00=0\hat u_{00} = 0, which picks the zero-mean solution.

There are two honest choices of divisor, because “the Laplacian” can mean two things. The spectral symbol k2+l2k^2 + l^2 is the continuum Laplacian, and the answer is spectrally accurate. The finite-difference symbol comes from applying the five-point stencil of 10.1 Finite Differences: Discretizing Derivatives to a wave:

4−2cos⁡kh−2cos⁡lhh2.\frac{4 - 2\cos kh - 2\cos lh}{h^2}.

Dividing by this solves, to round-off, the periodic form of the five-point system of 10.8 Elliptic Solvers: Jacobi, Gauss–Seidel & SOR in one shot. Test both on u=esin⁡xcos⁡yu = e^{\sin x}\cos y, whose source is f=esin⁡xcos⁡y (sin⁡2x+sin⁡x)f = e^{\sin x}\cos y\,(\sin^2x + \sin x). Maximum error over the nodes:

NN8163264
spectral symbol1.2×10−31.2\times10^{-3}8.1×10−98.1\times10^{-9}roundingrounding
five-point symbol0.2130.2130.04960.04960.01220.01220.003040.00304

The five-point answer solves the discrete problem exactly, so its error is the discretisation error, second order: ratios 4.064.06 and 4.014.01 for 16→32→6416 \to 32 \to 64. The spectral answer hits rounding at N=32N = 32. I checked the five-point solve at N=16N = 16 against a dense solve of the 256×256256\times256 matrix: agreement to 9×10−149\times10^{-14}.

Honest limits. All this needs the eigenvectors of the operator to be fast-transform waves. That is true for periodic conditions (FFT). From the multigrid lesson, on a box with u=0u = 0 on the edges the eigenvectors of tridiag⁡(−1,2,−1)\operatorname{tridiag}(-1, 2, -1) are the sine vectors sin⁡(jkπ/N)\sin(jk\pi/N) with eigenvalue 2−2cos⁡(kπ/N)2 - 2\cos(k\pi/N), so a sine transform diagonalises the five-point Poisson matrix. I checked a two-dimensional version at N=40N = 40 against a sparse direct solve: agreement to 1.4×10−141.4\times10^{-14}. For zero normal derivative on a box (Neumann), the transform is the cosine transform (from memory, not tested here). Mixed conditions, jumping coefficients and non-box domains destroy the diagonalisation. Multigrid costs O(N2)O(N^2), a log factor less, and keeps working on all of those; the FFT solver wins where its conditions hold, for simplicity and exactness.

Beyond periodic: Chebyshev points (from memory)

A non-periodic function on [−1,1][-1, 1] extends periodically only with a jump, and then the coefficients fall like 1/k1/k and Gibbs ringing (8.5 Convergence & the Gibbs Phenomenon) returns. The classical escape, from memory and not computed here, is to substitute x=cos⁡θx = \cos\theta. A function of xx becomes an even 2π2\pi-periodic function of θ\theta, and a cosine series in θ\theta is a polynomial series in xx, the Chebyshev polynomials Tn(cos⁡θ)=cos⁡nθT_n(\cos\theta) = \cos n\theta. The natural grid is xj=cos⁡(jπ/N)x_j = \cos(j\pi/N), the Chebyshev points, which are equally spaced in θ\theta and so pile up near the ends of the interval. A cosine transform in θ\theta brings the FFT back. Equally spaced points can make polynomial interpolation diverge at the ends (Runge’s example, from memory), and the clustering prevents that: smooth functions converge exponentially again, without periodicity. The cost: the smallest spacing is about N−2N^{-2} (Problem 4), which tightens explicit step limits (from memory).

The exercise: a periodic Poisson solver

First a playground on the two phenomena above, then the solver.

🐍 PythonA wave the grid cannot hold, and the square of cos 4x on 12 points
⌘/Ctrl + Enter
🧪 Coding exerciseExercise: solve -Laplacian u = f on a periodic grid with two FFTs
⌘/Ctrl + Enter

Where spectral methods stop

The sim’s ∣sin⁡x∣3\lvert\sin x\rvert^3 curve showed the first limit: a spectral method is as accurate as the solution is smooth, and the solutions that matter to fluids often are not. A shock or a thin boundary layer is steep or discontinuous, and a Fourier truncation of it rings (8.5 Convergence & the Gibbs Phenomenon). The second limit is geometry. The trick needs a box, or a few shapes with known eigenfunctions (8.6 Orthogonal Polynomials & Special Functions); an airfoil or a car in a wind tunnel does not qualify. The third is locality: one global basis means one resolution everywhere. These are the questions 10.13 Introduction to Finite Elements takes up. Its tool is the weak form, an integral version of the equation that needs no pointwise derivatives, tested against a family of basis functions. Spectral methods can be read the same way, with Fourier modes as the family (from memory); finite elements use piecewise-linear “hat” functions on a mesh of triangles, which can follow a boundary and are local. I have not computed an element yet, so I claim only what the syllabus lists: weak forms, hat functions, stiffness matrices.

Concept checks

✅ Concept check

A central difference differentiates $e^{ikx}$ as if the wavenumber were $\sin(kh)/h$. For a wave of $2\pi/(kh) = 25.6$ points per wavelength the relative error is about $1\%$. About how many points per wavelength does the spectral derivative need to differentiate that wave exactly?

✅ Concept check

$1/(2+\cos x)$ has its nearest singularity at distance $\sigma = \ln(2+\sqrt3) = 1.317$ from the real axis. The Fourier coefficients fall like $e^{-\sigma k}$. By what factor does $e^{-\sigma N/2}$ shrink when $N$ is increased by $8$?

✅ Concept check

On a grid of $N = 30$ points, which highest wavenumber $K$ of $u$ keeps the band $\lvert k\rvert \le K$ free of aliasing in $u^2$?

✅ Concept checkselect all that apply

Select all that are true of the FFT Poisson solver on a periodic box.

Problems

✏️ Pen & paperThe effective wavenumber●○○

Show that the fourth-order formula (−fj+2+8fj+1−8fj−1+fj−2)/12h(-f_{j+2} + 8f_{j+1} - 8f_{j-1} + f_{j-2})/12h applied to eikxe^{ikx} gives the multiplier i(8sin⁡kh−sin⁡2kh)/6hi(8\sin kh - \sin 2kh)/6h, and that its relative error for small θ=kh\theta = kh is θ4/30\theta^4/30. Estimate the points per wavelength for a 1%1\% error.

Show worked solution

Pulling out eikxje^{ikx_j} leaves (−e2iθ+8eiθ−8e−iθ+e−2iθ)/12h=(−2isin⁡2θ+16isin⁡θ)/12h=i(8sin⁡θ−sin⁡2θ)/6h(-e^{2i\theta} + 8e^{i\theta} - 8e^{-i\theta} + e^{-2i\theta})/12h = (-2i\sin2\theta + 16i\sin\theta)/12h = i(8\sin\theta - \sin2\theta)/6h. With sin⁡θ=θ−θ3/6+θ5/120\sin\theta = \theta - \theta^3/6 + \theta^5/120 and sin⁡2θ=2θ−8θ3/6+32θ5/120\sin2\theta = 2\theta - 8\theta^3/6 + 32\theta^5/120: 8sin⁡θ−sin⁡2θ=6θ+(−8+8)θ3/6+(8−32)θ5/120=6θ−θ5/58\sin\theta - \sin2\theta = 6\theta + (-8 + 8)\theta^3/6 + (8 - 32)\theta^5/120 = 6\theta - \theta^5/5. Divide by 6θ6\theta: 1−θ4/301 - \theta^4/30. Setting θ4/30=0.01\theta^4/30 = 0.01 gives θ=0.740\theta = 0.740, so 8.58.5 points per wavelength (exact solve: 8.358.35).

✏️ Pen & paperCubic nonlinearity●●○

If uu has wavenumbers up to KK and u3u^3 is evaluated on NN points, find the condition on KK for no aliasing into the band ∣k∣≤K\lvert k\rvert \le K, and its value at N=48N = 48.

Show worked solution

u3u^3 has wavenumbers up to 3K3K. A mode mm with N/2<m≤3KN/2 \lt m \le 3K lands at N−m≥N−3KN - m \ge N - 3K. No pollution of the band requires N−3K>KN - 3K \gt K, so K<N/4K \lt N/4. For N=48N = 48, K≤11K \le 11, against K≤15K \le 15 for quadratic terms: a cubic costs more resolution.

✏️ Pen & paperA periodic Poisson problem by hand●●○

Solve −u′′=cos⁡x+2sin⁡2x-u'' = \cos x + 2\sin 2x on the period 2π2\pi. Then decide whether −u′′=cos⁡x+1-u'' = \cos x + 1 has a periodic solution, and say what goes wrong in the Fourier picture.

Show worked solution

Each wave is divided by k2k^2: cos⁡x→cos⁡x/1\cos x \to \cos x/1, sin⁡2x→sin⁡2x/4\sin 2x \to \sin 2x/4, so u=cos⁡x+12sin⁡2x+Cu = \cos x + \tfrac12\sin2x + C for any constant CC. The constant is the kernel (1.3 Linear Systems, Kernel & Column Space). For cos⁡x+1\cos x + 1: the term 11 has k=0k = 0, and 0⋅u^0=10\cdot\hat u_0 = 1 has no solution. Equivalently, u′=−x+cu' = -x + c is never periodic. A periodic problem is solvable only when the source has zero mean.

✏️ Pen & paperChebyshev spacing●●●

Show that Tn(cos⁡θ)=cos⁡nθT_n(\cos\theta) = \cos n\theta gives Tn′(1)=n2T_n'(1) = n^2, and that the spacing of the points xj=cos⁡(jπ/N)x_j = \cos(j\pi/N) is about (π/N)sin⁡θj(\pi/N)\sin\theta_j. How small is the smallest spacing, and how does it compare with the uniform spacing 2/N2/N on [−1,1][-1, 1]?

Show worked solution

Differentiating in θ\theta gives Tn′(cos⁡θ)=nsin⁡nθ/sin⁡θ→n2T_n'(\cos\theta) = n\sin n\theta/\sin\theta \to n^2 as θ→0\theta \to 0. For the spacing, xj−xj+1=cos⁡θj−cos⁡(θj+π/N)≈(π/N)sin⁡θjx_j - x_{j+1} = \cos\theta_j - \cos(\theta_j + \pi/N) \approx (\pi/N)\sin\theta_j. The first gap is the smallest: 1−cos⁡(π/N)≈12(π/N)2=4.9/N21 - \cos(\pi/N) \approx \tfrac12(\pi/N)^2 = 4.9/N^2. For N=32N = 32 that is 0.00480.0048, against the uniform 2/N=0.06252/N = 0.0625: thirteen times finer, which is why a wall layer is resolved well (and why explicit stepping needs a tiny Δt\Delta t, from memory).

Key Takeaways

  • A periodic derivative is FFT, multiply by ikik (Nyquist slot by 00), inverse FFT: Nlog⁡NN\log N, exact below Nyquist. FD2 and FD4 multiply by isin⁡(kh)/hi\sin(kh)/h and i(8sin⁡kh−sin⁡2kh)/6hi(8\sin kh - \sin 2kh)/6h instead.
  • For a 1%1\% derivative error FD2 needs 25.625.6 points per wavelength, FD4 8.358.35, the spectral method 22.
  • An analytic function has coefficients e−σke^{-\sigma k}, σ\sigma the distance to the nearest complex singularity, and the spectral error falls like Ne−σN/2N e^{-\sigma N/2}. For 1/(2+cos⁡x)1/(2+\cos x) to 10−610^{-6}: N=32N = 32 spectral, 192192 FD4, 40964096 FD2. For ∣sin⁡x∣3\lvert\sin x\rvert^3 all three fall on an order-two line.
  • Pseudo-spectral products are pointwise on the grid. A mode mm above Nyquist aliases to ∣m−N∣\lvert m - N\rvert; the band ∣k∣≤K\lvert k\rvert \le K stays clean exactly when K<N/3K \lt N/3 (the 2/32/3 rule; N/4N/4 for cubic terms).
  • Spectral advection’s step limit is about π\pi times tighter than FD2’s at the same hh.
  • −∇2u=f-\nabla^2 u = f on a periodic box is FFT, divide by k2+l2k^2 + l^2 (or the five-point symbol), inverse FFT, zero mode dropped. Dirichlet walls use a sine transform and Neumann a cosine transform (from memory); obstacles and jumping coefficients break the trick. Chebyshev points extend smooth non-periodic problems (from memory).
  • Next: 10.13 Introduction to Finite Elements, where weak forms and hat functions handle geometry and rough solutions.
Finished this lesson?

Mark it complete to track your progress (saved in this browser). Reading every section does this for you.