Spectral method

From Wikipedia, the free encyclopedia

Spectral methods are a class of techniques used in applied mathematics and scientific computing to numerically solve certain partial differential equations, often involving the use of the Fast Fourier Transform. For well-behaved problems, spectral methods have excellent error properties: The more differentiable the solution is, the better the accuracy of the method.

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

Note the differences between the major methods: Finite difference methods approximate the equation. Finite element methods approximate its solution. Spectral methods approximate its solution via its Fourier series. Simulation methods, such as molecular dynamics, model the very physics of the problem.

Spectral method can also mean the use of high-order polynomials to approximate the solution to a PDE. It is known as the spectral element method when combined with the finite element method.

1 A concrete example
- 1.1 Algorithm
2 See also
3 References

[edit] A concrete example

Here we presume a basic understanding of basic multivariate calculus 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

$\left(\frac{\partial^2}{\partial x^2}+\frac{\partial^2}{\partial y^2}\right)f(x,y)=g(x,y)\quad \mbox{for all } x,y$

where the expression on the left denotes the second partial derivatives of f in x and y, respectively. This is Poisson's equation, and can be physically interpreted as some sort of heat conduction problem.

If we write f and g in Fourier series:

$f=\sum a_{j,k}e^{ijx+iky}$

$g=\sum b_{j,k}e^{ijx+iky}$

and substitute into the differential equation, we obtain this equation:

$\sum -a_{j,k}(j^2+k^2)e^{ijx+iky}=\sum b_{j,k}e^{ijx+iky}$

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

(*) $a_{j,k}=-\frac{b_{j,k}}{j^2+k^2}$

which is an explicit formula for the Fourier coefficients a_j,k.

To turn this into an algorithm, only finitely many frequencies are solved for.

[edit] Algorithm

Compute the Fourier transform (b_j,k) of g.
Compute the Fourier transform (a_j,k) of 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 algorithm. Therefore, globally the algorithm runs in time O(nlogn).