Fourier pseudo-spectral method

A type of trigonometric pseudo-spectral method (cf. Trigonometric pseudo-spectral methods) used to solve differential and integral equations. See also Chebyshev pseudo-spectral method.

The Fourier pseudo-spectral method is used for problems in which there is a natural periodicity. In multi-dimensional problems it should be used only in those directions with periodic boundary conditions. In non-periodic directions, Chebyshev methods, finite element or difference methods of high order should be used.

Suppose the equation is to be solved where is a differential operator, is a given periodic function and is an unknown periodic function (period ). In the Fourier pseudo-spectral method, the solution is approximated by a trigonometric polynomial that interpolates at equally spaced points , .

The Lagrange interpolation polynomial (cf. also Lagrange interpolation formula) has the form , where is the Cardinal function, having the form

An equivalent way of defining the interpolating polynomial is by the discrete Fourier transform: , where the Fourier coefficients are

In the Lagrange polynomial or "grid-point representation" , the problem can be written as , where The form of can be found through differentiation of the Cardinal function: ,

to give a few. The derivative matrices are full and operations are required for evaluation.

The problem can also be formulated using the spectral coefficient representation. Derivatives are found through differentiation of the discrete Fourier series, for example,

and have an operation count. If the operator is non-linear or has non-constant coefficients multiplying the derivatives, evaluation of is much more complicated.

The fast Fourier transform provides a way of switching between grid-point and spectral representations in operations, instead of the using the definitions above. Derivatives can be accomplished in spectral space and multiplication of non-constant coefficients or evaluation of non-linear terms can be accomplished in grid point space — each with operations.

Particularly for time-dependent problems in which boundary value problems must be solved at each time step, it is very important to minimize operation counts by taking full advantage of each representation and the fast transformation between representations.

As an example, consider the operator

for the time-dependent problem . Suppose at a particular time the spectral coefficients , , are known. To compute , first the spectral coefficients of the first- and second-order derivatives are found: and . Then both of these arrays are transformed into their grid point representation using a fast Fourier transformation. Then can be evaluated in operations. The complete evaluation of the operator is done in operations rather than if done completely in one space. This property becomes even more critical for multi-dimensional problems; the operation counts are versus for a -dimensional problem.

References

[a1]	J.P. Boyd, "Chebyshev and Fourier spectral methods" , Dover (2000) (pdf version: http://www-personal.engin.umich.edu/~jpboyd/book_spectral2000.html)
[a2]	D. Gottlieb, S.A. Orszag, "Numerical analysis of spectral methods: Theory and applications" , SIAM (1977)
[a3]	C. Canuto, M.Y. Hussaini, A. Quarteroni, T.A. Zang, "Spectral methods in fluid dynamics" , Springer (1987)
[a4]	D. Gottlieb, M.Y. Hussaini, S.A. Orszag, "Theory and application of spectral methods" R.G. Voigt (ed.) D. Gottlieb (ed.) M.Y. Hussaini (ed.) , Spectral Methods for Partial Differential Equations , SIAM (1984)
[a5]	B. Fornberg, "A practical guide to pseudospectral methods" , Cambridge Monographs Appl. Comput. Math. , 1 , Cambridge Univ. Press (1996)