Spectral method
Encyclopedia
Spectral methods are a class of techniques used in applied mathematics
and scientific computing to numerically solve certain Dynamical System
s, often involving the use of the Fast Fourier Transform
. Where applicable, spectral methods have excellent error properties, with the so called "exponential convergence" being the fastest possible. Spectral methods were developed in a long series of papers by Steven Orszag starting in 1969 including, but not limited to, Fourier series methods for periodic geometry problems, polynomial spectral methods for finite and unbounded geometry problems, pseudospectral methods for highly nonlinear problems, and spectral iteration methods for fast solution of steady state problems.
Partial differential equations (PDEs) describe a wide array of physical processes such as heat conduction, fluid flow, and sound propagation. In many such equations, there are underlying "basic waves" that can be used to give efficient algorithms for computing solutions to these PDEs. In a typical case, spectral methods take advantage of this fact by writing the solution as its Fourier series
, substituting this series into the PDE to get a system of ordinary differential equations (ODEs) in the time-dependent coefficients of the trigonometric terms in the series (written in complex exponential form), and using a time-stepping method to solve those ODEs.
The spectral method and the finite element method
are closely related and built on the same ideas; the main difference between them is that the spectral method approximates the solution as linear combination
of continuous functions that are generally nonzero over the domain of solution (usually sinusoids or Chebyshev polynomials), while the finite element method approximates the solution as a linear combination of piecewise functions that are nonzero on small subdomains. Because of this, the spectral method takes on a global approach while the finite element method is a local approach. This is part of why the spectral method works best when the solution is smooth
. In fact there are no known three-dimensional single domain spectral shock capturing results.
In the finite element community, a method where the degree of the elements is very high or increases as the grid parameter h decreases to zero is sometimes called a spectral element method
.
The implementation of the spectral method is normally accomplished either with collocation
or a Galerkin
or a Tau approach.
and Fourier series
. If g(x,y) is a known, complex-valued function of two real variables, and g is periodic in x and y (that is, g(x,y)=g(x+2π,y)=g(x,y+2π)) then we are interested in finding a function f(x,y) so that
where the expression on the left denotes the second partial derivatives of f in x and y, respectively. This is the Poisson equation, and can be physically interpreted as some sort of heat conduction problem.
If we write f and g in Fourier series:
and substitute into the differential equation, we obtain this equation:
We have exchanged partial differentiation with an infinite sum, which is legitimate if we assume for instance that f has a continuous second derivative. By the uniqueness theorem for Fourier expansions, we must then equate the Fourier coefficients term by term, giving
which is an explicit formula for the Fourier coefficients aj,k.
With periodic boundary-conditions, the Poisson equation possesses a solution only if b0,0 = 0. Therefore
we can freely choose a0,0 which will be equal to the mean of the resolution. This corresponds to choosing the
integration constant.
To turn this into an algorithm, only finitely many frequencies are solved for. This introduces an error which can be shown to be proportional to
, where 
and 
is the highest frequency treated.
Since we're only interested in a finite window of frequencies (of size n, say) this can be done using a Fast Fourier Transform
algorithm. Therefore, globally the algorithm runs in time O(n log n).
using a spectral approach.
Given
on the periodic domain
, find 
such that
In weak, conservative form this becomes
where
following inner product
notation. Integrating by parts
and using periodicity grants
To apply the Fourier−Galerkin method
, choose both
and
where
. This reduces the problem to finding 
such that
Using the orthogonality
relation
where 
is the Kronecker delta, we simplify the above three terms for each 
to see
Assemble the three terms for each
to obtain
Dividing through by
, we finally arrive at
With Fourier transformed initial conditions
and forcing 
, this coupled system of ordinary differential equations may be integrated in time (using, e.g., a Runge Kutta technique) to find a solution. The nonlinear term is a convolution
, and there are several transform-based techniques for evaluating it efficiently. See the references by Boyd and Canuto et al. for more details.
is infinitely differentiable, then the numerical algorithm using Fast Fourier Transforms will converge faster than any polynomial in the grid size h. That is, for any n>0, there is a 
such that the error is less than 
for all sufficiently small values of 
. We say that the spectral method is of order 
, for every n>0.
Because a spectral element method
is a finite element method
of very high order, there is a similarity in the convergence properties. However, whereas the spectral method is based on the eigendecomposition of the particular boundary value problem, the spectral element method does not use that information and works for arbitrary elliptic boundary value problem
s.
Applied mathematics
Applied mathematics is a branch of mathematics that concerns itself with mathematical methods that are typically used in science, engineering, business, and industry. Thus, "applied mathematics" is a mathematical science with specialized knowledge...
and scientific computing to numerically solve certain Dynamical System
Dynamical system
A dynamical system is a concept in mathematics where a fixed rule describes the time dependence of a point in a geometrical space. Examples include the mathematical models that describe the swinging of a clock pendulum, the flow of water in a pipe, and the number of fish each springtime in a...
s, often involving the use of the Fast Fourier Transform
Fast Fourier transform
A fast Fourier transform is an efficient algorithm to compute the discrete Fourier transform and its inverse. "The FFT has been called the most important numerical algorithm of our lifetime ." There are many distinct FFT algorithms involving a wide range of mathematics, from simple...
. Where applicable, spectral methods have excellent error properties, with the so called "exponential convergence" being the fastest possible. Spectral methods were developed in a long series of papers by Steven Orszag starting in 1969 including, but not limited to, Fourier series methods for periodic geometry problems, polynomial spectral methods for finite and unbounded geometry problems, pseudospectral methods for highly nonlinear problems, and spectral iteration methods for fast solution of steady state problems.
Partial differential equations (PDEs) describe a wide array of physical processes such as heat conduction, fluid flow, and sound propagation. In many such equations, there are underlying "basic waves" that can be used to give efficient algorithms for computing solutions to these PDEs. In a typical case, spectral methods take advantage of this fact by writing the solution as its Fourier series
Fourier series
In mathematics, a Fourier series decomposes periodic functions or periodic signals into the sum of a set of simple oscillating functions, namely sines and cosines...
, substituting this series into the PDE to get a system of ordinary differential equations (ODEs) in the time-dependent coefficients of the trigonometric terms in the series (written in complex exponential form), and using a time-stepping method to solve those ODEs.
The spectral method and the finite element method
Finite element method
The finite element method is a numerical technique for finding approximate solutions of partial differential equations as well as integral equations...
are closely related and built on the same ideas; the main difference between them is that the spectral method approximates the solution as linear combination
Linear combination
In mathematics, a linear combination is an expression constructed from a set of terms by multiplying each term by a constant and adding the results...
of continuous functions that are generally nonzero over the domain of solution (usually sinusoids or Chebyshev polynomials), while the finite element method approximates the solution as a linear combination of piecewise functions that are nonzero on small subdomains. Because of this, the spectral method takes on a global approach while the finite element method is a local approach. This is part of why the spectral method works best when the solution is smooth
Smooth function
In mathematical analysis, a differentiability class is a classification of functions according to the properties of their derivatives. Higher order differentiability classes correspond to the existence of more derivatives. Functions that have derivatives of all orders are called smooth.Most of...
. In fact there are no known three-dimensional single domain spectral shock capturing results.
In the finite element community, a method where the degree of the elements is very high or increases as the grid parameter h decreases to zero is sometimes called a spectral element method
Spectral element method
In mathematics, the spectral element method is a high order finite element method.Introduced in a 1984 paper by A. T. Patera, the abstract begins: "A spectral element method that combines the generality of the finite element method with the accuracy of spectral techniques..."The spectral element...
.
The implementation of the spectral method is normally accomplished either with collocation
Collocation method
In mathematics, a collocation method is a method for the numerical solution of ordinary differential equations, partial differential equations and integral equations...
or a Galerkin
Galerkin method
In mathematics, in the area of numerical analysis, Galerkin methods are a class of methods for converting a continuous operator problem to a discrete problem. In principle, it is the equivalent of applying the method of variation of parameters to a function space, by converting the equation to a...
or a Tau approach.
A concrete, linear example
Here we presume an understanding of basic multivariate calculusCalculus
Calculus is a branch of mathematics focused on limits, functions, derivatives, integrals, and infinite series. This subject constitutes a major part of modern mathematics education. It has two major branches, differential calculus and integral calculus, which are related by the fundamental theorem...
and Fourier series
Fourier series
In mathematics, a Fourier series decomposes periodic functions or periodic signals into the sum of a set of simple oscillating functions, namely sines and cosines...
. If g(x,y) is a known, complex-valued function of two real variables, and g is periodic in x and y (that is, g(x,y)=g(x+2π,y)=g(x,y+2π)) then we are interested in finding a function f(x,y) so that
where the expression on the left denotes the second partial derivatives of f in x and y, respectively. This is the Poisson equation, and can be physically interpreted as some sort of heat conduction problem.
If we write f and g in Fourier series:
and substitute into the differential equation, we obtain this equation:
We have exchanged partial differentiation with an infinite sum, which is legitimate if we assume for instance that f has a continuous second derivative. By the uniqueness theorem for Fourier expansions, we must then equate the Fourier coefficients term by term, giving
which is an explicit formula for the Fourier coefficients aj,k.
With periodic boundary-conditions, the Poisson equation possesses a solution only if b0,0 = 0. Therefore
we can freely choose a0,0 which will be equal to the mean of the resolution. This corresponds to choosing the
integration constant.
To turn this into an algorithm, only finitely many frequencies are solved for. This introduces an error which can be shown to be proportional to
, where and is the highest frequency treated.Algorithm
- Compute the Fourier transform (bj,k) of g.
- Compute the Fourier transform (aj,k) of f via the formula (*) and the Fourier transform of g.
- Compute f by taking an inverse Fourier transform of (aj,k).
Since we're only interested in a finite window of frequencies (of size n, say) this can be done using a Fast Fourier Transform
Fast Fourier transform
A fast Fourier transform is an efficient algorithm to compute the discrete Fourier transform and its inverse. "The FFT has been called the most important numerical algorithm of our lifetime ." There are many distinct FFT algorithms involving a wide range of mathematics, from simple...
algorithm. Therefore, globally the algorithm runs in time O(n log n).
A concrete, nonlinear example
We wish to solve the forced, transient, nonlinear Burgers' equationBurgers' equation
Burgers' equation is a fundamental partial differential equation from fluid mechanics. It occurs in various areas of applied mathematics, such as modeling of gas dynamics and traffic flow...
using a spectral approach.
Given
on the periodic domain, find such thatIn weak, conservative form this becomes
where
following inner productInner product space
In mathematics, an inner product space is a vector space with an additional structure called an inner product. This additional structure associates each pair of vectors in the space with a scalar quantity known as the inner product of the vectors...
notation. Integrating by parts
Integration by parts
In calculus, and more generally in mathematical analysis, integration by parts is a rule that transforms the integral of products of functions into other integrals...
and using periodicity grants
To apply the Fourier−Galerkin method
Galerkin method
In mathematics, in the area of numerical analysis, Galerkin methods are a class of methods for converting a continuous operator problem to a discrete problem. In principle, it is the equivalent of applying the method of variation of parameters to a function space, by converting the equation to a...
, choose both
and
where
. This reduces the problem to finding such thatUsing the orthogonality
Orthogonality
Orthogonality occurs when two things can vary independently, they are uncorrelated, or they are perpendicular.-Mathematics:In mathematics, two vectors are orthogonal if they are perpendicular, i.e., they form a right angle...
relation
where is the Kronecker delta, we simplify the above three terms for each to seeAssemble the three terms for each
to obtainDividing through by
, we finally arrive atWith Fourier transformed initial conditions
and forcing , this coupled system of ordinary differential equations may be integrated in time (using, e.g., a Runge Kutta technique) to find a solution. The nonlinear term is a convolutionConvolution
In mathematics and, in particular, functional analysis, convolution is a mathematical operation on two functions f and g, producing a third function that is typically viewed as a modified version of one of the original functions. Convolution is similar to cross-correlation...
, and there are several transform-based techniques for evaluating it efficiently. See the references by Boyd and Canuto et al. for more details.
A relationship with the spectral element method
One can show that if is infinitely differentiable, then the numerical algorithm using Fast Fourier Transforms will converge faster than any polynomial in the grid size h. That is, for any n>0, there is a such that the error is less than for all sufficiently small values of . We say that the spectral method is of order , for every n>0.Because a spectral element method
Spectral element method
In mathematics, the spectral element method is a high order finite element method.Introduced in a 1984 paper by A. T. Patera, the abstract begins: "A spectral element method that combines the generality of the finite element method with the accuracy of spectral techniques..."The spectral element...
is a finite element method
Finite element method
The finite element method is a numerical technique for finding approximate solutions of partial differential equations as well as integral equations...
of very high order, there is a similarity in the convergence properties. However, whereas the spectral method is based on the eigendecomposition of the particular boundary value problem, the spectral element method does not use that information and works for arbitrary elliptic boundary value problem
Elliptic boundary value problem
In mathematics, an elliptic boundary value problem is a special kind of boundary value problem which can be thought of as the stable state of an evolution problem...
s.
See also
- Discrete element methodDiscrete element methodA discrete element method , also called a distinct element method is any of family of numerical methods for computing the motion of a large number of particles of micrometre-scale size and above...
- Gaussian gridGaussian gridA Gaussian grid is used in the earth sciences as a gridded horizontal coordinate system for scientific modeling on a sphere...
- Pseudo-spectral methodPseudo-spectral methodPseudo-spectral methods are a class of numerical methods used in applied mathematics and scientific computing for the solution of PDEs, such as the direct simulation of a particle with an arbitrary wavefunction interacting with an arbitrary potential...
- Spectral element methodSpectral element methodIn mathematics, the spectral element method is a high order finite element method.Introduced in a 1984 paper by A. T. Patera, the abstract begins: "A spectral element method that combines the generality of the finite element method with the accuracy of spectral techniques..."The spectral element...
- Galerkin methodGalerkin methodIn mathematics, in the area of numerical analysis, Galerkin methods are a class of methods for converting a continuous operator problem to a discrete problem. In principle, it is the equivalent of applying the method of variation of parameters to a function space, by converting the equation to a...
- Collocation methodCollocation methodIn mathematics, a collocation method is a method for the numerical solution of ordinary differential equations, partial differential equations and integral equations...