Pseudo-spectral method

Last updated May 14, 2024

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 representation of functions on a quadrature grid^{[ definition needed ]}. This simplifies the evaluation of certain operators, and can considerably speed up the calculation when using fast algorithms such as the fast Fourier transform.

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+1,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 contribution), 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 inx}.

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_{n-k}c_{k},

where the elements $V_{n-k}$ are calculated through the explicit Fourier-transform

V_{n-k}=\int _{0}^{1}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_{n-k}$ 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_{n-k}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:

$f(x),{\tilde {f}}(x)=V(x)f(x)$ are expanded in a finite set of basis functions (this is the spectral method).
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.
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_{n-m}c_{m}

with $V_{n-m}=\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 _{i=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 \cdot \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.

Notes

↑ Orszag, Steven A. (September 1972). "Comparison of Pseudospectral and Spectral Approximation". Studies in Applied Mathematics. 51 (3): 253–259. doi:10.1002/sapm1972513253.

Related Research Articles

Bra–ket notation, also called Dirac notation, is a notation for linear algebra and linear operators on complex vector spaces together with their dual space both in the finite-dimensional and infinite-dimensional case. It is specifically designed to ease the types of calculations that frequently come up in quantum mechanics. Its use in quantum mechanics is quite widespread.

In theoretical physics, a Feynman diagram is a pictorial representation of the mathematical expressions describing the behavior and interaction of subatomic particles. The scheme is named after American physicist Richard Feynman, who introduced the diagrams in 1948. The interaction of subatomic particles can be complex and difficult to understand; Feynman diagrams give a simple visualization of what would otherwise be an arcane and abstract formula. According to David Kaiser, "Since the middle of the 20th century, theoretical physicists have increasingly turned to this tool to help them undertake critical calculations. Feynman diagrams have revolutionized nearly every aspect of theoretical physics." While the diagrams are applied primarily to quantum field theory, they can also be used in other areas of physics, such as solid-state theory. Frank Wilczek wrote that the calculations that won him the 2004 Nobel Prize in Physics "would have been literally unthinkable without Feynman diagrams, as would [Wilczek's] calculations that established a route to production and observation of the Higgs particle."

The Riesz representation theorem, sometimes called the Riesz–Fréchet representation theorem after Frigyes Riesz and Maurice René Fréchet, establishes an important connection between a Hilbert space and its continuous dual space. If the underlying field is the real numbers, the two are isometrically isomorphic; if the underlying field is the complex numbers, the two are isometrically anti-isomorphic. The (anti-) isomorphism is a particular natural isomorphism.

A wavelet is a wave-like oscillation with an amplitude that begins at zero, increases or decreases, and then returns to zero one or more times. Wavelets are termed a "brief oscillation". A taxonomy of wavelets has been established, based on the number and direction of its pulses. Wavelets are imbued with specific properties that make them useful for signal processing.

Distributions, also known as Schwartz distributions or generalized functions, are objects that generalize the classical notion of functions in mathematical analysis. Distributions make it possible to differentiate functions whose derivatives do not exist in the classical sense. In particular, any locally integrable function has a distributional derivative.

<span class="mw-page-title-main">Wave function</span> Mathematical description of the quantum state of a system

In quantum physics, a wave function is a mathematical description of the quantum state of an isolated quantum system. The most common symbols for a wave function are the Greek letters $ψ$ and $Ψ$ . Wave functions are complex-valued. For example, a wave function might assign a complex number to each point in a region of space. The Born rule provides the means to turn these complex probability amplitudes into actual probabilities. In one common form, it says that the squared modulus of a wave function that depends upon position is the probability density of measuring a particle as being at a given place. The integral of a wavefunction's squared modulus over all the system's degrees of freedom must be equal to 1, a condition called normalization. Since the wave function is complex-valued, only its relative phase and relative magnitude can be measured; its value does not, in isolation, tell anything about the magnitudes or directions of measurable observables. One has to apply quantum operators, whose eigenvalues correspond to sets of possible results of measurements, to the wave function $ψ$ and calculate the statistical distributions for measurable quantities.

In mathematics, a self-adjoint operator on an infinite-dimensional complex vector space V with inner product $is a linear map A that is its own adjoint. If V is finite-dimensional with a given orthonormal basis, this is equivalent to the condition that the matrix of A is a Hermitian matrix, i.e., equal to its conjugate transpose A * . By the finite-dimensional spectral theorem, V has an orthonormal basis such that the matrix of A relative to this basis is a diagonal matrix with entries in the real numbers. This article deals with applying generalizations of this concept to operators on Hilbert spaces of arbitrary dimension.$

In mathematics, particularly linear algebra, an orthonormal basis for an inner product space $with finite dimension is a basis for whose vectors are orthonormal, that is, they are all unit vectors and orthogonal to each other. For example, the standard basis for a Euclidean space is an orthonormal basis, where the relevant inner product is the dot product of vectors. The image of the standard basis under a rotation or reflection is also orthonormal, and every orthonormal basis for arises in this fashion.$

<span class="mw-page-title-main">Eigenfunction</span> Mathematical function of a linear operator

In mathematics, an eigenfunction of a linear operator D defined on some function space is any non-zero function $in that space that, when acted upon by D, is only multiplied by some scaling factor called an eigenvalue. As an equation, this condition can be written as$

The Fock space is an algebraic construction used in quantum mechanics to construct the quantum states space of a variable or unknown number of identical particles from a single particle Hilbert space $H$ . It is named after V. A. Fock who first introduced it in his 1932 paper "Konfigurationsraum und zweite Quantelung".

In physics, an operator is a function over a space of physical states onto another space of physical states. The simplest example of the utility of operators is the study of symmetry. Because of this, they are useful tools in classical mechanics. Operators are even more important in quantum mechanics, where they form an intrinsic part of the formulation of the theory.

In mathematics, spectral theory is an inclusive term for theories extending the eigenvector and eigenvalue theory of a single square matrix to a much broader theory of the structure of operators in a variety of mathematical spaces. It is a result of studies of linear algebra and the solutions of systems of linear equations and their generalizations. The theory is connected to that of analytic functions because the spectral properties of an operator are related to analytic functions of the spectral parameter.

In physics, a pseudopotential or effective potential is used as an approximation for the simplified description of complex systems. Applications include atomic physics and neutron scattering. The pseudopotential approximation was first introduced by Hans Hellmann in 1934.

In functional analysis, a branch of mathematics, it is sometimes possible to generalize the notion of the determinant of a square matrix of finite order (representing a linear transformation from a finite-dimensional vector space to itself) to the infinite-dimensional case of a linear operator S mapping a function space V to itself. The corresponding quantity det(S) is called the functional determinant of S.

In mathematics, a dual wavelet is the dual to a wavelet. In general, the wavelet series generated by a square-integrable function will have a dual series, in the sense of the Riesz representation theorem. However, the dual series is not itself in general representable by a square-integrable function.

The time-evolving block decimation (TEBD) algorithm is a numerical scheme used to simulate one-dimensional quantum many-body systems, characterized by at most nearest-neighbour interactions. It is dubbed Time-evolving Block Decimation because it dynamically identifies the relevant low-dimensional Hilbert subspaces of an exponentially larger original Hilbert space. The algorithm, based on the Matrix Product States formalism, is highly efficient when the amount of entanglement in the system is limited, a requirement fulfilled by a large class of quantum many-body systems in one dimension.

Overcompleteness is a concept from linear algebra that is widely used in mathematics, computer science, engineering, and statistics. It was introduced by R. J. Duffin and A. C. Schaeffer in 1952.

Coherent states have been introduced in a physical context, first as quasi-classical states in quantum mechanics, then as the backbone of quantum optics and they are described in that spirit in the article Coherent states. However, they have generated a huge variety of generalizations, which have led to a tremendous amount of literature in mathematical physics. In this article, we sketch the main directions of research on this line. For further details, we refer to several existing surveys.

The projector augmented wave method (PAW) is a technique used in ab initio electronic structure calculations. It is a generalization of the pseudopotential and linear augmented-plane-wave methods, and allows for density functional theory calculations to be performed with greater computational efficiency.

In mathematics, the Weil–Brezin map, named after André Weil and Jonathan Brezin, is a unitary transformation that maps a Schwartz function on the real line to a smooth function on the Heisenberg manifold. The Weil–Brezin map gives a geometric interpretation of the Fourier transform, the Plancherel theorem and the Poisson summation formula. The image of Gaussian functions under the Weil–Brezin map are nil-theta functions, which are related to theta functions. The Weil–Brezin map is sometimes referred to as the Zak transform, which is widely applied in the field of physics and signal processing; however, the Weil–Brezin Map is defined via Heisenberg group geometrically, whereas there is no direct geometric or group theoretic interpretation from the Zak transform.

References

Orszag, Steven A. (1969). "Numerical Methods for the Simulation of Turbulence". Physics of Fluids. 12 (12): II-250. doi:10.1063/1.1692445.
Gottlieb, David; Orszag, Steven A. (1989). Numerical analysis of spectral methods : theory and applications (5. print. ed.). Philadelphia, Pa.: Society for Industrial and Applied Mathematics. ISBN 978-0898710236.
Hesthaven, Jan S.; Gottlieb, Sigal; Gottlieb, David (2007). Spectral methods for time-dependent problems (1. publ. ed.). Cambridge [u.a.]: Cambridge Univ. Press. ISBN 9780521792110.
Jie Shen, Tao Tang and Li-Lian Wang (2011) "Spectral Methods: Algorithms, Analysis and Applications" (Springer Series in Computational Mathematics, V. 41, Springer), ISBN 354071040X.
Trefethen, Lloyd N. (2000). Spectral methods in MATLAB (3rd. repr. ed.). Philadelphia, Pa: SIAM. ISBN 978-0-89871-465-4.
Fornberg, Bengt (1996). A Practical Guide to Pseudospectral Methods. Cambridge: Cambridge University Press. ISBN 9780511626357.
Boyd, John P. (2001). Chebyshev and Fourier spectral methods (2nd ed., rev. ed.). Mineola, N.Y.: Dover Publications. ISBN 978-0486411835.
Funaro, Daniele (1992). Polynomial approximation of differential equations. Berlin: Springer-Verlag. ISBN 978-3-540-46783-0.
de Frutos, Javier; Novo, Julia (January 2000). "A Spectral Element Method for the Navier--Stokes Equations with Improved Accuracy". SIAM Journal on Numerical Analysis. 38 (3): 799–819. doi:10.1137/S0036142999351984.
Claudio, Canuto; M. Yousuff, Hussaini; Alfio, Quarteroni; Thomas A., Zang (2006). Spectral methods fundamentals in single domains. Berlin: Springer-Verlag. ISBN 978-3-540-30726-6.
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. ISBN 978-0-521-88068-8.

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[1] Orszag, Steven A. (September 1972). "Comparison of Pseudospectral and Spectral Approximation". Studies in Applied Mathematics. 51 (3): 253–259. doi:10.1002/sapm1972513253.

[1]