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 per direction. This lesson shows what the trick buys (errors that fall exponentially, not like a power of ), what it costs (aliasing, periodic boundaries), and where it stops. 9.9 Infinite Domains & the Fourier Transform left the rule “from memory”; here we derive it.
Transcript
- 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.
- 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.
- 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.
- 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.
- 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 -periodic function sampled at , so . The FFT writes the samples as a sum of waves with integer from to . A wave differentiates to times itself, so the recipe of 9.9 Infinite Domains & the Fourier Transform follows: FFT, multiply the coefficient of wavenumber by (the Nyquist entry by ), inverse FFT. As a matrix this is the dense operator , never formed: the cost is , not .
To compare it with finite differences, ask what each formula does to one wave . A central difference gives
the exact multiplier with replaced by . The fourth-order formula gives . Expanding in gives and , so the relative error of the derivative of a wave is for FD2 and for FD4. The spectral formula has for every wave the grid can hold below Nyquist, . The sim’s second view plots these curves.
Turn the curves into a budget. The number of points per wavelength is . Solving numerically gives for FD2, so points per wavelength, and for FD4, so points. At the figures are and . Spectral differentiation needs (the Nyquist limit): a factor of about fewer points per direction than FD2, and fewer than FD4.
Worked example: a wave the grid cannot hold. On points, runs with the Nyquist slot. Sample . On the grid , so the samples are exactly those of . The FFT sees a wave of wavenumber , and the spectral derivative returns at the nodes: The true derivative is 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 with coefficients that shrink as grows. The grid keeps the modes 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 , multiplied by because differentiation multiplies by . Smoothness is the whole story. By the rule of 8.5 Convergence & the Gibbs Phenomenon, when has a jump the coefficients fall like and the derivative error like . When is analytic in a strip around the real axis the coefficients fall geometrically.
Worked example: a function whose rate we can read off. Take . Write . The identity
checks at : the bracket is , and . So with . That is the distance from the real axis to the complex zeros of , since . The nearest singularity sets the rate, and the grid keeps modes to , so the error should behave like (the factor is the derivative’s ). For , : a closer pole, slower decay.
Maximum error over the nodes for the derivative of :
| 16 | 32 | 64 | 128 | 256 | |
|---|---|---|---|---|---|
| FD2 | |||||
| FD4 | |||||
| spectral | rounding | rounding | rounding |
“Rounding” means about , whose digits depend on the implementation. FD2 and FD4 lose a fixed factor, (log-log slope between and ) and (slope ), per doubling of . Between and the spectral error shrinks about -fold. The smallest in the sim’s list () reaching :
| function | FD2 | FD4 | spectral |
|---|---|---|---|
| none up to |
A least-squares fit of against over the entries where the spectral error lies between and gives with and , against and . The rates sit a little below the prediction, plausibly because of the extra factor (my guess). Four or five points per fit: agreement to about .
Try in the sim. At the errors are , and for FD2, FD4 and spectral, and between and the log-log slopes are , and : the three methods collapse onto an order-two line. The function, not the method, is the limit: its third derivative jumps at and .
Pseudo-spectral nonlinear terms
Take Burgers’ equation . Derivatives and the diffusion are diagonal in Fourier space, so they are one multiplication each. The product is not: in coefficient space it is a convolution, , which costs . The pseudo-spectral idea avoids that. Differentiate in Fourier space, transform both factors back to the grid, multiply pointwise, and transform the product forward: per step.
The price is aliasing, and the cure is a rule you can derive in two lines. If contains wavenumbers up to , then contains wavenumbers up to . On an -point grid, wavenumber above Nyquist is indistinguishable from and shows up there. A product mode in the range therefore lands at . The retained band is untouched exactly when that lowest landing spot lies above :
This is the rule: keep wavenumbers below (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 , so . First : , and on the grid , so the sampled square is , a wave at that the true square does not contain. The FFT of the sampled has coefficient at , where the exact value is . Now , below : , and wavenumber is the Nyquist slot, outside the retained band. The retained coefficients are exact.
The sim’s third view measures this on : the largest coefficient error in the band , relative to the largest exact coefficient. At the threshold is :
| 12 | 15 | 16 | 20 | 24 | |
|---|---|---|---|---|---|
| error of on the grid |
Round-off up to , then a jump at , as derived. With the rule on, the field is first cut to and the product is exact in the retained band even for , at the price of of the field’s energy. A cousin, from memory, pads to points instead of discarding a third. A cubic term reaches , which asks for (Problem 2).
Diffusion, diagonal in Fourier space, can be advanced exactly by per mode. Advection still has a step limit (10.5 Wave Equation Numerics & the CFL Condition). The spectral derivative has eigenvalues up to , central differences only , and RK4’s stability region reaches on the imaginary axis (computed from its polynomial). So here, about times shorter than the FD2 allows.
The FFT Poisson solver
Now the thread from the multigrid lesson. Solve on , periodic in both directions. A wave has , so in coefficients the equation reads . The solver is three steps: two-dimensional FFT of , divide by , inverse FFT. The cost is for unknowns, with no iteration, tolerance, smoother or grid hierarchy.
One snag. At 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 is zero, and is then unique up to a constant. In code: drop the mean of and set , which picks the zero-mean solution.
There are two honest choices of divisor, because “the Laplacian” can mean two things. The spectral symbol 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:
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 , whose source is . Maximum error over the nodes:
| 8 | 16 | 32 | 64 | |
|---|---|---|---|---|
| spectral symbol | rounding | rounding | ||
| five-point symbol |
The five-point answer solves the discrete problem exactly, so its error is the discretisation error, second order: ratios and for . The spectral answer hits rounding at . I checked the five-point solve at against a dense solve of the matrix: agreement to .
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 on the edges the eigenvectors of are the sine vectors with eigenvalue , so a sine transform diagonalises the five-point Poisson matrix. I checked a two-dimensional version at against a sparse direct solve: agreement to . 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 , 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 extends periodically only with a jump, and then the coefficients fall like and Gibbs ringing (8.5 Convergence & the Gibbs Phenomenon) returns. The classical escape, from memory and not computed here, is to substitute . A function of becomes an even -periodic function of , and a cosine series in is a polynomial series in , the Chebyshev polynomials . The natural grid is , the Chebyshev points, which are equally spaced in and so pile up near the ends of the interval. A cosine transform in 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 (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.
Where spectral methods stop
The sim’s 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
Problems
Show that the fourth-order formula applied to gives the multiplier , and that its relative error for small is . Estimate the points per wavelength for a error.
Show worked solution
Pulling out leaves . With and : . Divide by : . Setting gives , so points per wavelength (exact solve: ).
If has wavenumbers up to and is evaluated on points, find the condition on for no aliasing into the band , and its value at .
Show worked solution
has wavenumbers up to . A mode with lands at . No pollution of the band requires , so . For , , against for quadratic terms: a cubic costs more resolution.
Solve on the period . Then decide whether has a periodic solution, and say what goes wrong in the Fourier picture.
Show worked solution
Each wave is divided by : , , so for any constant . The constant is the kernel (1.3 Linear Systems, Kernel & Column Space). For : the term has , and has no solution. Equivalently, is never periodic. A periodic problem is solvable only when the source has zero mean.
Show that gives , and that the spacing of the points is about . How small is the smallest spacing, and how does it compare with the uniform spacing on ?
Show worked solution
Differentiating in gives as . For the spacing, . The first gap is the smallest: . For that is , against the uniform : thirteen times finer, which is why a wall layer is resolved well (and why explicit stepping needs a tiny , from memory).
Key Takeaways
- A periodic derivative is FFT, multiply by (Nyquist slot by ), inverse FFT: , exact below Nyquist. FD2 and FD4 multiply by and instead.
- For a derivative error FD2 needs points per wavelength, FD4 , the spectral method .
- An analytic function has coefficients , the distance to the nearest complex singularity, and the spectral error falls like . For to : spectral, FD4, FD2. For all three fall on an order-two line.
- Pseudo-spectral products are pointwise on the grid. A mode above Nyquist aliases to ; the band stays clean exactly when (the rule; for cubic terms).
- Spectral advection’s step limit is about times tighter than FD2’s at the same .
- on a periodic box is FFT, divide by (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.