Spectral method

Encyclopedia

**Spectral methods**are a class of techniques used in applied mathematics

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

*a*

_{j,k}.

With periodic boundary-conditions, the Poisson equation possesses a solution only if

*b*

_{0,0}=

*0*. Therefore

we can freely choose

*a*

_{0,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 (
*b*) of_{j,k}*g*. - Compute the Fourier transform (
*a*) of_{j,k}*f*via the formula (*) and the Fourier transform of*g*. - Compute
*f*by taking an inverse Fourier transform of (*a*)._{j,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 that

In weak, conservative form this becomes

where following inner product

Inner 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 that

Using 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 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

Convolution

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...