Math 2.0

Numerical analysis Definition

Pseudo-spectral method

Builds on Spectral methodTrigonometric interpolationDiscrete Fourier transformFast Fourier transformChebyshev polynomials

Definition

Let x0,…,xN−1x_0, \ldots, x_{N-1} be collocation points in a domain Ω\Omega, and let VNV_N be a space of global functions with an interpolation property. For every vector of values (vj)(v_j) there is a unique p∈VNp \in V_N with p(xj)=vjp(x_j) = v_j for all jj. Write INvI_N v for this interpolant. A pseudo-spectral method for an equation ut=𝒩(u)u_t = \mathcal{N}(u), with 𝒩\mathcal{N} a differential operator, is the following scheme:

  1. the unknowns are the values uj(t)≈u(xj,t)u_j(t) \approx u(x_j, t);
  2. each derivative ∂mu\partial^m u is replaced by ∂m(INu)\partial^m (I_N u), evaluated at the points xjx_j;
  3. products and other nonlinear functions of uu and its derivatives are evaluated pointwise at the xjx_j;
  4. the equation is required to hold at each point xjx_j.

It is a spectral method of collocation type.

Remarks

Periodic case: Ω=[0,2π)\Omega = [0, 2\pi), xj=2πj/Nx_j = 2\pi j / N, and VNV_N the trigonometric interpolants of degree about N/2N/2. Derivatives are then computed with the discrete Fourier transform: transform, multiply the coefficient of eikxe^{ikx} by ikik, and transform back. With the fast Fourier transform this costs O(Nlog⁡N)O(N \log N) operations. On an interval one often uses Chebyshev points xj=cos⁡(πj/(N−1))x_j = \cos(\pi j / (N - 1)) and the Chebyshev polynomials.

Example: for N=8N = 8 and uj=sin⁡xju_j = \sin x_j, the transform has only the coefficients of e±ixe^{\pm ix}. Multiplying them by ±i\pm i and transforming back gives cos⁡xj\cos x_j exactly. For Burgers' equation ut+uux=0u_t + u u_x = 0, one forms uxu_x this way and then multiplies by uju_j at each point.

Non-example: a spectral Galerkin method computes the product uuxu u_x through its exact Fourier coefficients, a convolution of coefficient sequences. It does not use pointwise evaluation, so clause 3 fails.

Reading path

To understand this page from the ground up, read these 19 pages in order. The foundations come first.

Show the path as a graph
Big O notation, concept, no evidence levelBig O notationconceptChebyshev polynomials, object, no evidence levelChebyshev polynomialsobjectConvolution, concept, no evidence levelConvolutionconceptDiscrete Fourier transform, concept, no evidence levelDiscrete Fourier tran…conceptDivisibility, definition, no evidence levelDivisibilitydefinitionPrimitive root modulo n, concept, no evidence levelPrimitive root modulo…conceptPrimitive root of unity, concept, no evidence levelPrimitive root of uni…conceptSpectral method, concept, no evidence levelSpectral methodconceptTrigonometric interpolation, concept, no evidence levelTrigonometric interpo…conceptCooley–Tukey FFT algorithm, statement, no evidence levelCooley–Tukey FFT algo…statementCongruence modulo n, definition, no evidence levelCongruence modulo ndefinitionGreatest common divisor, definition, no evidence levelGreatest common divis…definitionBluestein's FFT algorithm, statement, no evidence levelBluestein's FFT algor…statementCoprime integers, definition, no evidence levelCoprime integersdefinitionRader's FFT algorithm, statement, no evidence levelRader's FFT algorithmstatementChinese remainder theorem, statement, no evidence levelChinese remainder the…statementPrime-factor FFT algorithm, statement, no evidence levelPrime-factor FFT algo…statementFast Fourier transform, statement, no evidence levelFast Fourier transformstatementPseudo-spectral method, definition, no evidence levelPseudo-spectral methoddefinition
Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.
  • no evidence level
  1. Big O notation concept
  2. Chebyshev polynomials object
  3. Convolution concept
  4. Discrete Fourier transform concept
  5. Divisibility definition
  6. Primitive root modulo n concept
  7. Primitive root of unity concept
  8. Spectral method concept
  9. Trigonometric interpolation concept
  10. Cooley–Tukey FFT algorithm statement
  11. Congruence modulo n definition
  12. Greatest common divisor definition
  13. Bluestein's FFT algorithm statement
  14. Coprime integers definition
  15. Rader's FFT algorithm statement
  16. Chinese remainder theorem statement
  17. Prime-factor FFT algorithm statement
  18. Fast Fourier transform statement
  19. Pseudo-spectral method definition

Further reading

  1. Web https://en.wikipedia.org/wiki/Pseudo-spectral_method
About this page
TagT37Q055GDA
URIm2://T37Q055GDA
Kinddefinition
WritingW0 stub
MSC65M70, 65N35
DefinesPseudo-spectral method
UsesSpectral method, Trigonometric interpolation, Discrete Fourier transform, Fast Fourier transform, Chebyshev polynomials

Markdown · JSON · Edit on GitHub

What this page needs for W1

  • an inventory row: the row of the inventory that the node accounts for (0 of 1)
  • a source with a locator (0 of 1)

The writing levels say how complete the text of a page is. They do not measure its truth.

What links here

No page links to this page yet.