World Library  
Flag as Inappropriate
Email this Article

Pseudo-spectral method

Article Id: WHEBN0000474353
Reproduction Date:

Title: Pseudo-spectral method  
Author: World Heritage Encyclopedia
Language: English
Subject: Steven Orszag, Neumann–Neumann methods, FETI-DP, Abstract additive Schwarz method, Neumann–Dirichlet method
Collection: Numerical Analysis
Publisher: World Heritage Encyclopedia
Publication
Date:
 

Pseudo-spectral method

Pseudo-spectral methods,[1] also known as discrete variable representation (DVR) methods, are a class of numerical methods used in applied mathematics and scientific computing for the solution of partial differential equations. They are closely related to spectral methods, but complement the basis by an additional pseudo-spectral basis, which allows to represent functions on a quadrature grid. This simplifies the evaluation of certain operators, and can considerably speed up the calculation when using fast algorithms such as the fast Fourier transform.

Contents

  • Motivation with a concrete example 1
  • Technical discussion 2
    • Expansion in a basis 2.1
    • Quadrature 2.2
    • Multiplication 2.3
  • Special pseudospectral schemes 3
    • The Fourier method 3.1
    • Polynomials 3.2
  • References 4

Motivation with a concrete example

Take the initial-value problem

i \frac{\partial}{\partial t} \psi(x, t) = \Bigl[-\frac{\partial^2}{\partial x^2} + V(x) \Bigr] \psi(x,t), \qquad\qquad \psi(t_0) = \psi_0

with periodic conditions \psi(x+2\pi, t) = \psi(x, t). This specific example is the Schrödinger equation for a particle in a potential V(x), but the structure is more general. In many practical partial differential equations, one has a term that involves derivatives (such as a kinetic energy contributions), and a multiplication with a function (for example, a potential).

In the spectral method, the solution \psi is expanded in a suitable set of basis functions, for example plane waves,

\psi(x,t) = \frac{1}{\sqrt{2\pi}} \sum_n c_n(t) e^{2\pi i n x} .

Insertion and equating identical coefficients yields a set of ordinary differential equations for the coefficients,

i\frac{d}{dt} c_n(t) = (2\pi n)^2 c_n + \sum_k V_{nk} c_k,

where the elements V_{nk} are calculated through the explicit Fourier-transform

V_{nk} = \frac{1}{2\pi} \int_0^{2\pi} V(x) \ e^{2\pi i (k-n) x} dx .

The solution would then be obtained by truncating the expansion to N basis functions, and finding a solution for the c_n(t). In general, this is done by numerical methods, such as Runge–Kutta methods. For the numerical solutions, the right-hand side of the ordinary differential equation has to be evaluated repeatedly at different time steps. At this point, the spectral method has a major problem with the potential term V(x).

In the spectral representation, the multiplication with the function V(x) transforms into a vector-matrix multiplication, which scales as N^2. Also, the matrix elements V_{nk} need to be evaluated explicitly before the differential equation for the coefficients can be solved, which requires an additional step.

In the pseudo-spectral method, this term is evaluated differently. Given the coefficients c_n(t), an inverse discrete Fourier transform yields the value of the function \psi at discrete grid points x_j = 2\pi j/N. At these grid points, the function is then multiplied, \psi'(x_i, t) = V(x_i) \psi(x_i, t), and the result Fourier-transformed back. This yields a new set of coefficients c'_n(t) that are used instead of the matrix product \sum_k V_{nk} c_k(t).

It can be shown that both methods have similar accuracy. However, the pseudo-spectral method allows the use of a fast Fourier transform, which scales as O(N\ln N), and is therefore significantly more efficient than the matrix multiplication. Also, the function V(x) can be used directly without evaluating any additional integrals.

Technical discussion

In a more abstract way, the pseudo-spectral method deals with the multiplication of two functions V(x) and f(x) as part of a partial differential equation. To simplify the notation, the time-dependence is dropped. Conceptually, it consists of three steps:

  1. f(x), \tilde{f}(x) = V(x)f(x) are expanded in a finite set of basis functions (this is the spectral method).
  2. For a given set of basis functions, a quadrature is sought that converts scalar products of these basis functions into a weighted sum over grid points.
  3. The product is calculated by multiplying V,f at each grid point.


Expansion in a basis

The functions f, \tilde f can be expanded in a finite basis \{\phi_n\}_{n = 0,\ldots,N} as

f(x) = \sum_{n=0}^N c_n \phi_n(x)
\tilde f(x) = \sum_{n=0}^N \tilde c_n \phi_n(x)

For simplicity, let the basis be orthogonal and normalized, \langle \phi_n, \phi_m \rangle = \delta_{nm} using the inner product \langle f, g \rangle = \int_a^b f(x) \overline{g(x)} dx with appropriate boundaries a,b. The coefficients are then obtained by

c_n = \langle f, \phi_n \rangle
\tilde c_n = \langle \tilde f, \phi_n \rangle

A bit of calculus yields then

\tilde c_n = \sum_{m=0}^N V_{nm} c_m

with V_{nm} = \langle V\phi_m, \phi_n \rangle. This forms the basis of the spectral method. To distinguish the basis of the \phi_n from the quadrature basis, the expansion is sometimes called Finite Basis Representation (FBR).


Quadrature

For a given basis \{\phi_n\} and number of N+1 basis functions, one can try to find a quadrature, i.e., a set of N+1 points and weights such that

\langle \phi_n, \phi_m \rangle = \sum_{i=0}^N w_i \phi_n(x_i) \overline{\phi_m(x_i)} \qquad\qquad n,m = 0,\ldots,N

Special examples are the Gaussian quadrature for polynomials and the Discrete Fourier Transform for plane waves. It should be stressed that the grid points and weights, x_i,w_i are a function of the basis and the number N.

The quadrature allows an alternative numerical representation of the function f(x), \tilde f(x) through their value at the grid points. This representation is sometimes denoted Discrete Variable Representation (DVR), and is completely equivalent to the expansion in the basis.

f(x_i) = \sum_{n=0}^N c_n \phi_n(x_i)
c_n = \langle f, \phi_n \rangle = \sum_{n=0}^{N} w_i f(x_i) \overline{\phi_n(x_i)}


Multiplication

The multiplication with the function V(x) is then done at each grid point,

\tilde f(x_i) = V(x_i) f(x_i).

This generally introduces an additional approximation. To see this, we can calculate one of the coefficients \tilde c_n:

\tilde c_n = \langle \tilde f, \phi_n \rangle = \sum_i w_i \tilde f(x_i) \overline{\phi_n(x_i)} = \sum_i w_i V(x_i) f(x_i) \overline{\phi_n(x_i)}

However, using the spectral method, the same coefficient would be \tilde c_n = \langle Vf, \phi_n \rangle. The pseudo-spectral method thus introduces the additional approximation

\langle Vf, \phi_n \rangle \approx \sum_i w_i V(x_i) f(x_i) \overline{\phi_n(x_i)}.

If the product Vf can be represented with the given finite set of basis functions, the above equation is exact due to the chosen quadrature.

Special pseudospectral schemes

The Fourier method

If periodic boundary conditions with period [0,L] are imposed on the system, the basis functions can be generated by plane waves,

\phi_n(x) = \frac{1}{\sqrt{L}} e^{-\imath k_n x}

with k_n = (-1)^n \lceil n/2 \rceil 2\pi/L, where \lceil\rceil is the ceiling function.

The quadrature for a cut-off at n_{\text{max}} = N is given by the discrete Fourier transformation. The grid points are equally spaced, x_i = i \Delta x with spacing \Delta x = L / (N+1), and the constant weights are w_i = \Delta x.

For the discussion of the error, note that the product of two plane waves is again a plane wave, \phi_{a} + \phi_b = \phi_c with c \leq a+b. Thus, qualitatively, if the functions f(x), V(x) can be represented sufficiently accurately with N_f, N_V basis functions, the pseudo-spectral method gives accurate results if N_f + N_V basis functions are used.

An expansion in plane waves often has a poor quality and needs many basis functions to converge. However, the transformation between the basis expansion and the grid representation can be done using a Fast Fourier transform, which scales favorably as N \ln N. As a consequence, plane waves are one of the most common expansion that is encountered with pseudo-spectral methods.

Polynomials

Another common expansion is into classical polynomials. Here, the Gaussian quadrature is used, which states that one can always find weights w_i and points x_i such that

\int_a^b w(x) p(x) dx = \sum_{i=0}^N w_i p(x_i)

holds for any polynomial p(x) of degree 2N+1 or less. Typically, the weight function w(x) and ranges a,b are chosen for a specific problem, and leads to one of the different forms of the quadrature. To apply this to the pseudo-spectral method, we choose basis functions \phi_n(x) = \sqrt{w(x)} P_n(x), with P_n being a polynomial of degree n with the property

\int_a^b w(x) P_n(x) P_m(x) dx = \delta_{mn}.

Under these conditions, the \phi_n form an orthonormal basis with respect to the scalar product \langle f, g \rangle = \int_a^b f(x) \overline{g(x)} dx. This basis, together with the quadrature points can then be used for the pseudo-spectral method.

For the discussion of the error, note that if f is well represented by N_f basis functions and V is well represented by a polynomial of degree N_V, their product can be expanded in the first N_f+N_V basis functions, and the pseudo-spectral method will give accurate results for that many basis functions.

Such polynomials occur naturally in several standard problems. For example, the quantum harmonic oscillator is ideally expanded in Hermite polynomials, and Jacobi-polynomials can be used to define the associated Legendre functions typically appearing in rotational problems.

References

  1. ^  
  • Steven A. Orszag (1969) Numerical Methods for the Simulation of Turbulence, Phys. Fluids Supp. II, 12, 250-257
  • D. Gottlieb and S. Orzag (1977) "Numerical Analysis of Spectral Methods : Theory and Applications", SIAM, Philadelphia, PA
  • J. Hesthaven, S. Gottlieb and D. Gottlieb (2007) "Spectral methods for time-dependent problems", Cambridge UP, Cambridge, UK
  • Lloyd N. Trefethen (2000) Spectral Methods in MATLAB. SIAM, Philadelphia, PA
  • Bengt Fornberg (1996) A Practical Guide to Pseudospectral Methods. Cambridge University Press, Cambridge, UK
  • Chebyshev and Fourier Spectral Methods by John P. Boyd.
  • Polynomial Approximation of Differential Equations, by Daniele Funaro, Lecture Notes in Physics, Volume 8, Springer-Verlag, Heidelberg 1992
  • Javier de Frutos, Julia Novo: A Spectral Element Method for the Navier--Stokes Equations with Improved Accuracy
  • Canuto C., Hussaini M. Y., Quarteroni A., and Zang T.A. (2006) Spectral Methods. Fundamentals in Single Domains. Springer-Verlag, Berlin Heidelberg
  • Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007). "Section 20.7. Spectral Methods". Numerical Recipes: The Art of Scientific Computing (3rd ed.). New York: Cambridge University Press.  
This article was sourced from Creative Commons Attribution-ShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and USA.gov, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for USA.gov and content contributors is made possible from the U.S. Congress, E-Government Act of 2002.
 
Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.
 
By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a non-profit organization.
 


Copyright © World Library Foundation. All rights reserved. eBooks from Project Gutenberg are sponsored by the World Library Foundation,
a 501c(4) Member's Support Non-Profit Organization, and is NOT affiliated with any governmental agency or department.